一種異構多核處理器啟發式綜合任務調度算法

李靜梅，王 雪，韓啟龍

(哈爾濱工程大學計算機科學與技術學院，哈爾濱 150001)

1 概述

多核處理器的產生為處理器性能的提升開辟了新的空間。如何將任務分配到具有不同計算性能的處理器內核上執行，從而獲得最短的調度長度是影響異構多核處理器性能發揮的關鍵問題之一［1］。

任務調度問題是NP 完全問題，無法在多項式時間內獲得最優解［2］。目前，應用最為普遍的任務調度算法為啟發式任務調度算法，獲得的是近似最優解［3］。啟發式任務調度算法包括表調度算法、任務復制算法和聚簇算法［4］。單獨應用一種啟發式調度算法都存在適應面受限以及調度性能不高的缺點。所以，在實際應用中，往往在一個調度算法中結合多種啟發式算法，借鑒各算法的優點，突破單一算法帶來的性能瓶頸，提高調度效率。

基于以上研究背景，本文提出一種異構多核處理器(Multi-core Processor，CMP)啟發式綜合任務調度算法IHTSHMP(Integrated Heuristic Task Scheduling Algorithm for Heterogeneous Multi-core Processor)。該算法以表調度算法為基礎，從任務調度全局出發，設定任務調度優先級，按照優先級構造任務調度列表。在調度過程中，利用任務復制技術進行調度優化。最后采用區間插入的方式將任務分配到處理器內核上執行，提高處理器利用率。

2 啟發式任務調度算法分析

本文的研究成果是基于表調度算法和任務復制算法提出的一種改進的高效啟發式綜合任務調度算法。為更好地敘述本文的研究成果，現對表調度算法和任務復制算法進行分析，并著重分析其各自的優缺點。

2.1 表調度算法

通常將表調度算法的執行過程分為2 個部分:任務優先級排序和映射任務到目標處理器。首先依據優先級權值的大小將任務添加到任務調度列表中，其次根據設定調度規則依序將調度列表中的任務分配到相應的處理器內核上執行［5-6］。表調度算法是一種高效的啟發式算法，具有算法實現簡單、調度額外開銷小和可預測性好等性能優勢，在任務調度問題中應用廣泛［7］。盡管表調度算法在性能提升方面有所裨益，但是優化過程缺乏針對性，單純使用表調度技術很難得到理想的調度結果。表調度具體工作流程如圖1 所示。

圖1 表調度流程

2.2 任務復制算法

任務復制算法是指在任務調度過程中按照設定條件，將符合條件的任務冗余地復制到處理器內核上，減少核間依賴任務的通信時延［8］。任務復制技術可有效縮短任務整體的完成時間，在本質上是一種犧牲空間來換取時間收益的方法。任務復制的關鍵在于如何選擇復制的任務。根據復制任務的個數，可以將任務復制算法分為單復制［9］和多復制［10］2 種，前者僅復制對當前任務開始時間影響最大的節點到處理器內核，后者復制多個符合條件的前驅任務。

在多核處理器系統中，利用任務復制將通信時延較大的核間開銷轉化為核內開銷，縮短了任務執行長度。由于使用任務復制技術需要對任務前驅節點進行搜索和對節點信息進行存儲，因此任務復制算法可能會增加調度算法的時間復雜性和空間復雜性，若使用不當會造成系統性能的下降。截至目前，任務復制算法雖然具有復雜性高的缺點，卻因其在減少通信開銷時間方面的貢獻而被廣泛應用于任務調度算法中。

3 IHTSHMP 算法

本文針對現有啟發式任務調度算法存在的缺點與不足，提出一種異構CMP 啟發式綜合任務調度算法IHTSHMP。IHTSHMP 算法采用表調度為主要思想將任務調度分為優先級排序和任務分配2 個階段。首先利用全局調度優化思想，設定優先級權值，并以此為依據構建任務執行列表。其次在任務分配階段利用任務復制技術復制任務的關鍵前驅節點，并以區間插入式的分配方式將任務分配到處理器內核上執行，進一步優化任務調度效率。

3.1 調度模型

調度模型包括任務模型和處理器模型，假設任務數為N，處理器內核數為M。

(1)任務模型

為分析任務間的依賴關系，采用圖論中的有向無環圖(Directed Acyclic Graph，DAG)來表示任務的執行屬性及依賴關系。

