王月恒, 倪 偉, 汪 敏

(合肥工業(yè)大學(xué) 微電子學(xué)院,安徽 合肥 230601)

由于具有高性能、低功耗、易擴(kuò)展等優(yōu)點(diǎn),多核處理器自問世后,迅速成為當(dāng)前主流的處理器架構(gòu)[1]。

對于多核處理器,合理的任務(wù)調(diào)度策略是提高任務(wù)并行度、減少任務(wù)執(zhí)行時間的關(guān)鍵因素之一。此外,異構(gòu)多核處理器中的各處理器核在功能和性能上大多存在差異,因此與同構(gòu)多核處理器相比,任務(wù)調(diào)度問題更為復(fù)雜,在多項式時間內(nèi)無法得到最優(yōu)解,屬于NP完全(non-deterministic polynomial complete,NPC)問題。

為了在合理的時間內(nèi)得到多核處理器并行任務(wù)調(diào)度問題的近似最優(yōu)解,學(xué)術(shù)界針對該問題進(jìn)行了廣泛的研究,提出了多種啟發(fā)式調(diào)度算法。根據(jù)算法的特征,可將這些算法分為基于列表的調(diào)度算法(HEFT[2]、PEFT[3]、lookahead[4])、智能搜索算法(GA[5],PSO[6],TS[7]、AS[8])以及基于任務(wù)復(fù)制的調(diào)度算法(TDS[9]、MJD[10]、WPTS[11]、TANH[12]、TDCA[13])。其中,基于任務(wù)復(fù)制的調(diào)度算法主要思想是以子任務(wù)的冗余計算為代價,減少不同處理器核上的任務(wù)間通訊消耗,進(jìn)而獲得更短的調(diào)度長度(makespan)。當(dāng)選用合理的復(fù)制策略時,任務(wù)復(fù)制算法能獲得比其他算法較優(yōu)的調(diào)度結(jié)果[14]。

TDS算法[9]是經(jīng)典的基于任務(wù)復(fù)制的同構(gòu)多核任務(wù)調(diào)度算法,采用了基于聚簇與任務(wù)復(fù)制的策略,其主要思想是將有向無環(huán)圖(directed acyclic graph,DAG)中join節(jié)點(diǎn)與其關(guān)鍵前驅(qū)任務(wù)分配到同一處理器,以降低并行執(zhí)行時間。但TDS算法只適用于同構(gòu)多核系統(tǒng),且在內(nèi)核數(shù)量不限的情況下,TDS算法不允許join節(jié)點(diǎn)的任何2個前驅(qū)節(jié)點(diǎn)調(diào)度到同一個處理器,影響算法調(diào)度效果。

文獻(xiàn)[13]提出了一種基于任務(wù)復(fù)制的聚簇算法——TDCA算法。該算法在TANH算法的基礎(chǔ)上進(jìn)行了改進(jìn)。TDCA算法針對異構(gòu)系統(tǒng)引入了一種新的參數(shù)計算方法,并根據(jù)參數(shù)對任務(wù)節(jié)點(diǎn)進(jìn)行分簇,生成初始任務(wù)集群;隨后根據(jù)任務(wù)復(fù)制算法的鏈?zhǔn)椒磻?yīng),采用關(guān)鍵前驅(qū)鏈復(fù)制策略優(yōu)化初始集群,進(jìn)一步縮短調(diào)度長度;最后通過隊列合并與任務(wù)插入在不增加調(diào)度長度的基礎(chǔ)上,減小占用的計算單元數(shù)目。但TDCA算法仍存在以下不足:

(1) 部分參數(shù)的定義未考慮資源約束,過于理想化。在某些算例的調(diào)度過程中,尤其針對任務(wù)節(jié)點(diǎn)前驅(qū)任務(wù)較多的算例,會出現(xiàn)與實際情況偏差過大的情況,缺少參考價值。

