王 冠，王宇新，陳 鑫，王 飛，郭 禾

(1.大連理工大學 軟件學院，遼寧 大連 116620； 2.遼寧警察學院 公安信息系，遼寧 大連 116036；3.大連理工大學 計算機科學與技術(shù)學院，遼寧 大連 116024)

(*通信作者電子郵箱wyx@dlut.edu.cn)

基于直接后繼節(jié)點完成時間的異構(gòu)調(diào)度算法

王 冠1,2，王宇新3*，陳 鑫1，王 飛3，郭 禾1

(1.大連理工大學 軟件學院，遼寧 大連 116620； 2.遼寧警察學院 公安信息系，遼寧 大連 116036；3.大連理工大學 計算機科學與技術(shù)學院，遼寧 大連 116024)

(*通信作者電子郵箱wyx@dlut.edu.cn)

分布式環(huán)境下的異構(gòu)計算系統(tǒng)(HCS)是大數(shù)據(jù)時代進行數(shù)據(jù)密集型計算不可或缺的，一個有效的任務(wù)調(diào)度算法可以提高整個異構(gòu)計算系統(tǒng)的效率。在對異構(gòu)環(huán)境下的任務(wù)調(diào)度進行有向無環(huán)圖(DAG)建模的基礎(chǔ)上，提出基于直接后繼節(jié)點完成時間的異構(gòu)調(diào)度算法(HSFT)。在計算開銷和通信開銷差異度較大的異構(gòu)環(huán)境中，考慮兩者之間的平衡，采用更為合理的以計算均值與標準方差的乘積和通信權(quán)值與任務(wù)節(jié)點出度的比值作為優(yōu)先權(quán)值計算方法，并在考慮最快完成時間(EFT)的基礎(chǔ)上，將直接后繼節(jié)點完成時間(SFT)用于處理器分配策略。實驗結(jié)果表明，HSFT在不增加算法時間復雜度的情況下，比HEFT、SDBATS、PEFT等算法有更短的調(diào)度長度(makespan)、更優(yōu)的調(diào)度長度比和效率。

有向無環(huán)圖調(diào)度；異構(gòu)計算；任務(wù)優(yōu)先級；直接后繼節(jié)點；靜態(tài)任務(wù)調(diào)度

0 引言

在大數(shù)據(jù)時代，數(shù)據(jù)的密集計算往往不能依靠單一的處理器完成，需要依賴于分布式環(huán)境下的異構(gòu)計算系統(tǒng)(Heterogeneous Computing System, HCS)。異構(gòu)計算系統(tǒng)被定義為一個由高速網(wǎng)絡(luò)聯(lián)通的多處理器計算平臺，可以執(zhí)行并行和分布式的密集計算[1]。所謂計算機系統(tǒng)的異構(gòu)性，是指其計算資源之間存在計算能力的差異，并且各計算資源之間進行數(shù)據(jù)傳輸時，其通信傳輸速度也存在差異性。云計算平臺就是一個典型的異構(gòu)計算系統(tǒng)。一個有效的任務(wù)調(diào)度算法可以提高整個異構(gòu)計算系統(tǒng)的效率，目標是為了得到最短的完成時間(makespan)[2]。具體來說，算法需要在滿足任務(wù)間先后續(xù)關(guān)系的情況下，決定每個任務(wù)的執(zhí)行順序，并將其分配到合適的處理器上去執(zhí)行。

對于如何合理進行任務(wù)調(diào)度的問題，諸多學者進行了研究，比較典型的任務(wù)調(diào)度算法有Topcuoglu等[3]提出的HEFT(Heterogeneous Earliest Finish Time)算法，該算法被認為是最經(jīng)典的任務(wù)調(diào)度算法，具有很好的通用性和穩(wěn)定性，通常被作為最基本的參照算法進行實驗對比；但是由于算法本身對于異構(gòu)的差異性考慮不夠，所以對待復雜異構(gòu)環(huán)境下的任務(wù)調(diào)度結(jié)果往往并不理想。Munir等[4]提出的SDBATS(Standard Deviation-Based Algorithm for Task Scheduling)算法是一個新穎的任務(wù)調(diào)度算法，首次提出使用標準方差(standard deviation)代替均值的方法進行任務(wù)調(diào)度優(yōu)先級Rank值的計算，提高了對計算差異過大的異構(gòu)調(diào)度的算法適應(yīng)性；但是算法本身過于忽略通信開銷的優(yōu)先權(quán)值，容易引起計算開銷和通信開銷的不公平性，并且算法采用對每個處理器都進行入口任務(wù)的副本策略，這一策略有時并不合理，不但不會提高調(diào)度效率，甚至會造成延遲調(diào)度時間的情況。Arabnejad等[5]提出的PEFT(Predict Earliest Finish Time)算法是新近提出的優(yōu)秀調(diào)度算法，給出一個預測性的OCT(Optimistic Cost Table)作為優(yōu)先權(quán)值，計算所有子節(jié)點在不同處理器上的計算開銷與通信開銷之和的最小值，并將此值代入處理器選擇階段中。但是由于PEFT算法過于關(guān)注子節(jié)點在串行時的開銷，對于子節(jié)點并行度較高的情況和通信開銷較大的任務(wù)模型，并不能給出理想的調(diào)度結(jié)果。本課題組在文獻[6]中提出了HSIP(Heterogeneous Scheduling algorithm with Improved task Priority)，更好地考慮了異構(gòu)差異度較大環(huán)境下的合理調(diào)度問題，但HSIP算法在對于計算開銷與通信開銷之間的權(quán)值數(shù)量級平衡問題以及對于處理器的分配策略還不夠理想，存在進一步改良的可能。

