基于異構多核處理器的靜態(tài)任務調(diào)度研究（二）

接上文：

基于異構多核處理器的靜態(tài)任務調(diào)度研究（一）

3 實驗驗證

3.1 性能評價參數(shù)

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

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

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

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

3.2 實驗與結果

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

實驗1:利用隨機任務產(chǎn)生器[10-11],根據(jù)參數(shù)值v（DAG的任務數(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é)點權值的DAG,共產(chǎn)生60000個隨機任務。

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

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

4 驗證方案結構

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

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

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

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

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

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

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

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

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

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

結束語

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