(2) 布局優(yōu)化階段的偶然性較強(qiáng)。TDCA算法的隊列優(yōu)化階段主要包含隊列合并與任務(wù)插入2個環(huán)節(jié)。對于TDCA算法的隊列合并環(huán)節(jié),若布局不更新,每一隊列最多僅能嘗試進(jìn)行一次合并操作,操作次數(shù)的限制使得部分算例在隊列優(yōu)化階段后無法得到提升，而任務(wù)插入環(huán)節(jié)對縮短調(diào)度長度的作用也十分有限。

針對上述不足,本文提出帶資源約束的異構(gòu)多核系統(tǒng)任務(wù)復(fù)制調(diào)度算法(task-duplication scheduling aglorithm with resource constraints,TDSA-RC)。與TDCA算法相比,該算法主要有以下改進(jìn):

(1) 新的參數(shù)計算方式。在計算參數(shù)時通過限制分配到同一內(nèi)核上任務(wù)的個數(shù),在一定程度上體現(xiàn)了實際系統(tǒng)中資源約束的影響,使得計算出的參數(shù)更加精確。

(2) 適用性更強(qiáng)的優(yōu)化方式。擴(kuò)大了單一隊列操作次數(shù)的限制,提高了布局優(yōu)化階段的有效率。

(3) 通過冗余篩除及時清除復(fù)制階段引入的對縮短調(diào)度長度沒有意義的重復(fù)節(jié)點(diǎn)計算。

1 模型與約束

1.1 任務(wù)模型

任務(wù)調(diào)度問題的通用解決思路是將任務(wù)與多核系統(tǒng)抽象成某種形式的模型來設(shè)計調(diào)度算法,最普遍的方法是采用有向無環(huán)圖(directed acyclic graph,DAG)模型對待調(diào)度的任務(wù)進(jìn)行抽象建模。通過對任務(wù)進(jìn)行抽象建模,便可將復(fù)雜的多核任務(wù)調(diào)度問題轉(zhuǎn)化成特定約束下的DAG調(diào)度問題[15]。

在DAG圖中將異構(gòu)多核系統(tǒng)下的任務(wù)抽象成一個五元組，即

G=(V,E,P,W,C)

(1)

V={v1,v2,…,vNT}為任務(wù)節(jié)點(diǎn)集合,NT為集合中任務(wù)節(jié)點(diǎn)的數(shù)量,vi∈V為任務(wù)節(jié)點(diǎn)集合中的一個子任務(wù)。

E為邊集,e(i,j)∈E為任務(wù)vi到任務(wù)vj存在數(shù)據(jù)通訊。

P={p1,p2,…,pNP}為多核處理器上內(nèi)核的集合，NP為集合中內(nèi)核的數(shù)量。

W為子任務(wù)的執(zhí)行時間。對于異構(gòu)多核系統(tǒng),同一任務(wù)在不同內(nèi)核上的執(zhí)行時間存在差異,因此往往通過一個NT×NP的任務(wù)計算消耗表給出對應(yīng)的數(shù)值。為方便區(qū)分,任務(wù)vi在內(nèi)核pk上的執(zhí)行時間記為w(vi,pk)。

C為任務(wù)間的通訊時間,如c(i,j)表示任務(wù)vi、vj分配到不同內(nèi)核時,任務(wù)間通訊需要消耗的時間。為衡量DAG中通訊時間與執(zhí)行時間的關(guān)系,引入通信計算比(communication to computation ratio,CCR)表征平均通訊時間與平均執(zhí)行時間的比值。

若CCR越大,則DAG圖中通信占比越高;反之,則表示通信占比越小。

1.2 特殊集合與特殊節(jié)點(diǎn)

為方便表述,本節(jié)給出某些特殊節(jié)點(diǎn)/集合的定義。

