劉林東，鄔依林

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

相關任務一般用有向無環(huán)圖(Directed Acyclic Graph,DAG)[1-2]表示，區(qū)別于獨立任務的特點是只有當前任務的所有前驅任務執(zhí)行完成后，才能調(diào)度當前任務。相關任務調(diào)度根據(jù)DAG的數(shù)量一般分為單DAG任務調(diào)度和多DAG任務調(diào)度兩種，近年以來，單DAG任務調(diào)度在分布式異構環(huán)境中的研究取得了較多的研究成果，通常不能將這些調(diào)度策略直接應用在多DAG任務調(diào)度問題中。

分布式異構計算環(huán)境下的任務調(diào)度問題[3]以及多DAG任務調(diào)度問題是現(xiàn)有任務調(diào)度的熱點[4-5]，任務調(diào)度模型以及任務調(diào)度算法一般從任務排序以及任務調(diào)度兩方面進行了一些優(yōu)化，對約束條件較多的多DAG調(diào)度，如提交的DAG時間不一致以及限定任務調(diào)度的完成時間等，以及如何動態(tài)地對多個DAG任務進行調(diào)，兼顧多個DAG之間調(diào)度的公平性以及資源利用率等問題，需要對這些問題進一步開展研究工作。

相關任務的調(diào)度算法主要包括HEFT算法[6-7]、MCP算法、ETF算法、CPOP算法[8]、LBP算法、DSC[9]算法、DCP[10]算法、DSH算法、CPFD[11]算法、Fairness[12]算法、Backfill算法、遺傳算法以及模擬退火算法等。

1 問題描述

以下分別從任務描述、資源環(huán)境以及任務調(diào)度目標等幾個方面對分布式異構計算環(huán)境下相關任務調(diào)度問題進行描述。

1.1 任務描述

圖1 多DAG任務圖Fig.1 Multi-DAG task graph

1.2 資源環(huán)境

1.3 任務調(diào)度目標

3)整個任務集在處理機上的執(zhí)行時間最短，即makespan值盡可能??；

5)任務調(diào)度算法穩(wěn)定性更好，計算并對比各種任務調(diào)度算法的Slack值，評估和選擇Slack值更小的任務調(diào)度算法。其中Slack是一個關于任務調(diào)度算法魯棒性的度量，反映的是一個任務調(diào)度算法產(chǎn)生的任務處理時間的不確定程度，Slack的定義如式(1)所示。其中M表示DAG的跨度makespan，n表示任務數(shù)量，blevel表示任務ti到出口節(jié)點最長路徑的長度，tlevel表示從入口節(jié)點到任

務ti(不包含任務ti)最長路徑的長度。

(1)

2 MDTS任務調(diào)度模型

提出了一種分布式異構環(huán)境下的多DAG任務調(diào)度模型，如圖2所示。MDTS任務調(diào)度模型在進行任務調(diào)度和處理機選擇時分三個階段完成，分別為DAG合并、任務排序以及任務調(diào)度。

圖2 多DAG任務調(diào)度模型Fig.2 Task scheduling model of multi-DAG

2.1 多DAG合并

首先對多個DAG任務圖進行合并，合并的方法是增加一個虛擬的入口任務節(jié)點和出口任務節(jié)點。入口任務節(jié)點同時作為每個子DAG入口任務節(jié)點的父親節(jié)點，出口節(jié)點同時作為每個子DAG圖出口任務節(jié)點的子任務節(jié)點，然后更新虛擬入口任務節(jié)點和出口任務節(jié)點與相關任務節(jié)點的通信開銷和計算代價，多DAG任務圖合并后的效果如圖3所示。

圖3 多DAG合并后Fig.3 The combined result of multi-DAG

2.2 任務排序

用合并后的任務在各個處理機上計算代價的二次方差以及通信成本作為參數(shù)對DAG任務進行排序。任務計算代價的方差以及通信成本越大，任務在不同的處理機上的調(diào)度時間差異就越大，給任務賦予較高的優(yōu)先級，相反，則賦予較小的優(yōu)先級，任務ti計算代價的方差及通信成本δi計算如下：

