李云洋, ,

(1.南京理工大學(xué) 自動(dòng)化學(xué)院,南京 210094; 2.中航工業(yè)西安飛行自動(dòng)控制研究所,西安 710065)

0 概述

隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展和在實(shí)際工程系統(tǒng)中的廣泛應(yīng)用,越來越多不同處理能力的單個(gè)處理器通過網(wǎng)絡(luò)互聯(lián)而組成了異構(gòu)分布式計(jì)算環(huán)境,如網(wǎng)絡(luò)化嵌入式系統(tǒng)[1]。在處理大規(guī)模任務(wù)時(shí),分布式計(jì)算系統(tǒng)通常將任務(wù)分解為若干相互依賴的子任務(wù)并進(jìn)行處理,而任務(wù)調(diào)度是實(shí)現(xiàn)高效異構(gòu)分布式計(jì)算的關(guān)鍵技術(shù)。由于大規(guī)模復(fù)雜多約束任務(wù)調(diào)度問題是NP-hard問題[2],往往難以獲得最優(yōu)解,尤其在分布式異構(gòu)計(jì)算環(huán)境中,由于各任務(wù)在異構(gòu)處理器上執(zhí)行特性不同,對(duì)復(fù)雜任務(wù)調(diào)度問題提出了挑戰(zhàn),因此研究并設(shè)計(jì)低復(fù)雜度、高性能的任務(wù)調(diào)度算法具有重要的理論意義和工程應(yīng)用前景。

靜態(tài)任務(wù)調(diào)度算法主要包括基于啟發(fā)式和基于隨機(jī)搜索的算法,其中啟發(fā)式調(diào)度主要有表調(diào)度算法、基于分簇的調(diào)度算法和基于復(fù)制的調(diào)度算法[3-4]。表調(diào)度由于簡(jiǎn)單易行,并且具有較高的調(diào)度效率和較低的時(shí)間復(fù)雜度,因此受到廣泛關(guān)注,其主要代表性算法有DLS[5]、HEFT[6]、CPOP[6]等。文獻(xiàn)[6]提出2種低復(fù)雜度的表調(diào)度算法HEFT和CPOP,但HEFT算法在處理器分配階段僅根據(jù)本任務(wù)完成時(shí)間最短的策略分配處理器,而未考慮對(duì)后繼任務(wù)完成時(shí)間的影響。文獻(xiàn)[7-8]提出2種基于復(fù)制策略的調(diào)度算法,減少了任務(wù)完成時(shí)間,但算法執(zhí)行時(shí)間復(fù)雜度較高且容易造成處理器資源浪費(fèi)。文獻(xiàn)[9-10]分別提出2種基于分簇策略的調(diào)度算法,基于分簇的算法能夠有效利用處理器資源而提高任務(wù)并行計(jì)算執(zhí)行效率,但在減少通信開銷上不如基于任務(wù)復(fù)制的算法,并且時(shí)間復(fù)雜度也高于表調(diào)度算法。在處理多任務(wù)調(diào)度問題時(shí),隨機(jī)搜索算法及應(yīng)用也得到研究。文獻(xiàn)[11-13]提出3種基于遺傳算法的任務(wù)調(diào)度算法,文獻(xiàn)[14]提出基于模擬退火的調(diào)度算法。此外,文獻(xiàn)[15-16]還提出基于禁忌搜索的調(diào)度算法。遺傳算法由于能夠縮短任務(wù)完成時(shí)間而應(yīng)用廣泛,但其程序運(yùn)行時(shí)間遠(yuǎn)比啟發(fā)式調(diào)度算法時(shí)間長(zhǎng),因此,對(duì)實(shí)時(shí)性要求高的系統(tǒng)僅適用于離線靜態(tài)調(diào)度場(chǎng)合。

HEFT表調(diào)度算法未考慮其直接后驅(qū)任務(wù)完成時(shí)間的影響。針對(duì)該不足,本文提出一種新型表調(diào)度算法IFEFT。通過計(jì)算任務(wù)最早完成時(shí)間,以及該任務(wù)與出口任務(wù)之間的最大通信開銷,并采用兩者乘積越小越優(yōu)先的策略,進(jìn)行處理器任務(wù)分配。

1 問題描述