如果某個節(jié)點(diǎn)存在到任務(wù)節(jié)點(diǎn)vi的通路,那么該節(jié)點(diǎn)即為任務(wù)vi的一個前驅(qū)任務(wù),vi所有的前驅(qū)任務(wù)的集合記為PRED(vi);如果某個節(jié)點(diǎn)存在來自任務(wù)節(jié)點(diǎn)vi的通路,那么該節(jié)點(diǎn)即為任務(wù)vi的一個后繼任務(wù),vi所有后繼任務(wù)的集合記為SUCC(vi)。

布局Sch用于表示調(diào)度的隊列分配結(jié)果,1個完整的布局Sch包含Sch(p1)、Sch(p2)、…、Sch(pNP)共NP個隊列,分別對應(yīng)p1、p2、…、pNP被分配到的任務(wù)隊列。

沒有前驅(qū)任務(wù),只有后繼任務(wù)的任務(wù)節(jié)點(diǎn)被稱為源點(diǎn)(entry-node);沒有后繼任務(wù),只有前驅(qū)任務(wù)的任務(wù)節(jié)點(diǎn)則被稱為匯點(diǎn)(exit-node)。

有2個及以上前驅(qū)任務(wù)的任務(wù)節(jié)點(diǎn)被稱為join節(jié)點(diǎn);有2個及以上后繼任務(wù)的任務(wù)節(jié)點(diǎn)則被稱為fork節(jié)點(diǎn)。

隊列節(jié)點(diǎn)Sch(pi,k)表示任務(wù)隊列Sch(pi)中第k個任務(wù)節(jié)點(diǎn)。

1.3 算法的約束條件

對?vi∈V,在實際調(diào)度中需要考慮2個值st(vi,p)和ct(vi,p),分別代表任務(wù)節(jié)點(diǎn)vi的在內(nèi)核p上的開始時刻和完成時刻。當(dāng)任務(wù)進(jìn)行實際調(diào)度時,需滿足以下約束條件:

(1) 資源約束。分配到同一個內(nèi)核上的任務(wù),其執(zhí)行時間不能重疊,即

(2)

(2) 數(shù)據(jù)約束。存在數(shù)據(jù)通訊的2個任務(wù),只有在前一任務(wù)完成且將數(shù)據(jù)結(jié)果傳遞到后一任務(wù)所在的內(nèi)核后,后一任務(wù)才能開始,即

ifvi,vj∈Sch(pk),e(vi,vj)∈E

?ct(vi,pk)≤st(vj,pk)或

ct(vj,pk)≤st(vi,pk)

(3)

(3) 任務(wù)約束。子任務(wù)是原子性的,執(zhí)行過程不可中斷,由此可以得到:

ct(vi,pk)=st(vi,pk)+w(vi,pk)

(4)

2 算法流程

2.1 參數(shù)計算

關(guān)鍵路徑是DAG任務(wù)圖的最長路徑,是算法壓縮調(diào)度長度的瓶頸所在。在調(diào)度算法中,關(guān)鍵路徑的確定與優(yōu)化十分重要。而對于異構(gòu)多核處理器,由于任務(wù)在不同內(nèi)核上的執(zhí)行時間存在差異,確定關(guān)鍵路徑時一方面需要考慮各個任務(wù)間的通訊消耗,另一方面還需要考慮在實際調(diào)度過程中任務(wù)的分配情況。因此,異構(gòu)多核系統(tǒng)下的調(diào)度算法在實際調(diào)度前無法準(zhǔn)確定位關(guān)鍵路徑,借助參數(shù)估算關(guān)鍵路徑是異構(gòu)多核調(diào)度算法的常見方法。

定義1 任務(wù)vi在內(nèi)核pk上的最早開始時刻為est(vi,pk)。在TDCA算法和TDSA-RC算法中,est(vi,pk)都是一個理想值,不用考慮計算單元是否被占用。TDCA算法中est(vi,pk)的計算公式如(6)式所示,其含義為在所有前驅(qū)任務(wù)vj調(diào)度到最理想內(nèi)核的情況下,最后一個前驅(qū)任務(wù)到達(dá)pk的時刻即為任務(wù)vi在pk最早開始時間，該值是不考慮內(nèi)核資源約束的理想值。