(2)

2.3 處理機選擇與任務調(diào)度

根據(jù)已排序好的任務集，按從高到低的順序依次對任務集進行調(diào)度，按HEFT算法中的任務調(diào)度策略對處理機進行選擇與調(diào)度。

3 MDTS任務調(diào)度算法

3.1 處理機選擇

在處理機選擇方面，在計算完每個DAG任務在各個處理機上計算代價的二次方差以及通信成本后，按HEFT算法中的任務調(diào)度策略將任務調(diào)度到相應的處理機執(zhí)行，即在處理器選擇階段，先對滿足任務復制條件的任務節(jié)點進行任務復制[13-14]，從而減少相關任務之間的通信開銷，再按HEFT算法將任務調(diào)度到使任務完成時間最早的處理機上執(zhí)行。

3.2 調(diào)度算法

多DAG任務調(diào)度MDTS算法如表1所示，算法將DAG任務模型以及任務在處理機計算資源上的計算代價作為算法的輸入，算法的輸出是各個DAG中的任務與處理機對應的調(diào)度關系以及任務調(diào)度跨度、任務調(diào)度平均等待時間以及平均Slack值等。

3.3 算法性能分析

MDTS任務調(diào)度算法的各個步驟的時間復雜度分別如下：

1) 增加入口任務節(jié)點和出口任務節(jié)點子程序的時間復雜度為O(p)；

表1 MDTS算法Table 1 MDTS algorithm

4 仿真實驗與結果分析

4.1 實驗目的

為了驗證文中提出的MDTS算法，在相同的實驗條件下對提出的MDTS算法與同類調(diào)度算法Sequential和Interleave算法進行性能比較，主要比較任務跨度makespan、任務平均等待時間AWT以及平均Slack值。

4.2 模擬環(huán)境

在模擬實驗環(huán)境中，設定一個分布式異構計算環(huán)境下的處理機對應一個處理機，因此可以將整個分布式異構處理機模擬成SimGrid[15-17]環(huán)境下的集群環(huán)境，基于SimGrid提供的模擬器工具包，構建一個分布式異構計算的仿真環(huán)境。其中：

(i) 處理機之間通過高速網(wǎng)絡互連；

(ii) 每個處理機可同時進行任務執(zhí)行和與其它處理機通信，而不需要爭用；

(iii) 任務在處理機上執(zhí)行是非搶占的；

(iv) 每個處理機之間是性能異構的，即同一個任務在不同處理機上執(zhí)行存在差異性。

實驗中使用的計算機配置為：Intel Core i5-3210M@2.5GHz雙核筆機本處理機，8 G內(nèi)存。本章實驗采用的處理機分別取3個和4個。

4.3 任務調(diào)度過程分析

以2個DAG任務圖為例，以下詳細分析MDTS相關任務調(diào)度算法實現(xiàn)多DAG任務圖的合并以及在分布式異構計算環(huán)境下的調(diào)度過程。

4.3.1 DAG初始化 圖4表示包含兩個DAG圖的多DAG任務圖。其中DAG1中包括有7個任務，DAG2中包括有4個任務。帶箭頭的邊表示任務之間的通信邊，邊上的數(shù)字表示兩個任務之間的通信代價ci,j。DAG1的入口節(jié)點為a1，出口節(jié)點為和a7；DAG2的入口節(jié)點為b1，出口節(jié)點為b4。表2、表3分別表示DAG1、DAG2中的任務在不同處理機上的計算時間ET(ti,cj)，表2、表3中包括3個處理機P0～P2，其中通信代價和執(zhí)行時間的單位為 s。

圖4 多DAG任務圖Fig.4 Task graph of multi-DAG

任務P0P1P2a112168a210157a3152010a49126a513189a67105a7162311

