基于直接后繼節(jié)點完成時間的異構調度算法

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

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

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

基于直接后繼節(jié)點完成時間的異構調度算法

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

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

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

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

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

0 引言

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

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

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

1 相關工作

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

對于靜態(tài)調度的問題模型來說，每個任務的計算和通信開銷以及整個任務間的連接關系都是已知的。算法可以在編譯時間內，根據上述已知的參數給出一個理想的調度結果。通常也將靜態(tài)調度算法分為兩大類：導向隨機搜索機制算法(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)。聚類算法通常適合在同構計算環(huán)境下的調度，對于異構環(huán)境的調度效果有限。副本算法通常會得到較好的調度結果，但同樣也會產生更高的算法復雜度。此外，副本會引起更多的處理器占用問題，這不僅會增加額外的處理器能耗開銷，更會耽誤其他任務對于資源的共享，影響整體的優(yōu)化調度。表調度算法相對來說有著更好的調度性能、更低的算法復雜度，是靜態(tài)調度中最為流行的調度算法。典型的表調度啟發(fā)式調度算法有HEFT[3]、SDBATS[4]、PEFT[5]、HSIP[6]、LDCP(Longest Dynamic Critical Path)[11]和PETS(low complexity Performance Effective Task Scheduling)[12]等。

2 異構環(huán)境下的任務調度模型

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

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

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

(1)

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

定義1 調度長度(makespan)表示DAG中最后一個任務的完成時間，如式(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可以開始運行任務的最早時間，pred(vi)表示任務vi的所有直接前驅節(jié)點，即任務vi在處理器pj上最快開始運行時間，為處理器可以運行時間與前驅節(jié)點傳輸數據完成時間兩者之間的較大值，當前驅節(jié)點vm和vi在同一處理器運行時，cm, j=0。對于入口節(jié)點，不考慮處理器啟動時間的情況下，最快開始時間EST(ventry,pj)=0。

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

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

(4)

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

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

(5)

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

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

3 HSFT

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

3.1 任務調度優(yōu)先級階段

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

(6)

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

3.2 處理器分配階段

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

3.2.1 入口任務選擇副本策略

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

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

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

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

WVentry,i

(7)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(8)

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

3.3 HSFT詳細偽代碼

HSFT詳細偽代碼如下。

輸入:DAG任務聯通矩陣與計算開銷矩陣，任務集V,處理器集合P。 輸出:調度結果,調度完成時間。

1)

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

2)

將所有任務通過ranku值降序排列形成調度隊列

3)

While調度隊列存在任務時do

4)

選擇調度隊列最上面的任務vi

5)

If該任務為入口任務

6)

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

7)

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

8)

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

9)

對任務vi進行插入ITS處理器分配

10)

else

11)

for 每個處理器pk∈Pdo

12)

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

13)

end

14)

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

15)

End if

16)

End if

17)

更新調度隊列

18)

End while

3.4 算例分析

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

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

圖2 各算法調度結果

表1 HSFT任務調度權值

Tab.1 Priority weights of tasks in HSFT

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

表2 各算法調度任務順序與調度長度

對于V個任務和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 實驗與結果分析

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

(9)

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

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

(10)

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

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

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

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

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

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

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

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

(11)

本文實驗各DAG生成參數取值范圍為：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}；處理器個數Processors={4,8,16,32}。上述參數組合共生成70 560個DAG模型，對于每個DAG模型再隨機生成10個具體DAG，因此共有705 600個隨機DAG用于實驗測試。具體實驗結果如圖3～6：圖3給出了不同任務數v下的各算法調度結果的平均SLR；圖4給出不同通信計算比CCR下的各算法調度結果的平均SLR；圖5給出不同異構參數η下的各算法調度結果的平均SLR；圖6給出了不同處理器數下各算法調度的平均效率值。本文對所有實驗結果進行了標準偏差的實驗誤差估計，其誤差范圍大致在3%到6%之間。

圖3 不同任務數下的平均SLR

圖4 不同CCR下的平均SLR

圖5 不同異構參數下的平均SLR

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

圖6 不同處理器數目下的效率值

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

5 結語

本文提出了一種異構環(huán)境下的DAG調度算法——HSFT，在考慮充分平衡計算與通信差異對優(yōu)先級影響的基礎上，以直接后繼節(jié)點的完成時間作為處理器選擇的衡量標準，算法在異構差異度較大的DAG調度中具有明顯的優(yōu)勢。在各種參數的隨機DAG實驗下，HSFT的調度長度、調度比SLR和效率值都要好于現有的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)圖調度[J].計算機應用,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)結構、并行計算; 王宇新(1973—)，男，遼寧大連人，副教授，博士，CCF會員，主要研究方向：計算機系統(tǒng)結構、并行計算； 陳鑫(1983—)，男，遼寧錦州人，講師，博士，主要研究方向：組合優(yōu)化與調度； 王飛(1993—)，男，山東棗莊人，碩士研究生，主要研究方向：計算機系統(tǒng)結構、系統(tǒng)仿真； 郭禾(1955—)，男，遼寧大連人，教授，碩士，主要研究方向：計算機系統(tǒng)結構。

1001-9081(2017)01-0012-06

10.11772/j.issn.1001-9081.2017.01.0012

TP393.01

A