所有前驅(qū)任務(wù)vj都調(diào)度到最理想內(nèi)核這一條件在實際調(diào)度過程中是很難實現(xiàn)的。例如,調(diào)度到當(dāng)前內(nèi)核pk不需要計算通訊消耗,使得pk被大多數(shù)前驅(qū)任務(wù)認(rèn)定為最理想內(nèi)核的概率增高。若前驅(qū)任務(wù)堆積在pk上,則會使因沒有考慮內(nèi)核資源約束而造成的誤差大大增加,從而降低參數(shù)的可信度。

本文提出了一種新的參數(shù)計算方式,在一定程度上考慮調(diào)度過程中pk的資源約束問題。在計算est(vi,pk)時補(bǔ)充條件:vi的前驅(qū)任務(wù)中,有且僅有一個任務(wù)被放置在pk上。當(dāng)確定了某個前驅(qū)任務(wù)vm調(diào)度到pk后,其余的前驅(qū)任務(wù)只能被調(diào)度在除pk以外的次優(yōu)內(nèi)核,并補(bǔ)充通訊消耗,由此得到:

(5)

其中

(6)

(7)

ect(vk,fproc(vk,1))+comm(vk,vi,fproc(vk,1),fproc(vi,1))}

(8)

定義2 任務(wù)vi在計算單元pk上的最早完成時刻ect(vi,pk)。根據(jù)(4)式所描述的任務(wù)的原子性約束,在得到最早開始時刻的計算結(jié)果后,就可以計算出任務(wù)vi在計算單元pk上的最早完成時刻ect(vi,pk)。

ect(vi,pk)=est(vi,pk)+w(vi,pk)

(9)

定義3 任務(wù)vi對內(nèi)核的優(yōu)先級。根據(jù)任務(wù)vi在不同內(nèi)核的最早完成時刻ect(vi,p),按照非降序的原則對內(nèi)核進(jìn)行排序,得到任務(wù)vi對內(nèi)核的優(yōu)先級列表fproc(vi)。其中,優(yōu)先級最高的內(nèi)核被記為fproc(vi,1),意味著根據(jù)估算當(dāng)vi調(diào)度到pk時擁有最早結(jié)束時刻。因此,可以根據(jù)優(yōu)先級得到以下推斷:

ect(vi,fproc(vi,1))≤ect(vi,fproc(vi,2))≤

…≤ect(vi,fproc(vi,NP))

(10)

定義4 關(guān)鍵前驅(qū)任務(wù)cpred(vi)。關(guān)鍵前驅(qū)任務(wù)是最晚到達(dá)當(dāng)前內(nèi)核的前驅(qū)任務(wù),是優(yōu)化當(dāng)前任務(wù)最早開始時刻的瓶頸。TDSA-RC算法中關(guān)鍵前驅(qū)任務(wù)的定義如(8)式。

定義5 任務(wù)優(yōu)先級。為避免調(diào)度過程中發(fā)生數(shù)據(jù)沖突而造成算法中止,在生成初始布局前需要對任務(wù)節(jié)點(diǎn)進(jìn)行排序。TDSA-RC采用權(quán)值b-level(vi)確定各任務(wù)的優(yōu)先級。權(quán)值b-level(vi)的計算方法如(11)式所示,該權(quán)值代表了當(dāng)前子任務(wù)節(jié)點(diǎn)到達(dá)匯點(diǎn)的最長路徑長度。按照b-level(vi)遞減的原則對任務(wù)節(jié)點(diǎn)進(jìn)行排序,可得到任務(wù)優(yōu)先級列表(task priority list,TPL)。

(11)

定義6 關(guān)鍵前驅(qū)鏈。對于任意任務(wù)vi,其關(guān)鍵前驅(qū)鏈被定義為cpred(vi),cpred(cpred(vi)),……,直至追溯到源點(diǎn)。

2.2 生成初始布局

完成參數(shù)計算后進(jìn)入生成初始布局的階段。