DAG 任務圖G=(V，E，τ，c)為一個四元組。其中，V 為長度為N 的任務節點集合;元素ni表示集合中的第i 個元素，0≤i≤N -1;E 為任務圖中有向邊的集合，表示任務之間的依賴關系;τ 為任務執行時間的集合，元素τ(ni，pu)表示任務ni在內核pu上的執行時間，在DAG 任務圖中表現為節點的權值;c 為依賴任務之間通信時延的集合，元素cij表示任務ni和nj之間的通信時延大小，在DAG 任務圖中表現為有向邊的權值。如圖2 所示為一個具有10 個節點的DAG 任務圖。

圖2 具有10 個節點的DAG 任務圖

在DAG 任務圖中，對于任意任務ni都有直接前驅節點集合prep(ni)、關鍵前驅節點fprep(ni)、后繼節點集合succ(ni)、在任意核pu上的最開始時間est(ni，pu)和最早完成時間eft(ni，pu)5 個重要屬性。其中，est(ni，pu)和eft(ni，pu)的定義分別如式(1)、式(2)所示。在式(1)中，p_avail 為處理器內核可利用時間，即處理器可以接受并執行任務的開始時間。

(2)處理器模型

本文的研究平臺是異構多核處理器，假設處理器結構為片上全相連網狀結構，任意2 個內核之間可以直接通信。定義處理器內核集合P，集合元素pu為第u 個內核，1≤u≤M。

3.2 優先級計算

關鍵路徑是DAG 任務圖的最長路徑，是獲得任務圖最短調度長度的瓶頸所在，所以對關鍵任務的合理調度也顯得尤為重要。IHTSHMP 算法首先在調度的各個環節都賦予關鍵路徑節點最高優先級。此外，針對現有表調度算法中依據任務的局部信息定義任務優先級，致使后續的關鍵任務無法優先調度的問題，本文算法提出一種以優先級權值weighti定義任務優先級的方式。優先級權值的選取充分考慮到整個任務圖拓撲結構，定義為任務在當前格局下向后關鍵路徑的執行時間，并按權值降序排序任務優先級。優先級權值weighti的計算方式如式(3)所示:

其中，cp_value(ni)的定義如式(4)所示;ncp表示當前任務節點的直接后繼關鍵路徑節點。

3.3 任務分配

為簡化算法復雜度，選擇任務完成時間最早的處理器內核為目標處理器內核。在此基礎上，IHTSHMP 算法采用任務復制的分配思想和區間插入的分配方式對任務分配階段進行優化。使用多復制的任務復制技術，循環判斷任務是否滿足復制條件。若復制關鍵前驅節點可以提早任務的最早開始時間，則復制其到處理器內核上，更新任務的關鍵前驅節點。判斷不采用任務復制情況下的任務最早完成時間est(ni)和采用任務復制2 種情況下的任務最早完成時間est2(ni)。若est(ni)＞est2(ni)，則復制關鍵前驅節點到處理器內核。est2(ni)的計算方法如式(5)所示。

任務復制過程如圖3 所示。區間插入是指在任務分配時，將任務分配到2 個已調度任務之間的處理器內核空閑時間段上。它是提高處理器利用率的有效手段。特別地，將處理器內核最后一個任務完成且可執行新任務的時間作為一個處理器空閑區間的開始時間，其結束時間為∞。

圖3 任務復制過程

若滿足式(6)，則將任務分配到該空閑時間段上執行。

其中，Spaces和Spacee分別為處理器內核空閑時間段的開始時間和結束時間。

4 性能測試

將本文算法與基于關鍵前驅復制的CPFD(Critical Path Fast Duplication)算法［11］和選擇性任務復制的表調度STDH(Selected Task Duplication for Heterogeneous System)算法［12］在同等條件下進行模擬實驗。為進一步進行性能驗證，本文引入調度長度比率(Schedule Length Ratio，SLR)和加速比speedup 作為算法性能評估參數。

(1)關鍵路徑是DAG 任務圖的最長路徑，是任務調度長度的瓶頸所在。SLR 反映了任務圖相對于關鍵路徑的執行情況。SLR 的計算公式rSLR如式(7)所示。

其中，makespan 表示任務圖的調度長度，即任務映射圖中最后一個任務的完成時間;CP 為各關鍵路徑節點在各處理器內核上平均執行開銷之和。關鍵路徑作為任務圖中最長的一條執行路徑，是整個任務調度長度的瓶頸所在，SLR 越小則證明任務調度算法的性能越好。

(2)加速比speedup 反映的是程序的并行化執行程度。定義為任務的串行執行時間與任務圖實際調度長度的比值，加速比越大則證明算法并行化程度越高，調度性能越好。speedup 的計算方式如式(8)所示。

