異構多核環(huán)境下的任務調度方法研究.pdf

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

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

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

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