引 言

異構多核處理器以其芯片面積利用率高、處理器功耗低、應用程序的并行化程度高等諸多優勢成為處理器體系結構發展的一個重要方向，同時它的出現給計算機學科發展帶來了新的挑戰。研究發現多核處理器任務調度的優劣對處理器的執行時間、任務調度長度、處理器的功耗等諸多性能產生直接影響。因此，多核處理器的任務調度作為影響操作系統性能的重要因素成為近年來系統結構方向的熱點研究問題之一。當前對異構多核處理器上任務調度的研究很少考慮任務優先級的選取對調度結果的影響以及使用復制技術的任務調度算法會產生冗余任務的問題。

本文深入分析了CPFD、HCPFD和HDEFT這3種最具有代表性的任務調度算法，并在總結目前任務調度算法存在的缺點基礎上，根據異構多核處理器系統結構的特點，設計了基于加權優先級的任務調度算法（weighted prioritytask scheduling,WPTS），算法以3個參數構成的加權值作為任務的優先級，將任務排序構成任務調度列表，然后依次將任務映射到處理器上，并在映射過程中對任務進行優化處理，最后通過預先設定的性能評價參數對算法進行實驗驗證。本研究能有效改善原有任務調度算法的不足，提升了多核處理器在實際應用中的性能，對異構多核處理器上靜態任務調度技術的發展具有重大理論和現實意義。

1 WPTS算法設計

1.1 3種現有高效算法的分析

目前基于異構多核處理器取得較好調度性能的算法有CPFD算法、HCPFD算法和HDEFT算法。CPFD算法使用任務節點到入口節點的最長路徑b-level作為任務調度的優先級，將任務調度到具有最早完成時間的處理器上，其時間復雜度是O （v4），v是DAG圖中任務節點的數目。

HCPFD算法以關鍵任務和任務的最晚開始時間劃分任務的優先級，將任務分配到使其完成時間最早的處理器節點上，在任務到處理器的映射階段優先考慮使用處理器上的空閑時間段來處理任務，其時間復雜度為O （pv2），p是任務調度中處理器的總個數。HDEFT算法在任務分配階段采用sumu （vi）作為任務優先級，在任務到處理器的映射階段使用任務插入和復制技術，其時間復雜度為O （pv2）。

CPFD算法和HCPFD算法的調度性能不夠理想，原因在于算法只選擇唯一任務屬性作為任務的優先級，沒有考慮任務間的約束關系和通信開銷等影響調度性能的重要因素。HDEFT算法時間復雜度不高，但沒有對使用任務復制技術后存在的冗余任務進行處理，冗余任務延長了總的任務調度完成時間，浪費了處理器資源。

本文在總結并分析上述算法不足的基礎上，設計出WPTS算法，并給出任務調度實驗以驗證新算法的正確性和有效性。

1.2 WPTS算法執行過程

WPTS算法的執行分為兩個階段：任務優先級計算和任務到處理器的映射。其中第一階段包括任務合并、任務分層和任務權值計算3個過程，第二階段包括任務分配到處理器和任務調度結果優化兩個過程，如圖1所示。

圖1 WPTS算法執行過程

1.3 WPTS算法實現原理

1.3.1 任務優先級計算階段

(1)任務優先級計算階段的設計思想任務合并是將任務中較獨立、任務間通信開銷較大的任務進行合并優化。對DAG圖進行深度優先搜索,當任務vi只有一個直接后繼節點vj、任務vj只有一個直接前驅節點vi,且c (vi,vj)≥wj,k,即任務vi、vj間的通信開銷大于任務vj在所有處理器上的平均執行開銷,則合并任務vi、vj,并記為vi*,vi*的計算開銷為vi、vj計算開銷的總和,在隨后的調度中任務vi*被作為整體處理。

任務分層是為方便后續任務權值的計算。用level標記任務在DAG圖中的層數,設置入口節點任務level=0,從上到下遍歷任務DAG圖,計算任務節點到入口節點的最大通信邊數目,以此作為任務的level值。非入口節點任務vi的level值為其所有前驅節點的最大level值加1,計算公式如下所示level(vi)=Max (level(vj))+1,vj∈pred (vi)(1)在任務權值計算過程中,WPTS算法綜合考慮任務各屬性對任務優先級排序的影響,選擇使用平均計算開銷和通信開銷作為任務的優先級參數。平均計算開銷ACC是任務在所有處理器上計算開銷的平均值,計算公式如式(2)所示。通信開銷包括平均數據傳輸開銷ADTC和平均數據接收開銷ADRC,計算公式如式(3)和式(4)所示,式中x為vi直接后繼節點數量,y為vi直接前驅節點數量