本文采用隨機任務圖作為測試用例，對算法性能進行驗證。為控制產生任務圖的形狀和大小等屬性，對任務圖的參數取值范圍進行設定。設定任務圖中任務個數N={20，30，40，50，60，70，80，90，100};任務圖中節點的最大出度α={1，2，5，10，100};任務圖中任務的通信時間與執行時間比值參數CCR={0.1，0.5，1.0，5.0，10.0};任務在不同處理器內核上執行時間差異度參數β={0.1，0.5，1，1.5，2}。通過對以上參數的設定，產生1 125 組任務圖類型。從每組類型中隨機地選擇10 個任務圖，此時可以生成11 250 個任務圖。對產生的11 250 個任務圖在模擬平臺上進行調度，評測算法性能。

將IHTSHMP 算法與已有CPFD 算法和STDH 算法分別在不同任務數和不同通信計算比率(Communication Computation Ratio，CCR)的情況下對3 種算法的speedup 和SLR 性能進行對比分析。得到算法在不同任務數情況下的平均speedup 和平均SLR 結果對比圖，分別如圖4 和圖5 所示;不同CCR情況下的平均speedup 和平均SLR 結果對比圖，分別如圖6 和圖7 所示。

圖4 不同任務數下的平均加速比對比

圖5 不同任務數下的平均SLR 對比

圖6 不同CCR 下的平均加速比對比

圖7 不同CCR 下的平均SLR 對比

由圖4 和圖5 所示，在不同任務數的情況下，IHTSHMP 算法始終保持較高的調度性能，與CPFD 算法和STDH 算法相比，IHTSHMP 算法加速比speedup約分別提高17.20%和9.81%，調度下界比SLR 約分別降低15.40%和8.15%。由圖6 和圖7 所示，在不同CCR 下，IHTSHMP 算法性能較為平穩，與CPFD 算法和STDH 算法相比，加速比speedup 約分別提高16.35%和9.08%，調度下界比SLR 約分別降低14.53%和8.10%。由實驗結果對比分析可知，IHTSHMP 算法有效優化任務調度性能。

5 結束語

本文提出一種異構CMP 架構下的啟發式綜合任務調度算法。該算法綜合2 種啟發式算法完成任務調度過程，克服了現有算法中存在的不足，提高調度效率，在優先級權值設定時，充分考慮任務拓撲圖結構，提高了全局調度效率;在任務分配時，采取了對于減少依賴任務通信延遲有效的多任務復制技術和對于提升處理器利用率有效的區間插入方式，進一步優化調度。性能測試結果表明，本文算法能有效減少任務調度長度，充分發揮異構CMP 的優勢。

［1］李靜梅，張 博.基于混合粒子群優化的CMP 線程調度方法［J］.計算機工程，2012，38(20):113-115.

［2］Ullman J D.NP-complete Scheduling Problem ［J］.Journal of Computer and System Sciences，1975，10(3):384-393.

［3］梁洪濤，袁由光，方 明.一種基于任務全局遷移的靜態調度算法［J］.計算機研究與發展，2006，43(5):797-804.

［4］Prashanth C，Ranga S.Algorithms for Task Scheduling in Heterogeneous Computing Environments ［D］.Alabama，USA:Auburn University，2006.

［5］Palmer A，Sinnen O.Scheduling Algorithm Based on Force Directed Clustering ［C］//Proc.of the 9th International Conference on Parallel and Distributed Computing，Applications and Technologies.［S.l.］:IEEE Press，2008:311-318.

［6］邢建生，王永吉，劉軍祥，等.一種靜態最少優先級分配算法［J］.軟件學報，2007，18(7):1844-1854.

［7］Hwang R，Gen M，Katayama H.A Comparison of Multiprocessor Task Scheduling Algorithms with Communication Costs［J］.Computer ＆ Operations Research，2008，35(3):976-993.

［8］林劍檸，吳慧中，陳學勤.基于任務復制的網格任務調度算法［J］.計算機科學，2006，33(6):89-92.

［9］何 琨，趙 勇，黃文奇.基于任務復制的分簇與調度算法［J］.計算機學報，2008，31(5):733-740.

［10］Darbha S，Agrawal D P.Optimal Scheduling Algorithm for Distributed-memory Machines［J］.IEEE Transactions on Parallel and Distributed Systems，1998，9(1):87-95.

［11］Ahmad I，Kwok Y K.On Exploiting Task Duplication in Parallel Program Scheduling［J］.IEEE Transactions on Parallel and Distributed Systems，1998，9(9):872-877.

［12］孟憲福，劉偉偉.基于選擇性復制前驅任務的DAG 調度算法［J］.計算機輔助設計與圖形學報，2010，22(6):1056-1062.