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

接上文：

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

3 實(shí)驗(yàn)驗(yàn)證

3.1 性能評(píng)價(jià)參數(shù)

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

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

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

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

3.2 實(shí)驗(yàn)與結(jié)果

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

實(shí)驗(yàn)1:利用隨機(jī)任務(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é)點(diǎn)的出度，取值為{1,2,3,4,5})、γ (節(jié)點(diǎn)的入度，取值為{1,2,3,4,5})、CCR (通信計(jì)算時(shí)間比，取值為{0.1,0.5,1.0,5.0,10.0})產(chǎn)生3000組DAG類型，每組類型中隨機(jī)產(chǎn)生20個(gè)具有不同節(jié)點(diǎn)權(quán)值的DAG,共產(chǎn)生60000個(gè)隨機(jī)任務(wù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

結(jié)束語(yǔ)

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