定義weight (vi)為任務vi的權值,它是任務的ADTC、ADRC、ACC之和,對每個處在level=i層的任務來說weight(vi)的計算公式如公式下所示weight(vi)=ADTC (vi)+ADRC (vi)+ACC (vi)(5)(2)任務優先級計算階段流程

任務優先級計算流程如圖2所示。

圖２任務優先級計算階段流程

任務優先級計算階段完成后，所有的任務已經按照優先級從高到低的次序加入到調度列表中，可以繼續執行任務到處理器映射階段的步驟。

1.3.2 任務到處理器映射階段

（1）任務到處理器映射階段的設計思想

任務到處理器映射階段包括任務映射到處理器和處理圖2 任務優先級計算階段流程器上的冗余任務處理。

在任務映射到處理器的過程中，遍歷所有處理器，直接將任務vi分配到具有最早完成時間的處理器上，其完成時間記為EFT1;將vi分配具有空閑時間段的處理器上且不使用任務復制技術的最早完成時間為EFT2;記使用復制任務技術復制任務vi的直接前驅節點到vi所處的處理器空閑時間段上最早完成時間為EFT3.比較三者的值，將任務vi分配到具有最小完成時間的處理器上。EFT1、EFT2、EFT3的計算公式如下

式中：AST （vi,pn）-任務vi在處理器pn上的實際開始時間；AFT （vi,pk）-任務vi在處理器pk上的實際完成時間；vpar-最后一個與任務vi通信的任務；Avail（pn）-處理器pn執行完分配到其上的所有任務的時間。

通過對DAG圖的深入研究發現，某層冗余任務的處理在其下一層任務到處理器的映射之后執行效果最好，如對level=1層任務調度完成后對level=0層任務進行冗余判斷，將任務分配到處理器和冗余任務處理兩個過程交替執行，直到冗余任務列表為空。

（2）任務到處理器映射流程任務到處理器映射流程如圖3所示。

（3）任務到處理器映射階段具體步驟

步驟1 初始化level=0,判斷任務調度列表TL在level層的任務是否調度完畢，如果是則跳轉到步驟5;否則向下執行步驟2.

步驟2 取任務調度列表TL的首任務記為vi,遍歷所有處理器，如果處理器存在空閑時間段且滿足vi插入條件，則將vi分配到空閑時間段，并計算其最小最早完成時間，記為EFT1;否則向下執行步驟3.

步驟3 計算將vi分配到所有處理器上的最小最早完成時間，記為EFT2.如果處理器上存在空閑時間段且能使用任務復制技術，則計算在處理器上復制vi的前驅獲得最小最早完成時間，記為EFT3,繼續執行步驟4.

步驟4 選擇EFT1、EFT2、EFT3的最小值，并將任務分配到具有最早完成時間的處理器上，從調度列表中刪除vi,建立冗余任務列表RTL,將被復制的任務加入到RTL中，格式為vi,0~vi,k,vi為被復制的任務節點，k為任務所在處理器的編號。

步驟5 判斷RTL中是否有（level-1）層任務，如果是則跳轉到步驟6;否則跳轉到步驟8.

步驟6 取RTL首任務節點，記為vi,k,判斷刪除任務vi,k后vi,k直接后繼節點的最早開始時間是否延遲，如果延遲，判定任務vi,k非冗余任務，從RTL中刪除vi,k,跳轉到步驟5;否則判定任務vi,k為冗余節點，從RTL中刪除vi,k,從任務映射圖中刪除vi,k,跳轉到步驟7繼續執行。

步驟7 判斷任務vi,k的后繼任務能否提前執行，如果能則將其前移執行，修改任務映射圖，跳轉到步驟5;否則，直接跳轉到步驟5.

步驟8 如果level

2 WPTS算法時間復雜度分析

任務合并過程是對DAG圖進行一次深度優先遍歷，因此其時間復雜度為O （v+e），v為DAG圖中任務的數量，e為有向邊的數目。任務分層是從上到下計算每個節點的level值，時間復雜度為O （n+e），n為任務合并后DAG圖中任務的數量。任務權值計算對DAG圖進行廣度優先遍圖3 任務到處理器映射階段流程歷，計算任務節點的weight值和尋找關鍵路徑節點，時間復雜度為O （n2），因此任務優先級計算階段的時間復雜度為O （v+e）+O （n+e）+O （n2）；任務到處理器的映射階段考慮了處理器空閑時間段插入和任務復制技術，因此每層任務被映射到處理器上的時間復雜度為O （kp），k為每層的任務數量，p為處理器的數量，冗余任務處理的時間復雜度為O （k2），將所有任務映射到處理器上并完成調度結果優化所需的時間復雜度為O （kpm+k2 m），m 為任務DAG圖的層數，其在最壞情況下等于任務數量v.

圖３任務到處理器映射階段流程

