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

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

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