從優(yōu)先級列表TPL中的第1個任務(wù)vk開始,將其分配到fproc(vk,1),然后依次補(bǔ)充當(dāng)前節(jié)點(diǎn)的關(guān)鍵前驅(qū)任務(wù),直至調(diào)度到源點(diǎn)。

隨后從剩余未調(diào)度的節(jié)點(diǎn)中,選擇b-level值最大的任務(wù)節(jié)點(diǎn)vp作為當(dāng)前任務(wù)curtask,進(jìn)行第2次分配,將其調(diào)度到空閑且當(dāng)前內(nèi)核優(yōu)先級最高的內(nèi)核隊列,然后對其關(guān)鍵前驅(qū)任務(wù)進(jìn)行調(diào)度。若其關(guān)鍵前驅(qū)任務(wù)cpred(vp)在第1次調(diào)度時已被調(diào)度到其他內(nèi)核隊列,則從vp的前驅(qū)任務(wù)中,選擇ect(vt,curtask)最小且未被調(diào)度的任務(wù)節(jié)點(diǎn)vt,將vt調(diào)度到當(dāng)前內(nèi)核隊列。以此類推,直至所有任務(wù)節(jié)點(diǎn)都完成調(diào)度。在生成初始布局時需要注意以下幾點(diǎn):

(1) 若curtask有且只有一個前驅(qū)任務(wù),則直接將該唯一的前驅(qū)任務(wù)添加進(jìn)當(dāng)前內(nèi)核隊列。

(2) 若curtask存在多個前驅(qū)任務(wù),則首先檢查curtask的關(guān)鍵前驅(qū)任務(wù)vi=cpred(curtask)是否滿足添加條件,即判斷是否滿足不等式ect(vi,fproc(vi,1))+c(vi,curtask)≥ect(vi,curtask),vi∈PRED(curtask)，目的是檢查當(dāng)任務(wù)調(diào)度vi被調(diào)度到其最佳隊列Sch(fproc(vi,1))時,能否得到比調(diào)度到當(dāng)前隊列更早的到達(dá)時間。若滿足添加條件,則將vi添加進(jìn)curtask所在隊列;若不滿足添加條件,則尋找其他前驅(qū)任務(wù)代替cpred(curtask);若找不到合適的替代任務(wù),則中斷該隊列的生成過程,進(jìn)行新隊列的生成。

生成初始布局的偽代碼如下:

for (task:TPL[1] to TPL[NP])

curtask=first unassigned task in TPL;

curproc=first proc in fproc(curtask)

&Sch(curproc)={?};

Sch(curproc)=Sch(curproc) ∪{curtask};

while curtask≠entry-node do

ptask=cpred(curtask);

if [in-degree(curtask)>1 &

(ptask is assigned or

ect(ptask,fproc(ptask,1))+

c(ptask,curtask)

Find unassigned ktask:

1.ktask∈PRED(curtask)

2.ect(ktask,fproc(ktask,1))+

c(ktask,curtask)≥ect(ktask,curproc)

3.minimizes ect(ktask,curproc);

if (ktask not exits)

back to line1;

else

ptask=ktask;

endif

Sch(curproc)=Sch(curproc)∪{ptask};

curtask=ptask;

end while

end for

2.3 任務(wù)復(fù)制

在任務(wù)復(fù)制階段,采用鏈?zhǔn)綇?fù)制策略,主要分為如下2個步驟。

(1) 尋找符合條件的備選點(diǎn)。備選點(diǎn)只需要滿足以下2個條件中的一個即可:①備選點(diǎn)是隊列頭節(jié)點(diǎn)Sch(p,1),但不是源點(diǎn);②備選點(diǎn)Sch(p,x)的前一節(jié)點(diǎn)Sch(p,x-1)不是Sch(p,x)的關(guān)鍵前驅(qū)任務(wù)。

