多DAG任務(wù)調(diào)度算法

劉林東，鄔依林

(廣東第二師范學(xué)院計(jì)算機(jī)科學(xué)系，廣東 廣州 510303)

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

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

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

1 問題描述

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

1.1 任務(wù)描述

圖1 多DAG任務(wù)圖Fig.1 Multi-DAG task graph

1.2 資源環(huán)境

1.3 任務(wù)調(diào)度目標(biāo)

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

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

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

(1)

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

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

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

2.1 多DAG合并

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

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

2.2 任務(wù)排序

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

(2)

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

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

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

3.1 處理機(jī)選擇

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

3.2 調(diào)度算法

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

3.3 算法性能分析

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

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

表1 MDTS算法Table 1 MDTS algorithm

4 仿真實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)?zāi)康?/h3>

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

4.2 模擬環(huán)境

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

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

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

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

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

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

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

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

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

圖4 多DAG任務(wù)圖Fig.4 Task graph of multi-DAG

任務(wù)P0P1P2a112168a210157a3152010a49126a513189a67105a7162311

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

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

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

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

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

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

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

圖5 合并后DAG任務(wù)圖Fig.5 Combined DAG task graph

任務(wù)P0P1P2entry0.010.010.01a112168b113158a210157a3152010b214179b3182312a49126a513189a67105b4152211a7162311exit0.010.010.01

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

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

4.3.4 任務(wù)排序 計(jì)算每個任務(wù)ai計(jì)算代價(jià)的方差以及通信開銷δi，并降序進(jìn)行排序，計(jì)算及排序的結(jié)果如表6所示。

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

4.4 實(shí)驗(yàn)結(jié)果分析

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

表5 依賴關(guān)系矩陣Table 5 Dependency matrix

表6 任務(wù)的δ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的值按降序進(jìn)行排序，產(chǎn)生任務(wù)集的任務(wù)調(diào)度序列如：entry,a1,b1,a3,a2,a6,a5,b3,b2,a4,a7,b4,exit。

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

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

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

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

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

圖8中縱坐標(biāo)為算法所獲得的平均Slack值，橫坐標(biāo)為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個處理機(jī)情況 分別采用3種算法對多個DAG任務(wù)集進(jìn)行調(diào)度，在處理機(jī)的數(shù)量為4的情況下，針對不同數(shù)量DAG任務(wù)模型進(jìn)行調(diào)度，得到所有任務(wù)的跨度(調(diào)度長度)makespan、平均等待時間AWT值以及平均Slack值，如圖9(a)、圖9(b)、圖10所示。

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

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

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

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

5 小 結(jié)

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