基于異構(gòu)多核處理器的靜態(tài)任務(wù)調(diào)度算法研究.pdf

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

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

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