基于HEFT和CPOP的相關任務表調度算法①

劉林東,鄔依林

1(廣東第二師范學院 計算機科學系,廣州 510303)

2(華南理工大學 計算機系統研究所,廣州 510006)

異構多核環境下的任務調度問題屬于NP-難問題[1-4],即任務調度問題只能得到近似最優解,因此異構多核環境下的任務調度問題對處理器系統的性能和效率提高具有非常重要的作用.多核處理器任務調度的目標[5]就是按照某種策略將每個任務合理分配到各個處理器內核上并行有序地執行,從而減少并行運行任務間的通信開銷和等待時間,使任務的執行時間最短.

異構多核處理器平臺下DAG任務調度算法主要包括表調度算法[6,7]、聚類調度算法以及基于復制的調度算法等,具體包括 DSC、DCP、CPFD、TDS、HEFT、CPOP和PEFT等算法.為了盡可以實現任務調度的目標,需要從任務調度的排序以及任務調度兩個環節對算法進行優化和改進.文中利用任務的方差以及平均通信開銷對任務進行排序,將關鍵路徑[8]、關鍵結點以及任務復制技術[9,10]應用于任務調度過程中,從而使任務調度的效率更接近任務調度的目標．在任務排序階段,以任務計算代價的二次方差以及平均通信開銷作為任務排序的依據,相比傳統HEFT算法直接用計算開銷作為排序的依據更科學、效率更高;在任務調度階段,對滿足任務復制條件的節點進行任務復制,可以避免部分任務之間的通信開銷,提高資源的利用率,降低任務集的計算時間.

1 相關任務調度及 DAG 任務模型

1.1 相關任務調度

根據被調度任務之間的相關性,可以將任務調度分為獨立任務調度和相關任務[11,12](依賴任務)調度兩種類型．異構多核處理器平臺下的任務調度可以分為靜態任務調度和動態任務調度兩種[13]．靜態任務調度[14]是指滿足硬件資源的負載均衡和通信開支的前提下將任務分配給固定的處理器內核;而動態任務調度[15]則指根據資源利用率的情況可以將任務分配到任何處理器內核上.相關任務在異構多核處理器平臺下的調度問題,主要任務是將子任務映射到多個處理器內核上,達到任務完成時間最小化等調度目標,因此在任務調度的過程中,不僅要考慮異構處理器內核計算能力的差異,同時還要考慮處理器內核之間的數據通信等問題,因此,相關任務的調度問題均屬于NP完全問題[16].

DAG任務調度算法主要有DSC[17]、DCP[18]、CPFD[19]、TDS[20]、HEFT[21,22]、CPOP[21,22]和PEFT[23]等算法.異構多核處理器平臺下DAG任務調度算法主要包括三類,分別為表調度算法、聚類調度算法以及基于復制的調度算法.

表調度算法[24]是最經典的DAG調度算法.表調度算法包括靜態調度算法和動態調度算法兩種．靜態調度算法的基本思想:根據DAG中的所有任務之間的關系,結合某種策略決定任務之間的優先級并構造一個調度列表;然后為具有最高優先級的任務分配能夠使它最快完成的資源并開始調度執行,循環上述步驟直到DAG中所有任務均被調度.動態表調度算法在執行完每一個任務后根據當前處理器內核的情況以及任務之間的依賴關系重新計算任務的優先級,靜態調度算法的不重新計算優先級,而動態調度算法需要重新計算優先級.常見的表調度算法包括Topcuoglu等人提出的 HEFT (Heterogeneous Earliest Finish Time)算法[25,26]以及CPOP算法.

1.2 DAG任務模型

通常使用 DAG (Directed Acyclic Graph)任務圖來描述相關任務之間的關系.相關任務的特點是任務的所有前驅節點執行完成后,后續任務才能開始執行.DAG表示為G=(V,E,ET,C),其中V表示n個任務結點t1,t2,…,tn的集合,每一個結點vi表示 DAG 中的一個任務,|V|=n;E表示k條有向邊e1,e2,…,ek的集合,每條有向邊ci,j∈E,表示任務結點ti,tj之間存在先后執行的關系,即任務tj必須在任務ti執行完成之后才能開始執行,每一條邊的權值表示任務和任務之間的通信時間;ET表示任務ti在處理器內核cj上的估算計算時間,在DAG中,通常用平均計算時間作為任務節點的權值,任務ti的平均執行時間為;C是任務之間通信開銷的集合,在DAG中,將任務的通信開銷作為邊的權值.

