適應(yīng)多核處理器的任務(wù)調(diào)度研究.pdf

1、多核并行系統(tǒng)中的任務(wù)調(diào)度是根據(jù)一定的調(diào)度規(guī)則和策略，將復(fù)雜程序的所有任務(wù)按照一定執(zhí)行時(shí)序分配到并行分布的多個(gè)內(nèi)核上，并行處理任務(wù)。這個(gè)問(wèn)題是強(qiáng)NP完全的，是最難的組合優(yōu)化問(wèn)題之一。各國(guó)學(xué)者對(duì)多核處理器上的任務(wù)調(diào)度技術(shù)開(kāi)展了一些研究，提出了多種調(diào)度模型和算法，可是這些算法存在著調(diào)度效率低和不能適應(yīng)處理器內(nèi)核資源變化等問(wèn)題，可見(jiàn)適應(yīng)多核并行系統(tǒng)的任務(wù)調(diào)度問(wèn)題仍然是一個(gè)不成熟的領(lǐng)域。本文研究的是多核處理器并行系統(tǒng)下的任務(wù)調(diào)度問(wèn)題，既考慮了任務(wù)

2、調(diào)度的執(zhí)行效率，又考慮了調(diào)度結(jié)果能夠按照處理器內(nèi)核的具體數(shù)量調(diào)整的情況，具有重要的理論和實(shí)際意義。
　　 針對(duì)目前任務(wù)調(diào)度算法調(diào)度時(shí)間長(zhǎng)或復(fù)雜度高的問(wèn)題，提出一種基于任務(wù)復(fù)制的調(diào)度算法。算法首先通過(guò)復(fù)制任務(wù)的方式將任務(wù)圖轉(zhuǎn)換成結(jié)構(gòu)簡(jiǎn)單的join結(jié)構(gòu)圖；對(duì)join結(jié)構(gòu)圖采取一種調(diào)度策略：選擇使join節(jié)點(diǎn)任務(wù)能夠最早開(kāi)始的方案，將join節(jié)點(diǎn)任務(wù)與其前驅(qū)節(jié)點(diǎn)任務(wù)形成調(diào)度組合，實(shí)現(xiàn)join節(jié)點(diǎn)任務(wù)開(kāi)始時(shí)間的提前和各前驅(qū)節(jié)點(diǎn)任務(wù)到不同

3、內(nèi)核上并行執(zhí)行，達(dá)到提高算法調(diào)度效率的目的。
　　 針對(duì)目前算法在處理資源緊缺的情況下算法不能根據(jù)內(nèi)核的具體數(shù)量調(diào)整的問(wèn)題，本文提出了一種適應(yīng)具體內(nèi)核數(shù)的調(diào)度算法。該算法先將任務(wù)圖分解為無(wú)關(guān)的執(zhí)行序列，消除任務(wù)間的聯(lián)系；然后為每個(gè)執(zhí)行序列分配一個(gè)核。當(dāng)內(nèi)核數(shù)少于執(zhí)行序列數(shù)時(shí)，采取策略合并執(zhí)行序列以減少執(zhí)行序列數(shù)。實(shí)現(xiàn)根據(jù)處理器內(nèi)核的具體數(shù)量調(diào)度任務(wù)。
　　 針對(duì)目前算法在處理資源充足的情況下核間通信開(kāi)銷大的問(wèn)題，提出了一