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

1、隨著CMP的出現(xiàn)，如何提升其運(yùn)行效率和最大化并行性倍受?chē)?guó)內(nèi)外專家和學(xué)者的關(guān)注。系統(tǒng)性能的提升不僅與硬件平臺(tái)有關(guān)，同時(shí)也離不開(kāi)硬件平臺(tái)上的優(yōu)化軟件設(shè)計(jì)，只有兩者充分結(jié)合，才能充分發(fā)揮硬件平臺(tái)自身及軟件設(shè)計(jì)的優(yōu)良性能。因此，CMP任務(wù)調(diào)度問(wèn)題已經(jīng)成為高性能CMP研究領(lǐng)域的熱點(diǎn)之一。鑒于CMP平臺(tái)的優(yōu)良性能和未來(lái)發(fā)展趨勢(shì)，本文將異構(gòu)CMP上的靜態(tài)任務(wù)調(diào)度算法作為研究對(duì)象，設(shè)計(jì)一種適合其硬件平臺(tái)且性能較好的靜態(tài)任務(wù)調(diào)度算法，該算法能夠縮短全部任

2、務(wù)執(zhí)行完成時(shí)間，充分發(fā)揮出異構(gòu)CMP的性能優(yōu)勢(shì)，提升CMP的執(zhí)行效率。
　　本文通過(guò)對(duì)CMP架構(gòu)、任務(wù)調(diào)度技術(shù)及其現(xiàn)有四種經(jīng)典異構(gòu)CMP上的靜態(tài)任務(wù)調(diào)度算法進(jìn)行分析，并針對(duì)現(xiàn)有靜態(tài)任務(wù)調(diào)度算法的不足，提出一種全局較優(yōu)任務(wù)調(diào)度算法。新算法首先對(duì)任務(wù)圖中某些特殊任務(wù)進(jìn)行歸并優(yōu)化；然后通過(guò)任務(wù)分層、標(biāo)記關(guān)鍵任務(wù)和任務(wù)優(yōu)先級(jí)權(quán)值計(jì)算三個(gè)過(guò)程順序執(zhí)行來(lái)構(gòu)造任務(wù)調(diào)度列表；最后在任務(wù)分配的同時(shí)加入冗余任務(wù)處理過(guò)程，兩個(gè)過(guò)程交替進(jìn)行，直到所有任務(wù)

3、調(diào)度完成。新算法保證逐層調(diào)度任務(wù)，考慮賦予關(guān)鍵任務(wù)較高優(yōu)先級(jí)，縮短整個(gè)任務(wù)圖的總完成時(shí)間。在任務(wù)分配時(shí)，采用區(qū)間插入和任務(wù)復(fù)制技術(shù)，通過(guò)在空閑時(shí)間段進(jìn)行必要的插入和復(fù)制，復(fù)制當(dāng)前任務(wù)的關(guān)鍵父任務(wù)來(lái)提前當(dāng)前任務(wù)的最早完成時(shí)間，同時(shí)對(duì)冗余任務(wù)進(jìn)行了檢測(cè)、刪除操作，充分利用處理器資源，提前后續(xù)任務(wù)的最早完成時(shí)間；且能及時(shí)刪除調(diào)度結(jié)果中的冗余任務(wù)，避免處理器資源的浪費(fèi)，縮短全部任務(wù)執(zhí)行完成時(shí)間，最終提升了整個(gè)CMP的性能。
　　為了驗(yàn)證全

4、局較優(yōu)任務(wù)調(diào)度算法的可行性和高效性，本文采用TGFF隨機(jī)生成大量具有不同特點(diǎn)的任務(wù)圖，在不同的硬件條件下對(duì)算法進(jìn)行測(cè)試，并在Matlab平臺(tái)編程實(shí)現(xiàn)該算法，驗(yàn)證新算法的調(diào)度性能。實(shí)驗(yàn)結(jié)果表明：新的算法繼承了現(xiàn)有算法優(yōu)先調(diào)度關(guān)鍵任務(wù)的優(yōu)點(diǎn)，同時(shí)改善了現(xiàn)有算法的任務(wù)優(yōu)先級(jí)選取過(guò)于單一所產(chǎn)生的局部較優(yōu)調(diào)度結(jié)果的問(wèn)題，且能有效的處理任務(wù)復(fù)制所帶來(lái)的冗余；在任務(wù)執(zhí)行過(guò)程中，任務(wù)間的并行性明顯提高，任務(wù)總調(diào)度長(zhǎng)度也明顯減小，達(dá)到了算法改進(jìn)的預(yù)期效果