定義1.pred(ti)表示在給定的 DAG 中,任務ti直接前驅任務組成的集合.如果pred(ti)=?,那么稱該任務為入口任務,用tentry表示.succ(ti)表示在給定的DAG中,任務ti直接后繼任務組成的集合.如果succ(ti)=?,那么稱該任務為出口任務,表示為texit.如果在一個DAG中,有多個入口任務或出口任務,那么增加一個通信時間和計算時間為0的虛擬入口或出口任務.

定義2.矩陣ET,是一個n*m的計算時間矩陣,其中n表示任務數,m表示處理機內核數量,ET(ti,cj)表示在處理機內核cj上執行任務ti的估算時間.

定義3.關鍵路徑 (Critical Path,CP),在 DAG 中,一條從入口節點tentry到出口節點texit的最長路徑稱為關鍵路徑.

定義4.跨度(Makespan)或調度長度表示某一個確定的調度算法對任務集T調度后,任務集T中最后一個任務的完成時間,如式(1)所示．其中AFT(ti)表示任務ti實際完成時間,Makespan是所有出口任務中實際完成時間的最大值．

定義5.最早開始時間EST(ti,cj)是指任務ti在處理器內核cj上的最早開始時間,EST(ti,cj)取AFT(ti)和EFT(cj)兩個值中的較大值,如式(2)所示.

定義6.最早完成時間EFT(ti,cj)是指任務ti在處理器內核cj上的最早完成時間,其值等于任務ti在處理器內核cj上的最早開始時間,加上ti在處理機內核cj上的計算時間,如式(3)所示.

定義7.平均等待時間AWT,任務集T中的所有任務在調度過程中,設任務ti的開始執行時間為STi,任務到達時間ATi,則.

定義8.C表示通信開銷的集合.ci,j表示任務ti和tj之間的通信開銷,通常用平均通信代價ci,j來表示任務ti和tj之間的通信開銷,任務ti和tj之間的平均通信開銷如式(4)所示.其中表示所有處理機內核的平均延遲,表示處理機內核相連的平均帶寬,datai,j表示ti發送給任務tj的數據總量．當ti和tj被分配到同一個處理機內核時ci,j=0,這是因為相比處理機內核之間的通信,處理機內核內的通信可以被忽略.

定義9.Slack．Slack是一個關于任務調度算法魯棒性的量度,其反映的是一個算法調度產生的任務處理時間的不確定程度.Slack的定義如式(5)所示.其中M表示DAG的Makespan,n表示任務數量,blevel表示任務ti到出口節點最長路徑的長度,tlevel表示從入口節點到任務ti(不包含任務ti)最長路徑的長度.

2 任務調度模型及算法

2.1 DAG任務模型

針對傳統的表調度算法中存在不能準確反應DAG任務圖中的內在聯系、任務與處理器內核之間調度效率不高以及負載不均衡等問題,本文提出了一種的相關任務調度模型及相關任務調度算法IHEFT算法.相關任務調度模型如圖1所示,任務集T中的任務被調度到處理器內核集C中包括分兩個步驟:任務排序和任務調度.任務排序階段,主要根據任務的執行時間方差以及平均通信開銷作為排序的依據;任務調度階段,判斷當前任務結點的前驅結點是否為關鍵結點,如果為關鍵結點且滿足任務復制條件,則進行任務復制,否則按HEFT調度算法對任務進行調度.

圖1 相關任務表調度模型

2.2 調度算法

相關任務調度IHEFT算法如算法1所示.算法的主要思想為:在任務排序階段,用任務在各個處理器內核上的執行時間方差以及通信成本作為參數對DAG任務進行排序,任務執行時間的方差以及通信成本越大,任務在不同的處理器內核上的執行時間差異就越大,給任務賦予較高的優先級,相反,賦予較小的優先級,任務ti的方差及通信成本 δi計算如式(7)所示.在任務調度階段,首先獲取DAG任務圖的關鍵路徑,關鍵路徑上的節點任務優先級最高,非關鍵路徑上的任務按 δi降序排列;然后利用任務復制技術優化任務調度過程,若當前任務ti的前驅節點tj為關鍵節點任務,且復制關鍵節點任務tj到被調度的處理器內核cm可以縮短當前任務的最早完成時間,EFT(ti,cm)′定義如式(6)所示,則復制關鍵節點任務tj到當前處理器內核cm;若不滿足任務復制條件,即EFT(ti,cm)′≥EFT(ti,cm),則按HEFT算法將任務調度到使任務完成時間最早的處理器內核.通過任務復制可以減少任務間通信開銷、提高處理器內核利用率等目的.

3 任務調度過程分析

以1個DAG任務圖為例,分析IHEFT相關任務調度算法在異構多核處理器內核上的調度過程.

