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

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

2、務(wù)圖拓?fù)湫蛄谐霭l(fā)，以拓展任務(wù)圖拓?fù)湫蛄兴阉骺臻g為指導(dǎo)，提出了迭代型列表調(diào)度方法，并給出兩種迭代型列表調(diào)度算法實(shí)現(xiàn):ILS-Mb(Iterative List Scheduling with Macroblock)和ILS-RS（Iterative List Scheduling with Random Swapping）。其中迭代型列表調(diào)度算法ILS-Mb通過遍歷宏塊拓?fù)湫蛄袛U(kuò)大任務(wù)圖拓?fù)湫蛄兴阉骺臻g，迭代型列表調(diào)度算法ILS-RS則通

3、過對(duì)換兩個(gè)隨機(jī)任務(wù)的優(yōu)先級(jí)以生成新的任務(wù)圖拓?fù)湫蛄小LS-Mb算法和ILS-RS算法的共同之處在于多次進(jìn)行列表調(diào)度并根據(jù)調(diào)度長度最小化原則篩選最優(yōu)調(diào)度解。本文進(jìn)一步地結(jié)合粒子群算法采用多個(gè)初始最優(yōu)解的基本思路提出組合型列表調(diào)度方法。組合型列表調(diào)度方法以多個(gè)最優(yōu)任務(wù)圖拓?fù)湫蛄凶鳛槌跏冀獗苊鈫蝹€(gè)任務(wù)圖拓?fù)湫蛄邢萑刖植孔顑?yōu)解。迭代型列表調(diào)度方法和組合型列表調(diào)度方法的結(jié)合形成迭代-組合型列表調(diào)度方法，以更高的算法時(shí)間復(fù)雜度以期獲取更小的調(diào)度長

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