綜上所述，本文提出HSFT(Heterogeneous scheduling algorithm with immediate Successor Finish Time)算法，在異構(gòu)差異度較大的情況下，平衡計算開銷與通信開銷之間的數(shù)量級公平性，采用更為合理的優(yōu)先權(quán)值計算方法，并提出直接后繼節(jié)點完成時間(Successor Finish Time, SFT)用于處理器分配策略。實驗證明，HSFT比HEFT、SDBATS、PEFT等算法有更好的調(diào)度長度(makespan)、調(diào)度長度比(schedule length ratio)與效率值(efficiency)，并且沒有增加算法的時間復雜度。

1 相關(guān)工作

近年來，眾多的調(diào)度算法被提出用于解決在異構(gòu)計算系統(tǒng)下的任務(wù)調(diào)度問題。通?？梢詫⑦@些調(diào)度算法根據(jù)解決的問題模型分為兩個大類，即動態(tài)調(diào)度(dynamic scheduling)和靜態(tài)調(diào)度(static scheduling)。在動態(tài)調(diào)度的問題模型中，每個任務(wù)的計算開銷和通信開銷以及任務(wù)之間的連接關(guān)系都是未知的。在一個新任務(wù)到來時，算法才能得到具體的相關(guān)參數(shù)，給出一個實時的調(diào)度策略。動態(tài)調(diào)度算法只對新到達的任務(wù)和正在準備執(zhí)行的任務(wù)進行判斷，決定先后執(zhí)行的策略。比較典型的動態(tài)調(diào)度算法有Dynamic Mapping Heuristics[7]和Dynamic scheduling method[8]。

對于靜態(tài)調(diào)度的問題模型來說，每個任務(wù)的計算和通信開銷以及整個任務(wù)間的連接關(guān)系都是已知的。算法可以在編譯時間內(nèi)，根據(jù)上述已知的參數(shù)給出一個理想的調(diào)度結(jié)果。通常也將靜態(tài)調(diào)度算法分為兩大類：導向隨機搜索機制算法(guided random search-based algorithm)和啟發(fā)式算法(heuristic-based algorithm)。比較典型的導向隨機搜索機制算法有GA Multiprocessor Task Scheduling[9]和Problem-Space Genetic Algorithm (PSGA)[10]。這類算法都是通過多次的迭代來求得最優(yōu)解，但是與啟發(fā)式算法相比會增加過多的復雜度與處理器開銷。啟發(fā)式算法可以分為三種類型：聚類(clustering)、副本(duplication)和表(list)。聚類算法通常適合在同構(gòu)計算環(huán)境下的調(diào)度，對于異構(gòu)環(huán)境的調(diào)度效果有限。副本算法通常會得到較好的調(diào)度結(jié)果，但同樣也會產(chǎn)生更高的算法復雜度。此外，副本會引起更多的處理器占用問題，這不僅會增加額外的處理器能耗開銷，更會耽誤其他任務(wù)對于資源的共享，影響整體的優(yōu)化調(diào)度。表調(diào)度算法相對來說有著更好的調(diào)度性能、更低的算法復雜度，是靜態(tài)調(diào)度中最為流行的調(diào)度算法。典型的表調(diào)度啟發(fā)式調(diào)度算法有HEFT[3]、SDBATS[4]、PEFT[5]、HSIP[6]、LDCP(Longest Dynamic Critical Path)[11]和PETS(low complexity Performance Effective Task Scheduling)[12]等。

2 異構(gòu)環(huán)境下的任務(wù)調(diào)度模型

本文研究的問題模型為在由多處理器集合P組成的異構(gòu)計算系統(tǒng)中對單一應(yīng)用程序(application)進行靜態(tài)調(diào)度。調(diào)度算法目的為對單一應(yīng)用程序在P中進行處理后，得到最小的執(zhí)行時間。該模型與HEFT、SDBATS、PEFT等算法的問題模型一致。應(yīng)用程序通常會描述為一個有向無環(huán)圖(Directed Acyclic Graph, DAG)，G=(V,E)。其中V= {v1,v2,…,vn}表示任務(wù)節(jié)點的集合，E={e1,e2,…,em}表示邊的集合。一個簡單的DAG模型用例如圖1，與前述算法中的例圖具有相同的結(jié)構(gòu)，并且其參數(shù)選取與文獻[5]完全一致。