綜上所述，WPTS算法的時間復雜度為O （v+e）+O（n+e）+O （n2）+O （kpm+k2 m），即O （v3），算法沒有提高時間復雜度，且能有效處理使用任務復制技術帶來的冗余任務，減少任務的調度長度，避免處理器資源的浪費。

3 實驗驗證

3.1 性能評價參數

在靜態任務調度中，任務調度的開銷比較小，任務調度的總長度成為評價一個任務調度算法的性能標準，除此之外還有任務調度長度比率、算法的效率等，具體的評定標準和公式如下：

（1）調度長度makespan,為所有處理器上的最大任務調度長度。

（2）調度長度比率SLR,計算公式如式（9）所示，分母為所有關鍵路徑任務執行時間的最小值之和。SLR的值總是大于等于1的，且值越小，任務調度算法性能越好。

（3）算法效率Efficiency,計算公式如式（10）所示，分子為任務調度的加速比，計算公式如式（11）所示，分母為任務調度中處理器的數量，Efficiency值越大表明任務調度算法的性能越好

3.2 實驗與結果

實驗將任務調度性能測試分成兩組，通過仿真實驗檢驗WPTS算法在不同任務中的性能。

實驗1:利用隨機任務產生器[10-11],根據參數值v（DAG的任務數量，取值為{30,40,50,60,70,80,90,100}）、α （DAG 的形狀參數，取值為{0.5,1.0,2.0}、β （節點的出度，取值為{1,2,3,4,5}）、γ （節點的入度，取值為{1,2,3,4,5}）、CCR （通信計算時間比，取值為{0.1,0.5,1.0,5.0,10.0}）產生3000組DAG類型，每組類型中隨機產生20個具有不同節點權值的DAG,共產生60000個隨機任務。

將隨機任務以參數形式輸入算法中，通過Socket將算法運行結果傳遞到仿真實驗環境中。仿真實驗使用Simics模擬多核異構處理器結構，通過C語言實現算法和Socket通信模塊，實現虛擬多核環境和算法之間的有效信息交互，通過對任務的完成時間長短判斷算法優劣（依次比較兩種算法，完成時間差在線性級之內的標記為Equal,其它情況下，算法1較算法2完成時間短時標記為Better,完成時間長時標記為Worse），實驗方案結構如4所示。

將WPTS算法與CPFD算法、HCPFD算法、HDEFT算法進行比較，統計WPTS算法較其它3種算法取得Bet- ter、Equal和Worse調度性能的次數和所占的比例，比較結果見表1.

4 驗證方案結構

從表1可以看出在隨機實驗環境下，在將3種算法綜合的情況下，WPTS 算法能取得最優調度的比例為71.53%,優于其它3種算法。

實驗2:（1）令α= {0.5,1.0,2.0},改變隨機任務的其它參數，計算各算法的平均SLR和Efficiency,計算公式如式（9）、式（10），實驗結果如5、6所示。

5 形狀參數α變化時算法的平均SLR

從對比可以看出，任務形狀參數α變化會影響任務調度的結果：α值為0.5時，DAG高度較小，任務之間并行性較高；α值為1.5時，DAG高度較大，任務之間并行性較低。4種算法在任務并行性較高時都能取得很好的性能，其中WPTS算法的性能最優，原因是任務并行性較高時，處理器上的空閑時間較少，處理器的利用率較高，而WPTS算法能及時處理任務調度中存在的冗余任務，提高處理器的執行效率。

6 形狀參數α變化時算法的Efficiency

（2）改變處理器數量，使其分別為4、8、12、16、20,其它參數不變，各算法的性能如7、8所示。

從對比可以看出，與其它任務調度算法相比，WPTS算法更具有性能優勢，其原因在于新算法充分利用處理器上的空閑時間調度任務，并及時對產生的冗余任務進行處理，提前后繼任務的最早開始時間，因此取得了更好的調度性能。

（3）CCR取值分別為0.1,0.5,1.0,5.0,10.0,其它參數值不變，各算法的性能測試結果如9、10所示。

從對比可以看出，CCR不同時，因為WPTS算法對冗余任務有較好的處理，因此較其它3種算法取得了更好的性能。

根據這兩組測試結果，可以看出WPTS算法要優于CPFD、HCPFD和HDEFT 算法，隨著任務規模的增大，WPTS算法的優勢越明顯。

結束語

通過深入分析目前異構多核處理器任務調度算法存在的不足，提出了WPTS 算法。WPTS 算法使用加權值weight標記任務的優先級，新優先級計算方法克服了優先級選取單一帶來的問題，能更準確地反映任務在DAG中的位置和屬性；在任務到處理器的映射階段及時消除任務調度中產生的冗余任務，提前后續任務的最早開始執行時間。實驗結果表明，新算法能取得最優調度的比例為71.53%,且在DAG形狀、處理器數量和CCR不同時較已有算法均能取得更好的性能