用戶請(qǐng)求應(yīng)用可分解為若干相互依賴的任務(wù),通過有向無環(huán)圖(Direct Acyclic Graph,DAG)描述。一般DAG圖由二元組G=(V,E)表示,其中,V表示DAG圖的節(jié)點(diǎn)集合,即任務(wù)集合V={v1,v2,…,vn},n=|V|表示任務(wù)總數(shù),E是DAG圖有向邊,每個(gè)邊連接2個(gè)任務(wù),E={ei,j|ei,j=〈vi,vj〉,ei,j∈V×V},如果ei,j∈E,表示任務(wù)vi和vj之間有依賴關(guān)系,vj必須在vi完成后才能開始處理。圖1為一個(gè)表示任務(wù)節(jié)點(diǎn)以及邊權(quán)重的標(biāo)準(zhǔn)DAG圖。

圖1 DAG圖

若異構(gòu)計(jì)算環(huán)境下處理器之間通過同構(gòu)網(wǎng)絡(luò)互聯(lián),即任意2個(gè)處理器之間的通信速率相同,則DAG圖中每條邊對(duì)應(yīng)一個(gè)通信開銷,用ci,j描述任務(wù)vi和任務(wù)vj在不同處理器上處理所需要的通信開銷,C={ci,j|ei,j∈E,ci,j>0}表示整個(gè)DAG圖的通信開銷集合。設(shè)異構(gòu)處理器集合為P={p1,p2,…,pm},m=|P|為處理器總數(shù),用wi,j表示任務(wù)vi在處理器pj上的計(jì)算開銷(時(shí)間),那么W=[wi,j]n×m即是任務(wù)集合在處理器上計(jì)算開銷矩陣。表1列出了圖1中10個(gè)任務(wù)在處理器p1～p3上的計(jì)算開銷。

表1 圖1中10個(gè)任務(wù)在3個(gè)處理器上的計(jì)算開銷

定義任務(wù)vi的前驅(qū)和后繼任務(wù)集合分別為:

Vpred(vi)={vj|vj∈V,ej,i∈E}

(1)

Vsucc(vi)={vj|vj∈V,ei,j∈E}

(2)

令入口任務(wù)為ventry,出口任務(wù)為vexit,那么Vpred(ventry)=0,Vsucc(vexit)=0。令TEST(vi,pj)和TEFT(vi,pj)分別表示任務(wù)vi在處理器pj的最早執(zhí)行開始時(shí)間和最早執(zhí)行完成時(shí)間,則對(duì)于入口任務(wù)ventry,有:

TEST(ventry,pj)=0

(3)

對(duì)于DAG圖中的其他任務(wù),從入口任務(wù)開始,采用遞歸的方法分別計(jì)算最早執(zhí)行開始時(shí)間(Earliest Start Time,EST)和最早執(zhí)行完成時(shí)間(Earliest Finish Time,EFT)。為計(jì)算任務(wù)vi的最早執(zhí)行完成時(shí)間,其所有的直接前驅(qū)任務(wù)都應(yīng)已被調(diào)度成功。最早執(zhí)行開始時(shí)間和最早執(zhí)行完成時(shí)間的計(jì)算公式如下:

TEST(vi,pj)=

(4)

TEFT(vi,pj)=wi,j+TEST(vi,pj)

(5)

其中,Tavail[j]表示處理器pj準(zhǔn)備好執(zhí)行任務(wù)的最早時(shí)間。

當(dāng)任務(wù)vi調(diào)度到處理器pj后,其在處理器pj上的最早完成執(zhí)行時(shí)間就等于實(shí)際完成時(shí)間TAFT(vi)。而當(dāng)DAG圖中全部任務(wù)都被調(diào)度執(zhí)行后,整個(gè)應(yīng)用的執(zhí)行時(shí)間就是出口任務(wù)vexit的實(shí)際完成時(shí)間,即:

Tmakespan=max{TAFT(vexit)}

(6)

2 IFEFT調(diào)度算法

本文提出的IFEFT表調(diào)度算法包括2個(gè)階段:任務(wù)優(yōu)先級(jí)排序和處理器分配。

2.1 任務(wù)優(yōu)先級(jí)排序

IFEFT算法首先建立任務(wù)的優(yōu)先級(jí)隊(duì)列,然后根據(jù)隊(duì)列順序?qū)θ蝿?wù)逐個(gè)進(jìn)行調(diào)度,在任務(wù)優(yōu)先級(jí)排序階段,令wDLC(vi)表示任務(wù)vi與其直接前驅(qū)任務(wù)vm之間的最大通信開銷,wULC(vi)表示任務(wù)vi與其直接后驅(qū)任務(wù)vn之間的最大通信開銷,wLC(vi,pj)表示vi與vm和vn之間的最大通信開銷以及vi在pj上的計(jì)算開銷三者之間和的最大值,wALC(vi)表示任務(wù)vi在不同處理器上計(jì)算的wLC(vi,pj)的平均值。分別定義如下:

wDLC(vi)=max{ci,m}

(7)

wULC(vi)=max{ci,n}

(8)

wULC(vi)+wi,j}

(9)

每個(gè)任務(wù)在不同處理器上計(jì)算開銷不同,因此,為了更精確,每個(gè)任務(wù)在不同處理器上都應(yīng)該有一個(gè)wLC值。首先通過式(9)計(jì)算在不同處理器上執(zhí)行的上行權(quán)重,然后根據(jù)式(10)求其平均值,最后對(duì)權(quán)重、優(yōu)先級(jí)由高降低進(jìn)行排序。根據(jù)式(9)和式(10)計(jì)算公式可得:任何一個(gè)前驅(qū)任務(wù)的上行權(quán)重必大于其所有后繼任務(wù)的上行權(quán)重,從而保證任務(wù)之間的約束關(guān)系。IFEFT算法描述如下:

1.計(jì)算隊(duì)列中每個(gè)任務(wù)的開銷LC(vi, pi)和平均開銷ALC(vi),并將任務(wù)按ALC(vi)降序排列;

2.While 隊(duì)列中有任務(wù)未被調(diào)度do

3.選擇ALC(vi)最大的任務(wù)vr;

4.計(jì)算最短完成時(shí)間EFT(vr, pj)與通信開銷LD(vr, pj);

5.分派vr到EFT(vr, pj)與LD(vr, pj)乘積最小的處理器上;

6.標(biāo)記vr為被調(diào)度任務(wù);

7.End while

2.2 處理器選擇

當(dāng)任務(wù)調(diào)度的優(yōu)先級(jí)隊(duì)列順序確定后,由式(4)和式(5)計(jì)算任務(wù)在每個(gè)處理器上的最早開始時(shí)間和完成時(shí)間。目前已有很多算法在處理器分配階段都是根據(jù)EFT大小來選擇處理器的,只考慮了直接前驅(qū)任務(wù)和本身任務(wù)完成時(shí)間,而未考慮其對(duì)直接后驅(qū)任務(wù)完成時(shí)間的影響。一個(gè)任務(wù)如果其EFT值小但鏈路距離(Link Distance,LD)很大,并不能取得很好的調(diào)度效果,因?yàn)镈AG圖的拓?fù)浣Y(jié)構(gòu)及通信開銷也會(huì)影響任務(wù)完成時(shí)間。為了獲得更好的調(diào)度效果,本文提出兼顧直接前驅(qū)任務(wù)和直接后驅(qū)任務(wù)對(duì)其完成時(shí)間長(zhǎng)短影響的設(shè)計(jì)思想。在處理器分配階段,令wLD表示任務(wù)vi與出口任務(wù)之間最大通信開銷,IEFT作為處理器選擇標(biāo)準(zhǔn),結(jié)合“向上看”和“向下看”的原則,即采用最早完成時(shí)間EFT和最大通信開銷LD乘積最小的原則,定義:

wLD(vi,pj)={wLC(vi,pj)-wi,j}

(11)

IEFT(vi,pj)=min{TEFT(vi,pj)×wLD(vi,pj)}

(12)

采用本文IFEFT算法對(duì)圖1和表1所示的任務(wù)調(diào)度模型進(jìn)行調(diào)度,并與HEFT、DLS、CPOP算法進(jìn)行比較,如圖2所示?？梢钥闯?本文IFEFT算法的任務(wù)完成時(shí)間最短。

圖2 4種表調(diào)度算法結(jié)果的甘特圖

3 實(shí)驗(yàn)與結(jié)果分析

3.1 參數(shù)及比較指標(biāo)

本文利用4種算法在相同的DAG圖上產(chǎn)生的調(diào)度結(jié)果進(jìn)行分析和比較,描述DAG圖的參數(shù)有任務(wù)節(jié)點(diǎn)個(gè)數(shù)n、處理器個(gè)數(shù)m、任務(wù)在處理器上的平均計(jì)算花費(fèi)wACC和通信計(jì)算比RCCR,即平均通信時(shí)間和平均計(jì)算時(shí)間之比。