(2) 針對備選點(diǎn)進(jìn)行任務(wù)復(fù)制。對于滿足條件①的備選點(diǎn),直接將備選點(diǎn)的關(guān)鍵前驅(qū)鏈復(fù)制到當(dāng)前任務(wù)隊列;對于滿足條件②的備選點(diǎn),將備選點(diǎn)前的任務(wù)移動到空閑且對Sch(p,x-1)而言優(yōu)先級最高的內(nèi)核隊列上;若此時不存在空隊列,則直接移動到fproc(sch(p,x-1),1)。最后,將備選點(diǎn)的關(guān)鍵前驅(qū)鏈補(bǔ)充進(jìn)當(dāng)前隊列。

完成任務(wù)復(fù)制操作后,需要進(jìn)一步判定調(diào)度長度是否得到優(yōu)化:若長度減少,則保留復(fù)制后的布局;否則恢復(fù)原有布局。

任務(wù)復(fù)制的偽代碼如下:

for (times:1 to TD-times-para)

for (curproc:1 to NP)

for(Sch(curproc,x):Sch(curproc,1) to Sch(curproc,last))

Sch-copy←Sch;//back-up

if(Sch(curproc,x-1)≠

cpred(Sch(curproc,x)))

nextProc=first processor in

fproc(Sch(curproc,x-1),1) to

fproc(Sch(curproc,x-1),NP)

&Sch(nextProc)={?};

if(nextProc not exits)

nextProc=fproc(Sch(curproc,x-1),1);

endif

move Sch(curproc,1)、

Sch(curproc,2)、…、Sch(curproc,x-1) to

Sch(nextProc);

Add predecessor trail of

Sch(curproc,x) to Sch(curproc);

else if(Sch(curproc,1)≠entry-node)

Add predecessor trail of

Sch(curproc,1) to Sch(curproc);

else

If (makespan(Sch)>makespan(copy-Sch))

Sch←copy-Sch;

end if

end for

end for

end for

2.4 布局優(yōu)化

任務(wù)復(fù)制完成后進(jìn)行布局優(yōu)化,優(yōu)化過程分為2個環(huán)節(jié),一是針對join節(jié)點(diǎn)的隊列合并;二是冗余節(jié)點(diǎn)篩除。

TDCA算法的布局優(yōu)化是通過將隊列與該隊末任務(wù)的最佳內(nèi)核隊列合并,其優(yōu)化效果的實質(zhì)是通過將不在同隊列的join節(jié)點(diǎn)前驅(qū),合并到同一隊列實現(xiàn)的,而TDSA-RC擴(kuò)大了隊列合并的適用范圍,并結(jié)合刪除冗余節(jié)點(diǎn)對布局進(jìn)行優(yōu)化。布局優(yōu)化的偽代碼如下:

Sch←after-tp-sch

for (times:1 to op-times-para)

for (cproc:p1topNP)

for (ctask:Sch(cproc,1) to

Sch(cproc,last))

if [ctask is join node &&

?v∈Sch(pv),v∈PRED(ctask),

pv≠cproc]

Sch-copy←Sch;

Add predecessor trail ofvandvto Sch(cproc);

if [makespan(Sch)≤makespan(Sch-copy)]

Sch←Check-Redundance(Sch)

endif

else Sch←Sch-copy;

endif

end for

end for

end for

final-Sch←Sch;

刪除冗余節(jié)點(diǎn)的目的是檢查任務(wù)復(fù)制過程中是否向布局內(nèi)引入對改進(jìn)調(diào)度長度無意義的冗余計算,若存在,則將其刪除。冗余節(jié)點(diǎn)篩除的偽代碼如下:

for(cproc:p1topNP)

for(ctask:Sch(cproc,1) to

Sch(cproc,last))

If(?ctask∈Sch(p),p≠cproc)

Sch-copy←Sch;

delete ctask in Sch(cproc);

if[makespan(Sch)>

makespan(Sch-copy)]

Sch←Sch-copy;

endif

end for

end for

After-check-sch←Sch;

3 實 驗

3.1 實驗概述

