新聞中心

EEPW首頁 > 嵌入式系統(tǒng) > 設計應用 > 基于異構多核處理器的靜態(tài)任務調(diào)度研究(二)

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

作者: 時間:2013-05-08 來源:網(wǎng)絡 收藏

接上文:

本文引用地址:http://m.butianyuan.cn/article/148035.htm

異構多核(一)

3 實驗驗證

3.1 性能評價參數(shù)

中,的開銷比較小,任務調(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不同時較已有算法均能取得更好的性能



評論


相關推薦

技術專區(qū)

關閉