調(diào)度算法采用調(diào)度長(zhǎng)度比(Scheduling Length Ratio,SLR)和加速比作為評(píng)價(jià)指標(biāo)。SLR表示算法實(shí)際執(zhí)行時(shí)間與關(guān)鍵路徑任務(wù)執(zhí)行時(shí)間的最小值之比,調(diào)度算法產(chǎn)生的SLR越小,說明算法越高效。SLR的計(jì)算公式為:

其中,CPmin表示所有待處理的任務(wù)在處理器上執(zhí)行時(shí)間最短的集合。加速比表示在一個(gè)處理器上串行執(zhí)行DAG圖時(shí)所有任務(wù)使用的最小時(shí)間與其實(shí)際執(zhí)行時(shí)間的比值,調(diào)度算法產(chǎn)生的加速比越大,說明算法越高效。加速比計(jì)算公式為:

3.2 隨機(jī)任務(wù)實(shí)驗(yàn)與結(jié)果對(duì)比

本文通過3組不同的實(shí)驗(yàn)對(duì)比IFEFT、HEFT、DLS、CPOP 4種算法的性能。

實(shí)驗(yàn)1設(shè)置n=20,m={2,4,6,8,16,32},wACC=40,RCCR=0.8,shape={0.4,0.5,0.6,0.7}進(jìn)行100次實(shí)驗(yàn),即隨機(jī)生成100個(gè)DAG圖測(cè)試不同處理器個(gè)數(shù)對(duì)算法性能的影響,得到的平均SLR和平均加速比如圖3所示。實(shí)驗(yàn)數(shù)據(jù)顯示,IFEFT的平均SLR分別比HEFT、DLS和CPOP算法小5.32%、15.23%和13.30%,平均加速比分別比HEFT、DLS和CPOP算法大3.04%、5.83%和4.79%,表明IFEFT算法的平均SLR和平均加速度2項(xiàng)性能指標(biāo)都優(yōu)于其他3種算法。

圖3 處理器個(gè)數(shù)對(duì)各算法性能的影響

實(shí)驗(yàn)2設(shè)置n=20,m=8,wCCR={0.2,0.4,0.8,1,2,4,6},shape={0.4,0.5,0.6,0.7},wACC=40,進(jìn)行100次實(shí)驗(yàn),即隨機(jī)生成100個(gè)DAG圖測(cè)試不同通信計(jì)算比,即通信時(shí)間與計(jì)算時(shí)間之比對(duì)算法性能的影響,獲得的平均SLR和平均加速比如圖4所示。實(shí)驗(yàn)結(jié)果顯示,IFEFT算法獲得的平均SLR分別比HEFT、DLS和CPOP算法小5.91%、12.34%和9.57%,平均加速比分別比HEFT、DLS和CPOP算法大0.96%、5.83%和3.16%,表明IFEFT算法的平均SLR和平均加速比2項(xiàng)性能指標(biāo)均優(yōu)于其他3種算法。

圖4 通信計(jì)算比對(duì)各算法性能的影響

實(shí)驗(yàn)3設(shè)置n={10,20,30,40,50},m=8,RCCR=0.8,shape={0.4,0.5,0.6,0.7},wACC=40,進(jìn)行100次實(shí)驗(yàn),即隨機(jī)生成100個(gè)DAG圖測(cè)試任務(wù)個(gè)數(shù)對(duì)算法性能的影響,獲得的平均SLR和平均加速比如圖5所示。實(shí)驗(yàn)數(shù)據(jù)顯示,IFEFT的平均SLR分別比HEFT、DLS和CPOP算法小7.03%、11.26%和9.66%,平均加速比分別比HEFT、DLS和CPOP算法大1.73%、7.11%和5.59%,表明IFEFT的平均SLR和平均加速比2項(xiàng)性能指標(biāo)都優(yōu)于其他3種算法。

圖5 任務(wù)個(gè)數(shù)對(duì)各算法性能的影響

4 結(jié)束語

本文提出一種新型表調(diào)度算法IFEFT。在處理器分配階段,該算法兼顧了任務(wù)對(duì)其直接前驅(qū)任務(wù)和直接后驅(qū)任務(wù)完成時(shí)間的影響。實(shí)驗(yàn)結(jié)果表明,與DLS、HEFT和CPOP算法相比,IFEFT算法可有效縮短任務(wù)完成時(shí)間,提高平均加速比。下一步將研究異構(gòu)分布式計(jì)算環(huán)境下的任務(wù)動(dòng)態(tài)調(diào)度策略,以及非理想異構(gòu)分布式環(huán)境下兼顧計(jì)算效率與整體可靠性的調(diào)度算法。