算法 1.IHEFT 算法4.計算所有任務的二次方差 值δiδi的值;1.從DAG任務圖中讀取任務數到n;2.從DAG任務圖中讀取計算節點的數量到m;3.讀取DAG任務圖中任務之間的通信開銷,并保存在c[n][n]中;5.按降序順序對所有任務 進行排序;6.從出口任務開始,對DAG任務進行遍歷,計算所有任務的ranku值;7.入口任務開始,對DAG任務圖進行遍歷,計算所有任務的rankd值;8.計算DAG中每個任務的優先級,計算方法為priority[ti]=ranku[i]+rankd[i];9.通過priority[ti]找出DAG任務圖的關鍵路徑CP;10.while 任務集非空{11.從DAG任務圖中找出優先級最高的任務ti;13.if當前任務節點ti的前驅節點tj是關鍵路徑節點,即滿足式(5-11)條件;12.找到相應的計算節點fm調度任務;14.將任務tj復制到計算節點fm上,并在此計算節點上執行;15．保存ST[i],FT[i],Avail[m]的值;16.else 17.調度任務ti到計算節點fm上;18.保存ST[i],FT[i],Avail[m]19.s[i][m]=120.計算所有任務的跨度Makespan值;21.}22.計算任務集中所有的任務的平均等待時間AWT以及Slack值

3.1 DAG初始化

圖2表示一個DAG任務模型,共有10個任務,帶箭頭的邊表示任務之間的通信邊,邊上的數字表示兩個任務之間的通信代價ci,j;節點t1為入口節點,節點t10為出口節點.表1表示任務在不同處理器內核上的計算時間ET(ti,cj),表1中包括 3 個處理器內核c0～c2,10 個任務t1～t10.

圖2 DAG 任務模型

表1 任務集在內核集上的調度時間

表2 依賴關系矩陣

3.2 依賴關系矩陣

根據DAG任務模型,生成任務之間對應的依賴關系矩陣,如表2所示.依賴關系矩陣的定義為:

(1)若結點i為結點j的前驅節點,則矩陣元素;

(2)若結點i和結點j之間不存在依賴關系,則矩陣元素di,j=0.

3.3 任務排序

計算每個任務ti的ranku、rankd、ranku+rankd值以及計算代價的二次方差、通信開銷值δi,并降序進行排序,表3所示為4核環境下各參數的計算及排序情況.

表3 IHEFT 算法的ranku、rankd值

3.4 任務調度

(1)計算關鍵路徑

計算每個任務的ranku值以及rankd值,在此基礎上找出DAG任務模型中的關鍵路徑,任務集t1～t10的關鍵路徑為:t1,t3,t8,t10.

(2)任務復制

根據生成的任務調度序列t1,t3,t4,t2,t8,t9,t7,t6,t5,t10,對每個被調度的任務檢查是否滿足任務復制條件EFT(ti,cm)′＜EFT(ti,cm),即任務被復制到另一個處理器內核上,要滿足復制前驅任務后當前任務的完成時間要小于不復制前驅任務的完成時間.在任務t4和t2被調度時,滿足任務復制條件,分別將t4和t2的前驅任務t1復制到處理器內核c1和c0上,如圖3(a)所示.

圖3 三種算法任務調度對比

(3)任務調度

任務集經過調度之后,任務與處理器內核的對應調度關系如圖3(a)所示,圖3(b)、圖3(c)分別表示同一任務集通過HEFT算法、CPOP算法調度的對應關系,很明顯,HEFT、CPOP 算法任務調度的總長度Makespan值比IHEFT算法要大.

4 仿真實驗與結果分析

4.1 實驗目的

為了驗證本章提出的IHEFT算法,在相同的實驗條件下對本章所提出的算法IHEFT與現有的調度算法HEFT和CPOP算法進行性能比較,主要比較任務跨度Makespan和任務平均等待時間AWT.

4.2 模擬環境

基于SimGrid提供的模擬器工具包,構建一個異構多核處理器的仿真環境.其中:

(1)處理器內核之間通過高速網絡互連;

(2)每個處理器內核可同時進行任務執行和與其它處理器內核通信,而不需要爭用;

(3)任務在處理器內核上執行是非搶占的;

(4)處理器內核之間是異構的,即同一個任務在不同處理器內核上執行存在差異性．

實驗中使用的計算機配置為:Intel Core i5-3210M@2.5 GHz 雙核筆機本處理機,8 GB 內存.本次實驗采用的處理器內核分別取3、4核.

4.3 測試數據集

