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

1、多核處理器任務(wù)調(diào)度主要研究如何通過(guò)一定的調(diào)度算法將任務(wù)分配到多個(gè)并行的計(jì)算內(nèi)核上執(zhí)行，使任務(wù)完成總時(shí)間得以縮短。這一問(wèn)題早已被證明是NP完全的問(wèn)題。各國(guó)學(xué)者們針對(duì)該問(wèn)題進(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)化算法沒(méi)有考慮關(guān)鍵路徑上節(jié)點(diǎn)對(duì)任務(wù)完成時(shí)間有重要影

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

3、，提出了基于動(dòng)態(tài)關(guān)鍵路徑的多核調(diào)度算法。該算法通過(guò)將任務(wù)圖轉(zhuǎn)換為產(chǎn)品加工樹(shù)，并在加工樹(shù)中按層序?qū)a(chǎn)品加工樹(shù)分解成子樹(shù)，在子樹(shù)中查找關(guān)鍵路徑，并且優(yōu)先調(diào)度關(guān)鍵節(jié)點(diǎn)形成調(diào)度序列。當(dāng)該子樹(shù)調(diào)度完畢后，將其整體虛擬為一個(gè)任務(wù)節(jié)點(diǎn)，加入上一級(jí)子樹(shù)中進(jìn)行調(diào)度，直到產(chǎn)品加工樹(shù)中所有節(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)度的問(wèn)題