表3 DAG2任務集在處理機集上的調(diào)度時間Table 3 Scheduling time of DAG2 task set on processor set

4.3.2 合并DAG任務圖 通過添加一個入口任務節(jié)點和出口任務節(jié)點將圖4中的DAG1和DAG2合并在一起，產(chǎn)生一個新的DAG圖，合并的步驟為：

(i) 添加一個入口任務節(jié)點entry，將入口任務節(jié)點entry分別與DAG1、DAG2的入口任務節(jié)點a1、b1相連，設通信代價為0.01；entry任務節(jié)點在處理機上的執(zhí)行時間均為0.01；

(ii) 添加一個出口任務節(jié)點exit，將出口任務節(jié)點exit分別與DAG1、DAG2的出口任務節(jié)點a7、b4相連，設通信代價為0.01；節(jié)點在處理機上的執(zhí)行時間都為0.01；

(iii) 保留DAG1和DAG2中的其余節(jié)點之間的關系、通信開銷以及執(zhí)行代價，合并后的新DAG如圖5所示，合并后的任務在處理機上的計算時間ET(ti,cj)如表4所示。

4.3.3 依賴關系矩陣 根據(jù)合并后的DAG任務圖，生成任務之間對應的依賴關系矩陣，如表5所示。依賴關系矩陣的定義為：

(i)若節(jié)點i為節(jié)點j的前驅節(jié)點，則矩陣元素di,j=ci,j；

圖5 合并后DAG任務圖Fig.5 Combined DAG task graph

任務P0P1P2entry0.010.010.01a112168b113158a210157a3152010b214179b3182312a49126a513189a67105b4152211a7162311exit0.010.010.01

(ii)若節(jié)點i和節(jié)點j之間不存在依賴關系，則矩陣元素di,j=0；

(iii)由于DAG中節(jié)點之間的依賴關系，當i≥j時，di,j=0。

4.3.4 任務排序 計算每個任務ai計算代價的方差以及通信開銷δi，并降序進行排序，計算及排序的結果如表6所示。

4.3.5 任務調(diào)度 任務集經(jīng)過MDTS算法調(diào)度之后，任務與處理機的對應調(diào)度關系如圖6(a)所示，圖6(b)、(c)分別表示同一任務集通過Sequential、Interleave算法[18]調(diào)度的對應關系。

4.4 實驗結果分析

利用3種算法分別對10個DAG任務圖進行調(diào)度，表7為三種算法分別在在3個處理機、4個處理機情況下Slack值的對比情況。

表5 依賴關系矩陣Table 5 Dependency matrix

表6 任務的δi值Table 6 The δi of each task

表7 MDTS、Sequential、Interleave算法的Slack值Table 7 Slack value of MDTS, Sequential and Interleave algorithms

根據(jù)δi的值按降序進行排序，產(chǎn)生任務集的任務調(diào)度序列如：entry,a1,b1,a3,a2,a6,a5,b3,b2,a4,a7,b4,exit。

圖6 三種算法任務調(diào)度對比Fig.6 Comparison of three algorithms for task scheduling

4.4.1 3個處理機情況 分別采用3種算法對多個DAG任務集進行調(diào)度，在處理機的數(shù)量為3的情況下，針對不同數(shù)量DAG任務模型進行調(diào)度，得到所有任務的跨度(調(diào)度長度)makespan平均等待時間AWT值以及平均Slack，如圖7(a)、圖7(b)、圖8所示。

圖7 不同DAG的任務對比圖Fig.7 Comparison of task for different DAGs

圖8 不同DAG的任務平均Slack對比Fig.8 Task average Slack comparison of different DAGs