每個節(jié)點vi∈V表示一個具體的執(zhí)行任務(wù)，每條邊e(i, j)∈E表示在任務(wù)先后續(xù)關(guān)系下的兩個任務(wù)之間的通信開銷，即任務(wù)vi必須執(zhí)行完成后才可以將數(shù)據(jù)傳給vj來執(zhí)行。

圖1 DAG例圖與計算開銷矩陣

(1)

ci, j作為邊e(i, j)上的權(quán)值用來表示任務(wù)vi和任務(wù)vj之間的通信開銷，當任務(wù)vi和vj分配到同一處理器上執(zhí)行時，兩者間通信開銷為0，因為模型忽略同一處理器內(nèi)部的通信開銷，并且認為各處理器之間是完全聯(lián)通的拓撲結(jié)構(gòu)，在各處理器上進行任務(wù)的執(zhí)行和通信傳輸是可以同時進行而沒有沖突的。接下來給出幾個在DAG調(diào)度問題中常見的定義。

定義1 調(diào)度長度(makespan)表示DAG中最后一個任務(wù)的完成時間，如式(2)所示：

makespan=max{AFT(vexit)}

(2)

其中AFT(vexit)表示出口節(jié)點的實時完成時間。

定義2 最快開始時間(Earliest Start Time, EST)。EST(vi,pj)表示節(jié)點vi在處理器pj上可以開始執(zhí)行的最早時間，具體定義如式(3)所示：

(3)

其中：TAvl(pj)表示處理器pj可以開始運行任務(wù)的最早時間，pred(vi)表示任務(wù)vi的所有直接前驅(qū)節(jié)點，即任務(wù)vi在處理器pj上最快開始運行時間，為處理器可以運行時間與前驅(qū)節(jié)點傳輸數(shù)據(jù)完成時間兩者之間的較大值，當前驅(qū)節(jié)點vm和vi在同一處理器運行時，cm, j=0。對于入口節(jié)點，不考慮處理器啟動時間的情況下，最快開始時間EST(ventry,pj)=0。

定義3 最快完成時間(Earliest Finish Time, EFT)。EFT(vi,pj)表示任務(wù)vi在處理器pj上的最快完成時間，如式(4)所示：

EFT(vi,pj)=EST(vi,pj)+wi, j

(4)

同樣的，對于入口任務(wù)，其最快完成時間EFT(ventry,pj)=wventry, j。

定義4 出度通信開銷權(quán)值(Out-degree Communication Cost Weight，occw)。表示任務(wù)vi所有出度節(jié)點的通信開銷之和，出度(out degree)即為該節(jié)點擁有的直接后繼節(jié)點個數(shù)。具體如式(5)所示：

(5)

出度通信開銷權(quán)值對于調(diào)度結(jié)果會產(chǎn)生很大的影響，當一個occw值過大的任務(wù)節(jié)點沒有被優(yōu)先調(diào)度時，往往導致其直接后繼節(jié)點需要更長時間的等待。

綜上所述，DAG調(diào)度算法的目標即為決定DAG中每個任務(wù)的執(zhí)行順序并將其分配到一個具體處理器上執(zhí)行，以得到一個最小的調(diào)度長度(makespan)。當所有任務(wù)被執(zhí)行完畢時，式(2)中出口節(jié)點的實時完成時間即為調(diào)度長度。

3 HSFT

本文提出基于直接后繼節(jié)點完成時間的異構(gòu)調(diào)度算法——HSFT，算法由計算任務(wù)調(diào)度優(yōu)先級階段和處理器分配階段兩個階段組成。

3.1 任務(wù)調(diào)度優(yōu)先級階段

在任務(wù)調(diào)度優(yōu)先級階段，通過從出口節(jié)點開始向上迭代來計算每個節(jié)點的優(yōu)先權(quán)值ranku，然后對其進行降序排列決定調(diào)度順序。每個節(jié)點的ranku計算如式(6)所示:

(6)

其中：succ(vi)表示任務(wù)vi的所有直接后繼節(jié)點，σi表示任務(wù)vi計算開銷的標準方差，outd(vi)表示任務(wù)vi的出度值，即直接后繼節(jié)點的個數(shù)。采用標準方差可以更好地體現(xiàn)出同一任務(wù)在不同處理器上的計算差異，即計算異構(gòu)差異越大，標準方差值越大，該算法的調(diào)度優(yōu)先級就越高。使用標準方差與均值相乘作為計算權(quán)值可以更好地保證與通信開銷在數(shù)量級上的公平性。同樣的，使用出度通信開銷權(quán)值occw除以出度求得平均直接后繼節(jié)點通信開銷作為通信開銷權(quán)值，與單純使用出度通信開銷作為通信權(quán)值來比可以更公平地做到通信密集情況下的計算差異度與通信傳輸之間的均衡，可以使調(diào)度優(yōu)先權(quán)值ranku具有更好的計算開銷和通信開銷之間的平衡，使調(diào)度算法在不同的異構(gòu)差異環(huán)境下具有更好的穩(wěn)定性。

