基于異構多核處理器的靜態任務調度研究（一）

摘 要：針對現存任務調度算法優先級選取過于單一、冗余任務處理較晚的問題，提出一種基于加權優先級的任務調度算法-WPTS算法。該算法綜合考慮任務3個屬性的加權值以決定任務被處理的先后次序，從而克服了任務選取時的單一性問題。在將任務分配到處理器的過程中，保證任務優先調度到完成時間最早的處理器上。同時，引入冗余任務處理過程，及時消除冗余任務，達到對處理器空閑時間段進行有效回收、減少處理器調度長度的效果。性能對比實驗表明，WPTS算法較CPFD算法、HCPFD算法和HDEFT算法能取得更好的性能。

0 引 言

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

本文深入分析了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所示。

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

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

1.3.2 任務到處理器映射階段

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

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

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