圖7(a)的縱坐標為算法所獲得的調(diào)度跨度makespan值，橫坐標為DAG數(shù)量；圖7(b)的縱坐標為算法所獲得的調(diào)度跨度平均等待時間AWT值，橫坐標為DAG數(shù)量。從實驗數(shù)據(jù)得出，在任務調(diào)度的跨度和任務平均等待時間方面，隨著DAG數(shù)量的增加，均會相應的增加?？傮w來說，MDTS算法的性能最佳，Interleave算法的性能其次，Sequential算法的性能最差。MDTS算法和Interleave算法在1個DAG時跨度相等，最高降低了27.0%；MDTS算法和Sequential算法在1個DAG時跨度相等，最高降低了21.2%；在任務平均等待時間方面，MDTS算法在幾種情況下比Interleave算法的等待時間稍長，最高降低了6.6%，MDTS算法和Sequential算法在1個DAG時相等，最高降低了55.0%。

圖8中縱坐標為算法所獲得的平均Slack值，橫坐標為DAG數(shù)量，從圖8可以看出，隨著DAG數(shù)量的增加，MDTS、Sequential和Interleave算法的Slack值變化不明顯，但是橫向比較可以看出MDTS相對Sequential和Interleave算法有更低的Slack值，MDTS算法的Slack值最高比Sequential算法要減少53.6%，比Interleave算法要減少18.8%。

4.4.2 4個處理機情況 分別采用3種算法對多個DAG任務集進行調(diào)度，在處理機的數(shù)量為4的情況下，針對不同數(shù)量DAG任務模型進行調(diào)度，得到所有任務的跨度(調(diào)度長度)makespan、平均等待時間AWT值以及平均Slack值，如圖9(a)、圖9(b)、圖10所示。

圖9 不同DAG的任務對比圖Fig.9 Comparison of task for different DAGs

圖10 不同DAG的任務平均Slack對比Fig.10 Task average slack comparison of different DAGs

圖9(a)的縱坐標為算法所獲得的調(diào)度跨度makespan值，橫坐標為DAG數(shù)量；圖9(b)的縱坐標為算法所獲得的調(diào)度跨度平均等待時間AWT值，橫坐標為DAG數(shù)量。從實驗數(shù)據(jù)得出，在任務調(diào)度的跨度和任務平均等待時間方面，隨著DAG數(shù)量的增加，任務調(diào)度的跨度會相應的增加；相比3個處理機情況，4個處理機的任務調(diào)用跨度和平均等待時間相對較小?？傮w來說，MDTS算法的性能最佳，Interleave算法的性能其次，Sequential算法的性能最差。MDTS算法和Interleave算法在1個DAG時跨度相等，最高降低了39.0%；MDTS算法和Sequential算法在1個DAG時跨度相等，最高降低了64.1%；在任務平均等待時間方面，MDTS算法在幾種情況下比Interleave算法的等待時間稍長，最高降低了16.3%，MDTS算法和FCFS算法在1個DAG時相等，最高降低了61.8%。圖10中縱坐標為算法所獲得的平均Slack值，橫坐標為DAG數(shù)量，從圖10可以看出，隨著DAG數(shù)量的增加，MDTS、Sequential和Interleave算法的Slack值變化不明顯，但是橫向比較可以看出MDTS相對Sequential和Interleave算法有更低的Slack值，MDTS算法的Slack值最高比FCFS算法要減少59.1%，比Interleave算法要減少23.1%。

通過兩組實驗分析得出，MDTS算法在任務調(diào)度跨度、任務調(diào)度平均等待時間以及平均Slack方面均優(yōu)于Sequential、Interleave算法?？傮w來講，4個處理機下的任務調(diào)度比3個處理機環(huán)境下的任務調(diào)度效果更佳，MDTS算法在4個處理機環(huán)境中的性能比3個處理機環(huán)境下的性能更好。

5 小 結

文中首先對多個DAG任務進行合并，將多個DAG任務合并為一個DAG，在此基礎上，提出了一種相關任務調(diào)度模型和相關任務調(diào)度算法MDTS算法。通過實驗以及案例分析過程，MDTS算法在任務調(diào)度跨度、任務調(diào)度平均等待時間以及平均Slack方面均優(yōu)于Sequential、Interleave算法。