基于異構多核處理器的靜態(tài)任務調度算法研究.pdf

1、伴隨著半導體制造工藝的發(fā)展，單位面積內(nèi)所能集成的晶體管的數(shù)目已經(jīng)達到極限，單核處理器碰到了無法逾越的障礙，多核處理器逐漸變成人們研究的熱門和重點。多核處理器分為同構多核處理器和異構多核處理器，專家學者和界內(nèi)人士普遍認為異構多核處理器將會是未來的主流處理器。任務調度的順序將會直接影響處理器的性能，因此，異構多核處理器的任務調度研究已經(jīng)成為研究熱點。
　　異構多核處理器的任務調度已經(jīng)被證明是NP完全問題，目前還沒有算法可以在多項式時間

2、內(nèi)求得最優(yōu)解，現(xiàn)有算法大都是使用啟發(fā)式的算法求得近似解，而其中的基于列表調度算法應用較為廣泛。經(jīng)典的基于列表調度算法有HEFT（Heterogeneous Earlier Finish Time）算法和HCNF（Heterogeneous Critical Node First）算法。HEFT算法按照ranku非遞增次序調度任務，使用區(qū)間插入技術分配任務。HCNF算法優(yōu)先調度關鍵任務，使用任務復制技術分配任務。
　　以上算法存在調

3、度結果不理想、處理器空閑時間段較多等問題，眾多專家學者對此都提出了改進方案。綜合考慮任務的約束依賴關系對調度結果的影響，使用區(qū)間插入技術和任務復制技術充分利用處理器的空閑時間段。本文吸取典型算法的優(yōu)點，并綜合專家學者的改進策略，在現(xiàn)有算法的基礎上加以改進。為了評價改進算法的性能，本文通過具體的測試用例說明改進算法的具體實現(xiàn)過程，并對比調度結果，接著設計測試方案，調度隨機生成的DAG任務圖集，對實驗結果進行分析比較。通過實驗證明，改進算法