異構(gòu)多核環(huán)境下的任務(wù)調(diào)度方法研究.pdf

1、任務(wù)調(diào)度方法研究是計(jì)算機(jī)學(xué)科的基本課題之一。近年來(lái)，多核體系結(jié)構(gòu)的出現(xiàn)，給這門(mén)學(xué)科帶來(lái)了新的挑戰(zhàn)。多核系統(tǒng)的任務(wù)調(diào)度問(wèn)題是把若干個(gè)任務(wù)分配到一定數(shù)目的處理器上，使得任務(wù)完成時(shí)間最短。有效的任務(wù)調(diào)度方法將會(huì)大大提高多處理器系統(tǒng)的計(jì)算能力，降低不必要的能耗。異構(gòu)多核系統(tǒng)由于其處理器特性的不同，任務(wù)調(diào)度方法也尤為復(fù)雜。
　　 異構(gòu)環(huán)境下的任務(wù)調(diào)度方法主要分為兩個(gè)步驟：(一)將一個(gè)應(yīng)用程序分割成若干個(gè)任務(wù)，生成應(yīng)用模型，盡可能的獲取任務(wù)

2、間的并行性。(二)根據(jù)應(yīng)用模型，采用一定任務(wù)調(diào)度算法，將任務(wù)分配到合適的處理器上。
　　 本文以獨(dú)立任務(wù)和依賴任務(wù)為研究對(duì)象，對(duì)異構(gòu)多處理器系統(tǒng)的任務(wù)調(diào)度方法進(jìn)行深入的研究。通過(guò)對(duì)當(dāng)前的獨(dú)立任務(wù)調(diào)度算法和依賴任務(wù)調(diào)度算法的改進(jìn)，獲得更快的任務(wù)完成時(shí)間和較小的算法復(fù)雜度。主要工作體現(xiàn)在如下幾個(gè)方面：
　　 (1)從任務(wù)模型和處理器模型兩方面對(duì)應(yīng)用模型進(jìn)行介紹，對(duì)目前主要的任務(wù)分割方法、任務(wù)調(diào)度模型和處理器模型進(jìn)行比較和分析

3、。
　　 (2)基于任務(wù)交互圖任務(wù)模型(Task Precedence Graph，TPG)，對(duì)現(xiàn)有的獨(dú)立任務(wù)調(diào)度方法進(jìn)行研究。針對(duì)Min-Min算法在處理器性能差別較大和短作業(yè)較多兩種情況下，存在的任務(wù)完成時(shí)間過(guò)長(zhǎng)及處理器負(fù)載不均問(wèn)題，提出一種改進(jìn)的Div-Sub算法。Div-Sub算法在分配任務(wù)之前，先觀察當(dāng)前每個(gè)處理器的負(fù)載，再把該任務(wù)分配給使當(dāng)前所有任務(wù)的完成時(shí)間最小的處理器。仿真結(jié)果表明，相對(duì)于Min-Min算法，Di

4、v-Sub算法在任務(wù)完成時(shí)間上提升了7[％]左右，是一種高效的獨(dú)立任務(wù)調(diào)度方法。
　　 (3)基于有向無(wú)環(huán)圖任務(wù)模型(Directed Acycling Graph，DAG)，采用基于表結(jié)構(gòu)的調(diào)度算法對(duì)現(xiàn)有的依賴任務(wù)調(diào)度方法進(jìn)行研究。針對(duì)HEFT算法的兩個(gè)不足，提出了一種改進(jìn)的APS(Accurate Priority Scheduling)算法。第一個(gè)不足是HEFT算法的任務(wù)優(yōu)先級(jí)的確定方式一次到位，無(wú)法對(duì)任務(wù)優(yōu)先級(jí)進(jìn)行調(diào)整。