3.2 處理器分配階段

在處理器分配階段中，將已經(jīng)決定好調(diào)度順序的任務(wù)依次選擇最合適的處理器進行執(zhí)行，HSFT提出了3個具體的策略來順序執(zhí)行，詳細介紹如下。

3.2.1 入口任務(wù)選擇副本策略

傳統(tǒng)的任務(wù)副本算法通常會減少調(diào)度長度，并增加實際運行時的容錯性和穩(wěn)定性，但是也會因為額外的副本增加處理器的負載而影響其他任務(wù)的調(diào)度，降低處理器的效率[13-14]。入口任務(wù)由于是整個調(diào)度算法中執(zhí)行的第一個任務(wù)，即在各處理器均為空載的情況下，采用本算法提出的入口任務(wù)選擇副本策略，可以在不引起處理器過載的情況下，進一步提高整個程序的調(diào)度效率，其他任務(wù)不需要等待入口副本的執(zhí)行而影響自身的運行時間。這種策略對于入口任務(wù)直接后繼節(jié)點傳輸時間遠大于處理器執(zhí)行入口任務(wù)時間的情況極為有效，并且當判斷執(zhí)行入口副本并不會減少調(diào)度時間的情況時，也不會執(zhí)行副本引起延遲。對于入口副本是否執(zhí)行的具體判斷策略如下：

1)只對入口任務(wù)進行如下的副本執(zhí)行判斷機制；

2)首先選擇對入口任務(wù)產(chǎn)生最小EFT的處理器pj執(zhí)行入口任務(wù)；

3)對于其余處理器pi(pi∈P)，如果有入口任務(wù)的直接后繼節(jié)點(immediate successor)vn分配pi執(zhí)行時，進行如式(7)的循環(huán)判斷，如果滿足式(7)則進行pi處理器上的入口任務(wù)復制，否則直接在pi上執(zhí)行vn。

WVentry,i

(7)

當以下兩個條件中任意一個滿足時，上述循環(huán)判斷終止：

條件a 所有處理器均已分配任務(wù)執(zhí)行，意味每個處理器pi的入口副本選擇策略已經(jīng)判斷完成；

條件b 所有vn均已分配處理器執(zhí)行完畢，意味著不需要入口任務(wù)進行傳輸數(shù)據(jù)。

3.2.2 插入機制優(yōu)化策略

插入機制(Insertion-Basedstrategy)最初由HEFT算法提出，后續(xù)的眾多調(diào)度算法都有采用，但均沒有對判定條件進行合理的數(shù)學描述并且在存在多個滿足插入條件的空閑時間縫隙(IdleTimeSlot,ITS)，即任務(wù)完成與下一任務(wù)開始之間的處理器空閑時，HEFT等算法都只是選擇第一個出現(xiàn)的ITS而不是最快完成的。本文對插入機制進行優(yōu)化并詳細描述如下：

1)在每次分配任務(wù)執(zhí)行后，更新每個處理器上的ITS隊列。

2)當任務(wù)vi進行處理器分配時，首先搜尋所有ITS，找出可以滿足條件c并同時滿足條件d的所有ITS。

3)如果存在唯一一個同時滿足條件c和d的ITS，則直接進行插入操作。

4)如果存在多個同時滿足條件c和d的ITS，則選取產(chǎn)生最小EFT的ITS進行插入執(zhí)行任務(wù)vi；

5)當不存在任何同時滿足條件c和d的ITS時，不執(zhí)行插入機制，對任務(wù)vi進行下文的SFT分配策略。

上述策略判斷條件描述如下：

條件cwi, j≤ITS，即在該ITS所在處理器pj上執(zhí)行任務(wù)vi時間小于存在的ITS空閑時間長度；

條件dvi在該ITS所在處理器pj上的EFT小于或等于該ITS的下限時間點，即可以滿足任務(wù)先后續(xù)關(guān)系。

3.2.3 直接后繼節(jié)點完成時間分配策略

對于所有決定了調(diào)度優(yōu)先級的任務(wù)進行具體的處理器分配時，當經(jīng)過上文提到的入口副本選擇和插入機制優(yōu)化策略后，仍未分配處理器的任務(wù)vi遵照直接后繼節(jié)點完成時間SFT(immediate Successors Finish Time)分配策略。相比傳統(tǒng)算法[3-4,6]只考慮最快EFT進行處理器分配，本文算法策略考慮直接后繼節(jié)點的完成時間對于整個調(diào)度結(jié)果的影響，避免了單純考慮任務(wù)自身最快完成時間EFT進行選擇處理器時可能引起后續(xù)通信數(shù)據(jù)傳輸時間過長的不合理問題。首先給出SFT計算公式，如式(8)：

(8)

