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

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

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

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

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