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

接上文：

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

3 實(shí)驗驗證

3.1 性能評價(jià)參數

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

(1)調度長(cháng)度makespan,為所有處理器上的最大任務(wù)調度長(cháng)度。

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

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

3.2 實(shí)驗與結果

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

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

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

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

4 驗證方案結構

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

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

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

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

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

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

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

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

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

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

結束語(yǔ)

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