當任務(wù)vi與直接后繼節(jié)點vj在同一處理器上執(zhí)行，即pw=pk時，ci, j=0，對于出口節(jié)點,SFT(vi,pk)為0。任務(wù)vi進行處理器分配時，選擇滿足EFT(vi,pk)+SFT(vi,pk)的和為最小值的處理器pk執(zhí)行。

3.3 HSFT詳細偽代碼

HSFT詳細偽代碼如下。

輸入:DAG任務(wù)聯(lián)通矩陣與計算開銷矩陣，任務(wù)集V,處理器集合P。 輸出:調(diào)度結(jié)果,調(diào)度完成時間。

1)

從出口節(jié)點開始向上按照式(6)計算每個任務(wù)的ranku值

2)

將所有任務(wù)通過ranku值降序排列形成調(diào)度隊列

3)

While調(diào)度隊列存在任務(wù)時do

4)

選擇調(diào)度隊列最上面的任務(wù)vi

5)

If該任務(wù)為入口任務(wù)

6)

執(zhí)行本文3.2.1節(jié)的入口任務(wù)選擇副本策略

7)

Else(任務(wù)vi不是入口任務(wù))

8)

if 滿足本文3.2.2節(jié)的插入機制優(yōu)化策略條件

9)

對任務(wù)vi進行插入ITS處理器分配

10)

else

11)

for 每個處理器pk∈Pdo

12)

按照式(4)和(8)計算任務(wù)vi的EFT和SFT

13)

end

14)

分配vi到產(chǎn)生最小EFT+SFT的處理器pk上執(zhí)行

15)

End if

16)

End if

17)

更新調(diào)度隊列

18)

End while

3.4 算例分析

由圖1的DAG例圖求得的各算法調(diào)度結(jié)果如圖2，對于該算例的調(diào)度結(jié)果，本文算法HSFT為117，PEFT算法調(diào)度結(jié)果為122，SDBATS調(diào)度結(jié)果為126，HEFT調(diào)度結(jié)果為133。由此可以看出，在與PEFT算法的文獻[5]使用同樣結(jié)構(gòu)和參數(shù)的DAG模型下，HSFT仍然可以得到最為優(yōu)秀的調(diào)度結(jié)果。值得一提的是，HSFT對于處理器p1進行了入口任務(wù)副本選擇策略，選擇處理器p2來執(zhí)行入口任務(wù)，并且對其他處理器進行了判斷。圖2(a)中的p1處理器上的D1即為入口任務(wù)的副本，對于處理器p3，由于判斷在該處理器上執(zhí)行入口任務(wù)副本并不會比在p2上執(zhí)行完入口任務(wù)后再把數(shù)據(jù)傳輸?shù)絧3得到更好的調(diào)度結(jié)果，因此算法沒有對其進行入口任務(wù)副本。這一點與圖2(c)中的SDBATS算法對于所有處理器都進行了入口任務(wù)副本產(chǎn)生了明顯的區(qū)別，HSFT也因此得到了更好的調(diào)度結(jié)果。

HSFT得到的各節(jié)點的ranku值降序排列如表1，即以此權(quán)值的大小決定任務(wù)的調(diào)度優(yōu)先級。各算法的節(jié)點調(diào)度優(yōu)先順序與最終調(diào)度長度如表2。另一個使得HSFT優(yōu)于其他算法調(diào)度結(jié)果的原因是對于任務(wù)3得到了相對于任務(wù)4更優(yōu)先的調(diào)度順序。這是由于本文3.1節(jié)改良的優(yōu)先級計算公式，使得計算開銷差異較大或平均出度通信開銷較大的任務(wù)都可以得到更為公平的調(diào)度順序。

圖2 各算法調(diào)度結(jié)果

表1 HSFT任務(wù)調(diào)度權(quán)值

Tab.1 Priority weights of tasks in HSFT

任務(wù)ranku(vi)任務(wù)ranku(vi)v1787．7v6471．0v2432．8v7344．7v3588．0v8379．8v4406．0v9266．9v5427．0v10182．0

表2 各算法調(diào)度任務(wù)順序與調(diào)度長度

對于V個任務(wù)和P個處理器，HSFT和比較算法HEFT、SDBATS及PEFT有著同樣的時間復雜度O(v2,p)。具體分析如下：當計算ranku值時其時間復雜度為O(v2*p)，在分配處理器階段計算EFT的復雜度為O(v*P)，計算SFT的復雜度為O(v2*p)，因此整個算法時間復雜度為O(v2*p+v*P+v2*p)，即為O(v2,p)。

4 實驗與結(jié)果分析

本章給出在隨機生成DAG實驗中，HSFT和上述各個比較算法的具體實驗結(jié)果。首先介紹幾個衡量實驗性能的比較參數(shù)。最常見的衡量DAG調(diào)度結(jié)果的參數(shù)就是式(2)介紹的調(diào)度長度makespan，但是由于DAG任務(wù)節(jié)點數(shù)與屬性不同，有必要給出一個參考標準，使用調(diào)度長度與理論調(diào)度完成時間的比值，即為調(diào)度長度比(Schedule Length Ratio, SLR)，如式(9)所示：

