帶資源約束的異構多核任務復制調度算法

王月恒, 倪 偉, 汪 敏

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

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

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

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

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

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

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

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

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

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

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

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

1 模型與約束

1.1 任務模型

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

有2個及以上前驅任務的任務節(jié)點被稱為join節(jié)點;有2個及以上后繼任務的任務節(jié)點則被稱為fork節(jié)點。

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

1.3 算法的約束條件

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

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

(2)

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

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

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

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

(3)

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

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

(4)

2 算法流程

2.1 參數(shù)計算

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

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

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

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

(5)

其中

(6)

(7)

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

(8)

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

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

(9)

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

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

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

(10)

定義4 關鍵前驅任務cpred(vi)。關鍵前驅任務是最晚到達當前內核的前驅任務,是優(yōu)化當前任務最早開始時刻的瓶頸。TDSA-RC算法中關鍵前驅任務的定義如(8)式。

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

(11)

定義6 關鍵前驅鏈。對于任意任務vi,其關鍵前驅鏈被定義為cpred(vi),cpred(cpred(vi)),……,直至追溯到源點。

2.2 生成初始布局

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

從優(yōu)先級列表TPL中的第1個任務vk開始,將其分配到fproc(vk,1),然后依次補充當前節(jié)點的關鍵前驅任務,直至調度到源點。

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

(1) 若curtask有且只有一個前驅任務,則直接將該唯一的前驅任務添加進當前內核隊列。

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

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

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 任務復制

在任務復制階段,采用鏈式復制策略,主要分為如下2個步驟。

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

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

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

任務復制的偽代碼如下:

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)化

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

TDCA算法的布局優(yōu)化是通過將隊列與該隊末任務的最佳內核隊列合并,其優(yōu)化效果的實質是通過將不在同隊列的join節(jié)點前驅,合并到同一隊列實現(xiàn)的,而TDSA-RC擴大了隊列合并的適用范圍,并結合刪除冗余節(jié)點對布局進行優(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é)點的目的是檢查任務復制過程中是否向布局內引入對改進調度長度無意義的冗余計算,若存在,則將其刪除。冗余節(jié)點篩除的偽代碼如下:

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算法的調度效果,采用C語言分別實現(xiàn)了TDCA、HEFT、PEFT和TDSA-RC 4種算法。實驗主要分為如下2個部分:

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

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

3.2 隨機任務圖實驗

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

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

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

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

表2 隨機任務圖調度結果概率統(tǒng)計 %

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

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

ACC(TDSA-RC,TDCA)=

100%

(12)

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

圖1 隨機任務圖實驗結果

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

3.3 實際任務圖實驗

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

圖2 實際任務的DAG

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

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

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

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

圖3 實際任務圖實驗結果

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

3.4 時間復雜度分析

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

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

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

4 結 論

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