為了驗證所提TDSA-RC算法的調(diào)度效果,采用C語言分別實現(xiàn)了TDCA、HEFT、PEFT和TDSA-RC 4種算法。實驗主要分為如下2個部分:

(1) 驗證TDSA-RC算法處理任意隨機(jī)的任務(wù)圖時的加速效果。

(2) 驗證TDSA-RC算法在處理實際任務(wù)圖時的加速效果。

3.2 隨機(jī)任務(wù)圖實驗

參考文獻(xiàn)[13]中生成隨機(jī)任務(wù)圖的流程,本實驗選取任務(wù)圖中任務(wù)節(jié)點(diǎn)的總數(shù)(NT)、異構(gòu)處理單元的總數(shù)(NP)、隨機(jī)任務(wù)DAG的最大層級數(shù)(LEVEL)、通訊計算比(CCR)、系統(tǒng)異構(gòu)程度(OFFSET)和任務(wù)通訊所能跨越的最大層級數(shù)(CROSS-LEVEL)作為生成隨機(jī)任務(wù)圖時的參數(shù)。針對每一類型的變量生成了25張任務(wù)圖,總計生成51 200張任務(wù)圖。各個參數(shù)的取值范圍與默認(rèn)值見表1所列。

表1 隨機(jī)DAG參數(shù)及取值范圍

算例生成程序在生成異構(gòu)多核平臺的計算消耗表時,首先生成NP個中心值mid(v),其取值范圍為[MMIN,MMAX]。mid(v)為計算消耗w(v,p)的取值范圍中心,w(v,p)∈[mid(v)-OFFSET,mid(v)+OFFSET],OFFSET越高則系統(tǒng)異構(gòu)程度越強(qiáng)。實驗中MMIN、MMAX的默認(rèn)值分別為10、20。CROSS-LEVEL代表任務(wù)通訊所跨越的最大層級數(shù)。

在生成的51 200張隨機(jī)任務(wù)圖中,將TDSA-RC算法與TDCA、PEFT和HEFT算法的調(diào)度結(jié)果進(jìn)行對比,取得更優(yōu)、更差以及相同調(diào)度長度的概率統(tǒng)計結(jié)果見表2所列。

表2 隨機(jī)任務(wù)圖調(diào)度結(jié)果概率統(tǒng)計 %

由表2可知,若多核系統(tǒng)需要處理多種類型的隨機(jī)任務(wù),相比TDCA、PEFT和HEFT算法,采用TDSA-RC算法進(jìn)行調(diào)度獲得更好的結(jié)果幾率更大,其中與TDCA算法對比時,TDSA-RC算法的優(yōu)勢最為明顯。

實驗還進(jìn)一步地驗證了TDSA-RC在不同的參數(shù)取值下相比于TDCA算法的加速效果。TDSA-RC相對TDCA在處理隨機(jī)任務(wù)圖時的平均加速效果以ACC(TDSA-RC,TDCA)表示,簡記為ACC,其計算公式如下：

ACC(TDSA-RC,TDCA)=

100%

(12)

2種算法在不同參數(shù)取值下的相對加速效果變化如圖1所示。

圖1 隨機(jī)任務(wù)圖實驗結(jié)果

由圖1a～圖1e可知,在選定參數(shù)的范圍內(nèi),無論LEVEL、OFFSET、NT、NP、CCR如何變化,TDSA-RC算法都能取得較好的效果,平均加速比為12.08%；當(dāng)LEVEL=3或NT=30時,平均加速比可達(dá)15%以上。此外,由圖1a、圖1c可知,ACC的數(shù)值與DAG的任務(wù)節(jié)點(diǎn)總數(shù)NT成正相關(guān),而與DAG的任務(wù)層級數(shù)LEVEL成負(fù)相關(guān)。因此,與TDCA相比,TDSA-RC更適合處理規(guī)模較大、層級數(shù)較小的任務(wù)圖,而參數(shù)OFFSET、CCR的取值對ACC影響不大。