(9)

式(9)的分母為所有關(guān)鍵路徑節(jié)點在各自最快完成的處理器上執(zhí)行時間累加值，完全忽略在不同處理器間通信所產(chǎn)生的傳輸時間，即調(diào)度的理想下限時間。因此在實驗比較中，效果更好的調(diào)度算法會得到更小的SLR值，但SLR永遠不會小于1。

加速比為串行調(diào)度時間與并行調(diào)度時間之比，見式(10)，即為當所有任務(wù)在同一處理器順序完成的時間最小值除以算法的調(diào)度時間：

(10)

效率值(Efficiency) 定義為加速比除以參與運行的處理器個數(shù)。理論上，隨著處理器的個數(shù)增加，加速比會越來越大，因此采用效率值作為評估參數(shù)可以更合理地判斷算法的效率，越好的算法其調(diào)度效率值越高。

本文使用本課題組研發(fā)的DAG生成仿真程序[15]，生成用于隨機DAG實驗中的測試用例。采用和文獻[5]同樣的隨機生成DAG參數(shù)，具體包括：任務(wù)節(jié)點數(shù)v(number of tasks)、形狀參數(shù)fat(shape parameter)、勻稱參數(shù)regularity(symmetry parameter)、邊密度參數(shù)density(number of edge factor)、跳躍跨度jump(the degree of leaping)、通信計算比CCR(Communication to Computation Ratio)以及異構(gòu)計算差異參數(shù)η(Range percentage of computation cost)。

density值用來定義兩層DAG節(jié)點之間邊的數(shù)量，低的取值意味著整個DAG生成的邊越少，反之取高的值會產(chǎn)生更多的邊。邊密度參數(shù)確定了各層節(jié)點間的連通性，即影響出度通信開銷權(quán)值和對通信密集型任務(wù)的判斷。

regularity值用來定義每層節(jié)點的均勻度，取值越小會造成各層節(jié)點的數(shù)量差異過大，即不均勻。反之則會讓各層之間的節(jié)點數(shù)量相近，整體得到一個均勻的DAG結(jié)構(gòu)。

jump值表示一個節(jié)點向下聯(lián)通的跳躍度，即從當前節(jié)點所在層向下的跨度，當jump取1時，每個節(jié)點正常連接下一層節(jié)點，取2即可以跨過1層而連接下2層的節(jié)點。

CCR用于決定DAG任務(wù)的通信開銷與計算開銷之間的比例關(guān)系，通常來說，該值由所有通信開銷矩陣的有效聯(lián)通邊的均值與計算開銷矩陣所有有效值的均值相比得到，CCR值較大表示DAG為一個通信密集型程序；反之，CCR值較小，即為計算密集型DAG。

異構(gòu)計算差異參數(shù)η反映了異構(gòu)計算環(huán)境下處理器之間的速度差異。通常在一個[0,2*Wdag]的范圍內(nèi)，隨機選取每個任務(wù)vi計算開銷的初始值wi，其中Wdag是最初給定的整個DAG計算開銷初始值。每個任務(wù)vi在每個處理器pj上的計算開銷wi, j則在式(11)的范圍內(nèi)選?。?/p>

wi×(1-η/2)≤wi, j≤wi×(1+η/2)

(11)

本文實驗各DAG生成參數(shù)取值范圍為：v={10,20,30,40,50,60,70,80,90,100,200,300,400,500}；CCR={0.1,0.5,0.8,1,2,5,10}；η={0.1,0.2,0.5,1,2}；jump={1,2,4}；regularity={0.2,0.8}；fat={0.1,0.4,0.8}；density={0.2,0.8}；處理器個數(shù)Processors={4,8,16,32}。上述參數(shù)組合共生成70 560個DAG模型，對于每個DAG模型再隨機生成10個具體DAG，因此共有705 600個隨機DAG用于實驗測試。具體實驗結(jié)果如圖3～6：圖3給出了不同任務(wù)數(shù)v下的各算法調(diào)度結(jié)果的平均SLR；圖4給出不同通信計算比CCR下的各算法調(diào)度結(jié)果的平均SLR；圖5給出不同異構(gòu)參數(shù)η下的各算法調(diào)度結(jié)果的平均SLR；圖6給出了不同處理器數(shù)下各算法調(diào)度的平均效率值。本文對所有實驗結(jié)果進行了標準偏差的實驗誤差估計，其誤差范圍大致在3%到6%之間。

圖3 不同任務(wù)數(shù)下的平均SLR

圖4 不同CCR下的平均SLR

圖5 不同異構(gòu)參數(shù)下的平均SLR