IHEFT算法輸入的數據包括DAG任務圖(包括任務集、處理器內核集、任務間通信成本)、任務調度計算時間矩陣;算法的輸出為任務調度執行時間Makespan以及任務平均等待時間AWT．IHEFT算法任務調度測試分兩種情形.第一種情況:任務集中包括10個任務,處理器內核集中包括3個處理器內核,DAG任務圖的數量分別為1～10;第一種情況:任務集中包括10個任務,處理器內核集中包括4個處理器內核,DAG任務圖的數量分別為1～10,所有任務的到達時間為0.

4.4 實驗結果分析

利用三種算法分別對10個DAG任務圖進行調度,表4為三種算法在3核、4核情況下Slack值的對比情況.

(1)3 個處理器內核

分別采用3種算法對DAG任務集進行調度,在處理器內核的數量為3的情況下,針對不同數量DAG任務模型進行調度,得到所有任務的跨度(調度長度)Makespan、平均等待時間AWT的值以及平均Slack值,如圖4(a)、圖4(b)、圖5所示.

表4 IHEFT、HEFT、CPOP 算法的Slack值

圖4 不同DAG的任務跨度對比和任務平均等待時間對比

圖4(a)的縱坐標為算法所獲得的調度跨度Makespan值,橫坐標為 DAG 數量;圖4(b)的縱坐標為算法所獲得的調度跨度平均等待時間AWT值,橫坐標為DAG數量．從實驗數據得出,在任務調度的跨度方面,IHEFT算法比HEFT算法最低降低了10%,最高降低了15.7%;IHEFT算法比CPOP最低降低了14.3%,最高降低了21.2%;在任務平均等待時間方面,IHEFT算法比HEFT算法最低降低了3.3%,最高降低了17.5%,IHEFT算法比CPOP算法最低降低了14.6%,最高降低了28.0%．圖5中縱坐標為算法所獲得的平均Slack值,橫坐標為 DAG 數量,從圖5可以看出,隨著 DAG數量的的增加,IHEFT、HEFT和CPOP算法的Slack值變化不明顯,但是橫向比較可以看出IHEFT相對HEFT和CPOP算法有更低的Slack值,IHEFT算法的Slack值最高比HEFT算法要減少31.2%,比CPOP算法要減少36.1%．

圖5 不同 DAG 的任務Slack對比

(2)4 個處理器內核

分別采用3種算法對DAG任務集進行調度,在處理器內核的數量為4的情況下,針對不同數量DAG任務模型進行調度,得到所有任務的跨度makespan、平均等待時間AWT的值以及平均Slack值,如圖6(a)、圖6(b)、圖7所示.

圖6(a)的縱坐標為算法所獲得的調度跨度makespan值,橫坐標為DAG數量;圖6(b)的縱坐標為算法所獲得的調度跨度平均等待時間AWT值,橫坐標為DAG數量.從實驗數據得出,在任務調度的跨度方面,IHEFT算法比HEFT算法最低降低了22.2%,最高降低了27.1%;IHEFT算法比CPOP最低降低了29.1%,最高降低了34.4%;在任務平均等待時間方面,IHEFT算法比HEFT算法最低降低了19.9%,最高降低了24.8%,IHEFT算法比CPOP算法最低降低了33.6%,最高降低了37.0%.圖7中縱坐標為算法所獲得的平均Slack值,橫坐標為 DAG 數量,從圖7可以看出,隨著DAG數量的的增加,IHEFT、HEFT和CPOP算法的Slack值變化不明顯,但是橫向比較可以看出IHEFT相對HEFT和CPOP算法有更低的Slack值,IHEFT算法的Slack值最高比HEFT算法要減少26.6%,比CPOP算法要減少34.3%.

圖6 不同DAG的任務跨度對比和任務平均等待時間對比

通過兩組實驗分析得出,IHEFT算法在任務調度跨度以及任務調度平均等待時間兩方面均優于HEFT算法和CPOP算法.在任務調度跨度方面最小分別降低了10%和14.3%,在任務調度平均等待時間方面最小分別降低了3.3%和14.6%．IHEFT的任務排序方面采用計算代價的二次方差作為排序依據更能體現任務的優先級,而在任務調度的過程中對滿足條件的任務進行任務復制可以有效地減少任務調度的跨度、任務調度平均等待時間以及平均Slack值.

5 結論與展望

文中介紹了相關任務調度及DAG任務模型的基本概念,對相關任務調度算法HEFT算法和CPOP算法進行了介紹.由于HEFT算法和CPOP算法在相關任務調度中存在一些缺陷,基于HEFT算法和CPOP算法,對相關任務調度中任務排序和任務調度兩個方面進行改進,提出了一種相關任務調度模型和相關任務調度算法IHEFT算法.通過實驗證明,IHEFT算法在任務調度跨度、任務調度平均等待時間以及平均Slack方面均優于HEFT算法和CPOP算法.

圖7 不同 DAG 的任務Slack對比