多核系統(tǒng)靜態(tài)任務調(diào)度問題研究.pdf

1、由于傳統(tǒng)單核處理器的性能已經(jīng)遇到發(fā)展瓶頸，多核處理器應運而生并獲得廣泛應用。作為多核技術的一個重要方面，任務調(diào)度是備受關注的一類NPC(Non-deterministic Polynomial Complete)問題。
　　對于多核處理器的靜態(tài)任務調(diào)度問題，經(jīng)典列表調(diào)度(Simple List Scheduling，SLS)算法難以獲得滿意的調(diào)度解。本文從經(jīng)典列表調(diào)度算法缺陷——只考慮任務優(yōu)先級列表而忽略其它對應于更好調(diào)度結(jié)果的任

2、務圖拓撲序列出發(fā)，以拓展任務圖拓撲序列搜索空間為指導，提出了迭代型列表調(diào)度方法，并給出兩種迭代型列表調(diào)度算法實現(xiàn):ILS-Mb(Iterative List Scheduling with Macroblock)和ILS-RS（Iterative List Scheduling with Random Swapping）。其中迭代型列表調(diào)度算法ILS-Mb通過遍歷宏塊拓撲序列擴大任務圖拓撲序列搜索空間，迭代型列表調(diào)度算法ILS-RS則通

3、過對換兩個隨機任務的優(yōu)先級以生成新的任務圖拓撲序列。ILS-Mb算法和ILS-RS算法的共同之處在于多次進行列表調(diào)度并根據(jù)調(diào)度長度最小化原則篩選最優(yōu)調(diào)度解。本文進一步地結(jié)合粒子群算法采用多個初始最優(yōu)解的基本思路提出組合型列表調(diào)度方法。組合型列表調(diào)度方法以多個最優(yōu)任務圖拓撲序列作為初始解避免單個任務圖拓撲序列陷入局部最優(yōu)解。迭代型列表調(diào)度方法和組合型列表調(diào)度方法的結(jié)合形成迭代-組合型列表調(diào)度方法，以更高的算法時間復雜度以期獲取更小的調(diào)度長

4、度。文中通過理論分析證明，對于任意的一個任務圖，兩種迭代型列表調(diào)度方法所得的調(diào)度長度必不大于經(jīng)典列表調(diào)度算法。
　　為證實本文提出的迭代型列表調(diào)度方法的良好性能，文中采用四種常見類型任務圖生成大量的任務圖樣本進行兩個部分的對比實驗。統(tǒng)計結(jié)果首先表明:在全互聯(lián)通訊環(huán)境迭代型的列表調(diào)度算法ILS-Mb和ILS-RS能夠有效改善經(jīng)典列表調(diào)度算法的調(diào)度解，尤其在通信代價比超過1的情況下，調(diào)度性能提升超過14.6％，最大的調(diào)度性能提升達到1