圖3可以看出，在任務(wù)數(shù)逐漸增大的情況下，本文算法在SLR上要比其他算法都小，對比PEFT算法，在10任務(wù)時優(yōu)勢接近11%，在500任務(wù)時優(yōu)勢也達到6%左右。圖4和圖5可以看出，在CCR和異構(gòu)參數(shù)不斷增加的情況下，本文算法的SLR均小于其他算法，并且隨著參數(shù)取值的增加，算法的優(yōu)勢逐漸明顯。在最高的CCR取值時，優(yōu)勢達到8%左右；在最高的異構(gòu)參數(shù)取值為2的情況下，優(yōu)勢也接近5%。雖然本文算法目標是異構(gòu)差異度較大情況下的調(diào)度優(yōu)化，但通過圖5實驗結(jié)果可以看到，算法在異構(gòu)差異較小的情況下相對其他算法也有一定的優(yōu)勢。從圖6可以看出在不同處理器數(shù)目下，本文算法效率值也高于其他算法，優(yōu)勢最高可以達到9%左右。PEFT算法由于通過預測機制，優(yōu)先考慮子節(jié)點在串行權(quán)值較大情況下的調(diào)度優(yōu)先性，所以在比較窄的DAG中占有一定優(yōu)勢，但是在并行度比較大的DAG中，這個優(yōu)勢就并不明顯，尤其在計算開銷差異較大和子節(jié)點通信并行度較高的情況下，PEFT算法往往不占優(yōu)勢，甚至并不優(yōu)于HEFT算法。值得一提的是，為了更好地與PEFT算法進行比較實驗，本文的隨機DAG生成參數(shù)選取與PEFT文獻完全一樣。對于fat值，PEFT算法文獻選取參數(shù)沒有超過1，意味著生成的DAG是過于串行的，這有利于該算法的調(diào)度結(jié)果，而事實上這樣的隨機參數(shù)選取范圍不盡合理。SDBATS算法在大部分情況下得到的調(diào)度結(jié)果優(yōu)于HEFT，但是由于算法本身缺少插入機制，以及過于注重計算開銷差異，導致在通信開銷較大情況下并沒有優(yōu)勢。HEFT算法作為最經(jīng)典的調(diào)度算法，其調(diào)度的效果相對比較穩(wěn)定。

圖6 不同處理器數(shù)目下的效率值

總之，在各種參數(shù)的DAG模型下，HSFT的SLR和效率值都要好于其他比較算法，尤其在異構(gòu)度大的情況下，HSFT的優(yōu)勢更加明顯，這是因為本文算法更注重計算開銷的差異性以及計算開銷與通信開銷兩者間的平衡，并且采用更合理的SFT處理器選擇策略。

5 結(jié)語

本文提出了一種異構(gòu)環(huán)境下的DAG調(diào)度算法——HSFT，在考慮充分平衡計算與通信差異對優(yōu)先級影響的基礎(chǔ)上，以直接后繼節(jié)點的完成時間作為處理器選擇的衡量標準，算法在異構(gòu)差異度較大的DAG調(diào)度中具有明顯的優(yōu)勢。在各種參數(shù)的隨機DAG實驗下，HSFT的調(diào)度長度、調(diào)度比SLR和效率值都要好于現(xiàn)有的PEFT、SDBATS及HEFT算法；同時，HSFT具有和本文其他比較算法相同的時間復雜度O(v2,p)。

References)

[1] MAHESWARAN M, BRAUN T D, SIEGEL H J.Heterogeneous distributed computing [J].Encyclopedia of Electrical and Electronics Engineering, 1999, 8: 679-690.

[2] KWOK Y K, AHMAD I.Benchmarking the task graph scheduling algorithms [C]// IPPS/SPDP 1998: Proceedings of the First Merged International and Symposium on Parallel and Distributed Processing.Piscataway, NJ: IEEE, 1998: 531-537.

[3] TOPCUOGLU H, HARIRI S, WU M.Performance-effective and low-complexity task scheduling for heterogeneous computing [J].IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274.

[4] MUNIR E U, MOHSIN S, HUSSAIN A, et al.SDBATS: a novel algorithm for task scheduling in heterogeneous computing systems [C]// IPDPSW 2013: Proceedings of the IEEE 27th International Parallel and Distributed Processing Symposium Workshops & PhD Forum.Piscataway, NJ: IEEE, 2013: 43-53.

[5] ARABNEJAD H, BARBOSA J G.List scheduling algorithm for heterogeneous systems by an optimistic cost table [J].IEEE Transactions on Parallel and Distributed Systems, 2014, 25(3): 682-694.

[6] WANG G, WANG Y, LIU H, et al.HSIP: a novel task scheduling algorithm for heterogeneous computing [J].Scientific Programming, 2016, 2016: Article ID 3676149.

[7] KIM J K, SHIVLE S, SIEGEL H J, et al.Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment [J].Journal of Parallel and Distributed Computing, 2007, 67(2): 154-169.

[8] BARBOSA J G, MOREIRA B.Dynamic scheduling of a batch of parallel task jobs on heterogeneous clusters [J].Parallel Computing, 2011, 37(8): 428-438.