3.3 實際任務(wù)圖實驗

本實驗驗證TDSA-RC算法相比于TDCA算法在處理實際任務(wù)時的相對加速效果。實驗采用的DAG結(jié)構(gòu)如圖2所示。

圖2 實際任務(wù)的DAG

圖2中，LU分解(記為LU)、快速傅里葉變換(fast Fourier transform,FFT)、高斯(Gauss)消元以及相同節(jié)點(diǎn)數(shù)的隨機(jī)(Random)3種常見任務(wù)[16]作為調(diào)度對象進(jìn)行對比。

圖2中各個任務(wù)節(jié)點(diǎn)的計算消耗、通訊消耗由算例生成程序根據(jù)參數(shù)隨機(jī)給出,其中非自變量參數(shù)MMIN、MMAX的默認(rèn)值分別為10、20。

實驗選取了CCR、NP、OFFSET作為自變量,自變量參數(shù)的取值范圍與默認(rèn)值見表3所列。不同參數(shù)下相對于TDCA的加速效果如圖3所示。

表3 實際任務(wù)圖參數(shù)及取值范圍

圖3 實際任務(wù)圖實驗結(jié)果

從圖3可以看出,TDSA-RC在對FFT、LU分解進(jìn)行調(diào)度時,其調(diào)度結(jié)果優(yōu)于TDCA算法。其中針對FFT的改進(jìn)最為明顯,在多數(shù)情況下優(yōu)于對同等結(jié)點(diǎn)數(shù)的隨機(jī)任務(wù)進(jìn)行調(diào)度的效果。針對高斯消元的調(diào)度效果最差,在某些參數(shù)條件下會得到比TDCA算法更差的調(diào)度結(jié)果。

3.4 時間復(fù)雜度分析

TDCA算法的時間復(fù)雜度是O(mne+m2e)。其中:n為任務(wù)數(shù)；m為內(nèi)核數(shù)量；e為通訊數(shù)量。

TDSA-RC算法在參數(shù)計算階段的計算參數(shù)est(vi,pk)時間復(fù)雜度為O(mne),計算ect(vi,pk)的時間復(fù)雜度為O(mn)。且因計算內(nèi)核優(yōu)先級需要對內(nèi)核進(jìn)行排序,TDSA-RC算法中采用的排序算法的時間復(fù)雜度為O(m2),計算內(nèi)核優(yōu)先級的時間復(fù)雜度為O(m2n),計算關(guān)鍵前驅(qū)cpred(v)和b-level(v)權(quán)值的時間復(fù)雜度均為O(ne),因此參數(shù)計算環(huán)節(jié)的總時間復(fù)雜度為O(mne+mn+m2+m2n+ne)=O(m2n+mne);生成初始布局的時間復(fù)雜度為O(n2+mn+me);任務(wù)復(fù)制階段的的時間復(fù)雜度為O(mne);布局優(yōu)化階段的時間復(fù)雜度為O(mn×me)=O(m2ne)。

綜上可得TDSA-RC算法的時間復(fù)雜度為O(m2ne+n2),可以看出TDSA-RC的調(diào)度效果提升是以犧牲時間復(fù)雜度為代價的。

4 結(jié) 論

針對現(xiàn)有TDCA算法的不足,本文提出了一種異構(gòu)多核系統(tǒng)任務(wù)復(fù)制調(diào)度算法TDSA-RC。通過在參數(shù)計算階段考慮核的計算資源、改進(jìn)布局優(yōu)化方法和篩除冗余節(jié)點(diǎn)等方法對任務(wù)調(diào)度進(jìn)行優(yōu)化。通過隨機(jī)任務(wù)圖以及以LU分解、FFT和高斯消元為調(diào)度對象的對比實驗,表明該算法能有效縮短并行任務(wù)的調(diào)度長度,與TDCA算法相比平均性能提升可達(dá)12.08%,更加適合處理規(guī)模大、層級少且join節(jié)點(diǎn)占比多的并行任務(wù)。