基于綜合調(diào)度關(guān)鍵路徑的多核任務(wù)調(diào)度研究.pdf

1、多核處理器任務(wù)調(diào)度主要研究如何通過一定的調(diào)度算法將任務(wù)分配到多個(gè)并行的計(jì)算內(nèi)核上執(zhí)行，使任務(wù)完成總時(shí)間得以縮短。這一問題早已被證明是NP完全的問題。各國(guó)學(xué)者們針對(duì)該問題進(jìn)行了研究，并提出了相應(yīng)的調(diào)度算法，但這些算法依然存在著進(jìn)一步完善的空間。本文主要在多核處理器任務(wù)分配方向進(jìn)行研究，對(duì)傳統(tǒng)任務(wù)調(diào)度算法進(jìn)行了改進(jìn)，具有一定的理論價(jià)值和實(shí)際意義。
　　針對(duì)目前大多數(shù)多核處理器任務(wù)分配優(yōu)化算法沒有考慮關(guān)鍵路徑上節(jié)點(diǎn)對(duì)任務(wù)完成時(shí)間有重要影

2、響，導(dǎo)致任務(wù)完成總時(shí)間延遲的問題，提出了基于關(guān)鍵路徑和任務(wù)復(fù)制(CPTD)的單任務(wù)調(diào)度算法。CPTD算法通過復(fù)制任務(wù)圖中fork節(jié)點(diǎn)的方式將任務(wù)圖轉(zhuǎn)化為與之相對(duì)應(yīng)的產(chǎn)品加工樹;再在生成的產(chǎn)品加工樹中找到關(guān)鍵路徑，并采取使關(guān)鍵路徑上節(jié)點(diǎn)的緊前節(jié)點(diǎn)盡早調(diào)度的方式，使關(guān)鍵路徑上節(jié)點(diǎn)盡早開始執(zhí)行。
　　針對(duì)關(guān)鍵路徑上的某一節(jié)點(diǎn)開始執(zhí)行時(shí)，當(dāng)前任務(wù)圖中的關(guān)鍵路徑可能已經(jīng)產(chǎn)生了變化，如不重新查找關(guān)鍵路徑不能保證下一待調(diào)度節(jié)點(diǎn)仍為關(guān)鍵節(jié)點(diǎn)的問題

3、，提出了基于動(dòng)態(tài)關(guān)鍵路徑的多核調(diào)度算法。該算法通過將任務(wù)圖轉(zhuǎn)換為產(chǎn)品加工樹，并在加工樹中按層序?qū)a(chǎn)品加工樹分解成子樹，在子樹中查找關(guān)鍵路徑，并且優(yōu)先調(diào)度關(guān)鍵節(jié)點(diǎn)形成調(diào)度序列。當(dāng)該子樹調(diào)度完畢后，將其整體虛擬為一個(gè)任務(wù)節(jié)點(diǎn)，加入上一級(jí)子樹中進(jìn)行調(diào)度，直到產(chǎn)品加工樹中所有節(jié)點(diǎn)調(diào)度完畢為止。
　　針對(duì)目前大多數(shù)適應(yīng)多核處理器的調(diào)度算法不能夠根據(jù)處理器內(nèi)核數(shù)量調(diào)整調(diào)度序列數(shù)量，導(dǎo)致處理器當(dāng)前剩余內(nèi)核不足時(shí)任務(wù)不能夠得到及時(shí)有效的調(diào)度的問題