[9] HOU E S H, ANSARI N, REN H.A genetic algorithm for multiprocessor scheduling [J].IEEE Transactions on Parallel and Distributed Systems, 1994, 5(2): 113-120.

[10] DHODHI M K, AHMAD I, YATAMA A, et al.An integrated technique for task matching and scheduling onto distributed heterogeneous computing systems [J].Journal of Parallel and Distributed Computing, 2002, 62(9): 1338-1361.

[11] DAOUD M I, KHARMA N.A high performance algorithm for static task scheduling in heterogeneous distributed computing systems [J].Journal of Parallel and Distributed Computing, 2008, 68(4): 399-409.

[12] ILAVARASAN E, THAMBIDURAI P.Low complexity perform-ance effective task scheduling algorithm for heterogeneous computing environments [J].Journal of Computer Science, 2007, 3(2): 94-103.

[13] CALHEIROS R N, BUYYA R.Meeting deadlines of scientific workflows in public clouds with tasks replication [J].IEEE Transactions on Parallel & Distributed Systems, 2014, 25(7): 1787-1796.

[14] BANSAL S, KUMAR P, SINGH K.An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems [J].IEEE Transactions on Parallel and Distributed Systems, 2003, 14(6): 533-544.

[15] 王宇新,曹仕杰,郭禾,等.兼顧費用與公平的帶通信開銷的多有向無環(huán)圖調(diào)度[J].計算機應(yīng)用,2015,35(11):3017-3020.(WANG Y X, CAO S J, GUO H, et al.Communication aware multiple directed acyclic graph scheduling considering cost and fairness [J].Journal of Computer Applications, 2015, 35(11): 3017-3020.)

This work is partially supported by the National Natural Science Foundation of China (11372067, 61300016).

WANG Guan, born in 1984, Ph.D.candidate, lecturer.His research interests include computer system architecture, parallel computing.

WANG Yuxin, born in 1973, Ph.D., associate professor.His research interests include computer system architecture, parallel computing.

CHEN Xin, born in 1983, Ph.D., lecturer.His research interests include combinatorial optimization and scheduling.

WANG Fei, born in 1993, M.S.candidate.His research interests include computer system architecture, system simulation.

GUO He, born in 1955, M.S., professor.His research interests include computer system architecture.

Heterogeneous scheduling algorithm with immediate successor finish time

WANG Guan1,2, WANG Yuxin3*, CHEN Xin1, WANG Fei3, GUO He1

(1.SchoolofSoftwareTechnology,DalianUniversityofTechnology,DalianLiaoning116620,China;2.DepartmentofPoliceInformation,LiaoningPoliceCollege,DalianLiaoning116036,China;3.SchoolofComputerScienceandTechnology,DalianUniversityofTechnology,DalianLiaoning116024,China)

In the era of big data, data intensive computing always relies on distributed Heterogeneous Computing System (HCS), and an effective task scheduling method can improve the efficiency of a HCS.Based on a Directed Acyclic Graph (DAG) model, a task scheduling algorithm for heterogeneous computing named HSFT (Heterogeneous scheduling algorithm with immediate Successor Finish Time) was proposed.In the heterogeneous environment, especially when the computation cost and communication cost vary largely, the balance between them was considered and a more reasonable method was adopted, the product of the computation cost standard deviation and mean value was taken as the computation weight, and the ratio between the out degree communication cost weight and out degree was taken as the communication weight.Furthermore, based on the consideration of Earliest Finish Time (EFT), the immediate Successor Finish Time (SFT) was used for processor selection strategy.The experimental results on randomly generated DAGs show that the proposed algorithm performs better than HEFT (Heterogeneous Earliest Finish Time), SDBATS (Standard Deviation-Based Algorithm for Task Scheduling) and PEFT (Predict Earliest Finish Time) in terms of makespan, schedule length ratio, and efficiency without increasing time complexity.

Directed Acyclic Graph (DAG) scheduling; heterogeneous computing; task priority; immediate successor; static task scheduling

2016-08-20;

2016-09-02。 基金項目:國家自然科學基金資助項目(11372067,61300016)。

王冠(1984—)，男，遼寧大連人，講師，博士研究生，CCF會員，主要研究方向：計算機系統(tǒng)結(jié)構(gòu)、并行計算; 王宇新(1973—)，男，遼寧大連人，副教授，博士，CCF會員，主要研究方向：計算機系統(tǒng)結(jié)構(gòu)、并行計算； 陳鑫(1983—)，男，遼寧錦州人，講師，博士，主要研究方向：組合優(yōu)化與調(diào)度； 王飛(1993—)，男，山東棗莊人，碩士研究生，主要研究方向：計算機系統(tǒng)結(jié)構(gòu)、系統(tǒng)仿真； 郭禾(1955—)，男，遼寧大連人，教授，碩士，主要研究方向：計算機系統(tǒng)結(jié)構(gòu)。

1001-9081(2017)01-0012-06

10.11772/j.issn.1001-9081.2017.01.0012

TP393.01

A