適應多核處理器的任務調(diào)度研究.pdf

1、多核并行系統(tǒng)中的任務調(diào)度是根據(jù)一定的調(diào)度規(guī)則和策略，將復雜程序的所有任務按照一定執(zhí)行時序分配到并行分布的多個內(nèi)核上，并行處理任務。這個問題是強NP完全的，是最難的組合優(yōu)化問題之一。各國學者對多核處理器上的任務調(diào)度技術開展了一些研究，提出了多種調(diào)度模型和算法，可是這些算法存在著調(diào)度效率低和不能適應處理器內(nèi)核資源變化等問題，可見適應多核并行系統(tǒng)的任務調(diào)度問題仍然是一個不成熟的領域。本文研究的是多核處理器并行系統(tǒng)下的任務調(diào)度問題，既考慮了任務

2、調(diào)度的執(zhí)行效率，又考慮了調(diào)度結果能夠按照處理器內(nèi)核的具體數(shù)量調(diào)整的情況，具有重要的理論和實際意義。
　　 針對目前任務調(diào)度算法調(diào)度時間長或復雜度高的問題，提出一種基于任務復制的調(diào)度算法。算法首先通過復制任務的方式將任務圖轉換成結構簡單的join結構圖；對join結構圖采取一種調(diào)度策略：選擇使join節(jié)點任務能夠最早開始的方案，將join節(jié)點任務與其前驅(qū)節(jié)點任務形成調(diào)度組合，實現(xiàn)join節(jié)點任務開始時間的提前和各前驅(qū)節(jié)點任務到不同

3、內(nèi)核上并行執(zhí)行，達到提高算法調(diào)度效率的目的。
　　 針對目前算法在處理資源緊缺的情況下算法不能根據(jù)內(nèi)核的具體數(shù)量調(diào)整的問題，本文提出了一種適應具體內(nèi)核數(shù)的調(diào)度算法。該算法先將任務圖分解為無關的執(zhí)行序列，消除任務間的聯(lián)系；然后為每個執(zhí)行序列分配一個核。當內(nèi)核數(shù)少于執(zhí)行序列數(shù)時，采取策略合并執(zhí)行序列以減少執(zhí)行序列數(shù)。實現(xiàn)根據(jù)處理器內(nèi)核的具體數(shù)量調(diào)度任務。
　　 針對目前算法在處理資源充足的情況下核間通信開銷大的問題，提出了一