異構(gòu)多核處理器系統(tǒng)的特點及基于加權(quán)優(yōu)先級的任務(wù)調(diào)度算法分析

引 言

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

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

1 WPTS算法設(shè)計

1.1 3種現(xiàn)有高效算法的分析

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

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

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

本文在總結(jié)并分析上述算法不足的基礎(chǔ)上，設(shè)計出WPTS算法，并給出任務(wù)調(diào)度實驗以驗證新算法的正確性和有效性。

1.2 WPTS算法執(zhí)行過程

WPTS算法的執(zhí)行分為兩個階段：任務(wù)優(yōu)先級計算和任務(wù)到處理器的映射。其中第一階段包括任務(wù)合并、任務(wù)分層和任務(wù)權(quán)值計算3個過程，第二階段包括任務(wù)分配到處理器和任務(wù)調(diào)度結(jié)果優(yōu)化兩個過程，如圖1所示。

圖1 WPTS算法執(zhí)行過程

1.3 WPTS算法實現(xiàn)原理

1.3.1 任務(wù)優(yōu)先級計算階段

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

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

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

任務(wù)優(yōu)先級計算流程如圖2所示。

圖２任務(wù)優(yōu)先級計算階段流程

任務(wù)優(yōu)先級計算階段完成后，所有的任務(wù)已經(jīng)按照優(yōu)先級從高到低的次序加入到調(diào)度列表中，可以繼續(xù)執(zhí)行任務(wù)到處理器映射階段的步驟。

1.3.2 任務(wù)到處理器映射階段

（1）任務(wù)到處理器映射階段的設(shè)計思想

任務(wù)到處理器映射階段包括任務(wù)映射到處理器和處理圖2 任務(wù)優(yōu)先級計算階段流程器上的冗余任務(wù)處理。

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

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

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

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

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

步驟1 初始化level=0,判斷任務(wù)調(diào)度列表TL在level層的任務(wù)是否調(diào)度完畢，如果是則跳轉(zhuǎn)到步驟5;否則向下執(zhí)行步驟2.

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

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

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

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

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

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

步驟8 如果level

2 WPTS算法時間復(fù)雜度分析

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

圖３任務(wù)到處理器映射階段流程

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

3 實驗驗證

3.1 性能評價參數(shù)

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

（1）調(diào)度長度makespan,為所有處理器上的最大任務(wù)調(diào)度長度。

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

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

3.2 實驗與結(jié)果

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

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

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

將WPTS算法與CPFD算法、HCPFD算法、HDEFT算法進行比較，統(tǒng)計WPTS算法較其它3種算法取得Bet- ter、Equal和Worse調(diào)度性能的次數(shù)和所占的比例，比較結(jié)果見表1.

4 驗證方案結(jié)構(gòu)

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

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

5 形狀參數(shù)α變化時算法的平均SLR

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

6 形狀參數(shù)α變化時算法的Efficiency

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

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

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

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

根據(jù)這兩組測試結(jié)果，可以看出WPTS算法要優(yōu)于CPFD、HCPFD和HDEFT 算法，隨著任務(wù)規(guī)模的增大，WPTS算法的優(yōu)勢越明顯。

結(jié)束語

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