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

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

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

3、，提出了基于動態(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ào)度序列。當(dāng)該子樹調(diào)度完畢后，將其整體虛擬為一個任務(wù)節(jié)點，加入上一級子樹中進行調(diào)度，直到產(chǎn)品加工樹中所有節(jié)點調(diào)度完畢為止。
　　針對目前大多數(shù)適應(yīng)多核處理器的調(diào)度算法不能夠根據(jù)處理器內(nèi)核數(shù)量調(diào)整調(diào)度序列數(shù)量，導(dǎo)致處理器當(dāng)前剩余內(nèi)核不足時任務(wù)不能夠得到及時有效的調(diào)度的問題