王 蘭，張龍信，滿君豐，周立前，李肯立

1(湖南工業(yè)大學 計算機學院，湖南 株洲 412007)2(湖南大學 信息科學與工程學院，長沙 410082)

1 引 言

隨著云計算和物聯(lián)網(wǎng)等技術的快速發(fā)展，以及新型社交網(wǎng)絡的不斷涌現(xiàn)，數(shù)據(jù)正在以前所未有的速度不斷地產(chǎn)生和累積，大數(shù)據(jù)和萬物互聯(lián)的時代已經(jīng)到來.相對于物聯(lián)網(wǎng)而言，萬物互聯(lián)在物聯(lián)網(wǎng)的基礎上更側重于“人”與“物”的互聯(lián)[1]，增強網(wǎng)絡智能，推動人工智能的發(fā)展.萬物互聯(lián)的不斷發(fā)展，網(wǎng)絡邊緣設備數(shù)量亦迅猛地增長.

網(wǎng)絡邊緣設備和社交媒體等產(chǎn)生海量的、復雜多樣的數(shù)據(jù)，利用云計算中心超強的計算能力來計算和處理數(shù)據(jù).數(shù)據(jù)中心接受到提交的數(shù)據(jù)任務，采用合理高效的任務調(diào)度算法可以提高計算性能、降低數(shù)據(jù)處理時間.因此，任務調(diào)度問題已經(jīng)成為云計算和邊緣計算中的研究熱點問題[2]，異構計算模式下的任務調(diào)度問題依舊是研究重點問題.

異構計算環(huán)境下的任務調(diào)度問題已經(jīng)被證明是NP-hard問題[3]，所以任務調(diào)度問題只能通過設計的優(yōu)化算法取得近似最優(yōu)解.在并行計算環(huán)境下，合理高效的任務調(diào)度算法會使處理器系統(tǒng)的計算性能得到很大的提升.任務調(diào)度問題是指在滿足某些約束條件的情況下(節(jié)點間的數(shù)據(jù)依賴關系和處理器的計算消耗)，按照設計的算法科學地將每個節(jié)點任務映射到對應處理器上并高效地執(zhí)行，以達到最小化任務執(zhí)行的完成時間、最大化算法的調(diào)度效率的目的.任務的有效調(diào)度是提高處理器計算性能和資源利用率的關鍵所在.

任務調(diào)度問題一直以來都是高性能計算中的經(jīng)典問題.根據(jù)應用程序的特征(包括任務間的依賴關系、任務在處理器上的計算開銷以及任務之間的通信開銷)是否提前給定，可將任務調(diào)度問題分為靜態(tài)任務調(diào)度和動態(tài)任務調(diào)度[4].現(xiàn)有的主要研究工作是針對靜態(tài)任務調(diào)度模型，靜態(tài)任務調(diào)度中應用程序的特征是確定的.針對異構系統(tǒng)中的靜態(tài)調(diào)度問題，主要可劃分為基于啟發(fā)式的調(diào)度算法和基于引導隨機搜索的調(diào)度算法，高調(diào)度效率的HEFT[4]、CPOP[4]、HCPFD[5]等啟發(fā)式算法被廣泛運用到實際的應用程序中.

隨著海量數(shù)據(jù)的產(chǎn)生和計算數(shù)量的增長，異構計算環(huán)境下DAG任務圖的結構也變得復雜多樣化.傳統(tǒng)的調(diào)度算法在解決復雜問題時可能得不到理想的結果，這需要通過更為合理高效的調(diào)度策略來優(yōu)化和平衡系統(tǒng)的各方面性能[6].目前，國內(nèi)外研究學者已經(jīng)提出了很多算法.文獻[7]提出了一種前驅節(jié)點優(yōu)先級最早完成時間算法，首先生成前驅節(jié)點優(yōu)先級隊列(PPQ)，任務根據(jù)向下排名和優(yōu)先級在PPQ中排隊等待調(diào)度.文獻[8]考慮到任務執(zhí)行時關鍵路徑上的信息會隨著任務調(diào)度動態(tài)更新，對首任務采用復制技術，然而任務每一次實時更新會增加整個任務的調(diào)度復雜性.文獻[9]提出了一種基于隊列的資源調(diào)度模型，其將任務和處理器問題轉化成最大費用最小流圖，從而有效地優(yōu)化大規(guī)模資源調(diào)度.文獻[10]針對異構計算系統(tǒng)中的應用程序在使用DVS(動態(tài)電壓頻率調(diào)節(jié))技術實現(xiàn)節(jié)能時，瞬態(tài)故障難以避免.對于具有優(yōu)先約束的并行任務集，設計了能量約束下的應用程序可靠性最大化算法RMEC.RMEC算法能有效地實現(xiàn)系統(tǒng)高可靠性與能量節(jié)約之間平衡的目標.文獻[11]提出了數(shù)據(jù)中心的能量消耗最小和系統(tǒng)失效率最小的雙目標優(yōu)化算法，該算法在不增加時間開銷的約束下，能找到更好的pareto front(帕內(nèi)托前沿).文獻[12]提出了最小松弛時間和最小距離(MSMD)算法，該算法針對應用程序截止日期所需的最小VM實例數(shù)，在分配的VM實例上調(diào)度任務，以達到最小化應用程序的調(diào)度時間.以上研究很少針對復雜多樣的DAG并行任務集展開研究，因此，本文以提高任務間的并行性和處理器的執(zhí)行效率為目標，針對多入口、多出口的并行任務集，提出基于優(yōu)先隊列劃分調(diào)度算法(PQDSA).本文設計的算法將根據(jù)入口節(jié)點數(shù)量確定優(yōu)先隊列數(shù)量，劃分調(diào)度優(yōu)先隊列，將復雜多樣的任務集簡單化.

本文第一部分介紹了異構計算環(huán)境下任務調(diào)度的相關背景和現(xiàn)有的研究工作.第二部分闡述了任務調(diào)度模型和具體應用模型.第三部分詳細介紹了本文提出的算法.第四部分通過實驗驗證了本方法的可行性和有效性.最后對本文工作進行了總結，并對下一步的研究工作進行了展望.

2 相關知識

2.1 任務調(diào)度模型

異構環(huán)境下的任務調(diào)度問題，是指將具有約束條件的任務按照特定的算法映射到有限的處理器上進行執(zhí)行.這些任務一般會用DAG圖來刻畫，任務可以表示為節(jié)點，節(jié)點是任務調(diào)度中的最小單位.當異構計算系統(tǒng)中有任務等待執(zhí)行時，主機會按照特定算法尋找符合條件的處理器來進行調(diào)度，即將任務分配給合適的處理器進行有效調(diào)度以達到預期的優(yōu)化目標.將n個任務調(diào)度到m個處理器上的任務調(diào)度模型如圖1所示.

圖1 n個任務調(diào)度到m個處理器上調(diào)度模型Fig.1 Scheduling model of n tasks scheduled to m processors

2.2 應用模型描述

任務調(diào)度是異構計算環(huán)境下的關鍵問題，這種存在約束關系的任務節(jié)點可以用DAG圖來進行刻畫，即G={T，E，W，C}，其中T={ti|(i=1，2，…，n)}表示異構系統(tǒng)中的任務節(jié)點集合，n為任務節(jié)點總數(shù)量.E={eij|eij表示節(jié)點ti與節(jié)點tj的邊}，即節(jié)點ti與節(jié)點tj之間存在優(yōu)先約束關系且tj是ti的直接后繼節(jié)點.C={cij|cij表示ti與tj之間的通信開銷，ti是tj直接前驅節(jié)點}，cij表示兩個任務節(jié)點不在同一個處理器上執(zhí)行時所需的通信開銷.W={wij|表示節(jié)點ti在處理器pj上的計算開銷}，其中pj表示異構系統(tǒng)中第j個處理器，P是處理器的集合，P={p1，p2，…，pm}，m為處理器總數(shù)量.如果DAG任務圖中不止一個入口或出口節(jié)點，我們可以構建虛擬節(jié)點作為唯一的入口節(jié)點或出口節(jié)點，該虛擬節(jié)點無通信開銷和計算開銷.節(jié)點調(diào)度時必須接收到所有前驅節(jié)點的數(shù)據(jù)才可以進入準備就緒狀態(tài)，等待調(diào)度.如圖2所示的DAG任務圖，T1-T10表示10個任務節(jié)點，有向邊上的數(shù)字表示節(jié)點間的依賴關系，即通信開銷.表1描述了任務節(jié)點在不同處理器上執(zhí)行所需要的計算開銷.

圖2 包含10個任務節(jié)點的DAG應用模型Fig.2 DAG application model with 10 task nodes

圖2所示的DAG圖中，各任務節(jié)點在處理器上的計算開銷如表1所示.為了描述方便，現(xiàn)對任務的開始時間、完成時間、調(diào)度長度和調(diào)度效率給出以下定義.

表1 任務節(jié)點的計算開銷
Table 1 Computation cost of task nodes

TaskiP1P2P3wi-T12312T25133T32132T43343.3T52443.3T61322T72163T84534T91322T104835

定義1.任務的開始時間、完成時間：若ST(ti，pj)、FT(ti，pj)分別表示任務ti在處理器pj上的開始時間和完成時間，則它們之間的數(shù)學關系如式(1)所示：

FT(ti,pj)=ST(ti,pj)+cij

(1)

定義2.前驅節(jié)點、后繼節(jié)點：若pred(ti)表示任務ti的前驅節(jié)點，如果任務ti沒有前驅節(jié)點，則該任務是入口節(jié)點.succ(ti)表示任務ti的后繼節(jié)點，若任務ti沒有后繼節(jié)點，則該任務為出口節(jié)點.

任務節(jié)點ti平均計算開銷定義為：

(2)

其中，wij為任務ti在處理器pi上的計算開銷，m為處理器的數(shù)量.

節(jié)點任務的優(yōu)先級主要由通信開銷、自身在處理器上的計算開銷和前驅節(jié)點的優(yōu)先級等三個因素共同決定.

定義3.任務的TL(ti)值：從入口節(jié)點開始采用遞歸的方法計算每個節(jié)點的t-level值TL(ti)，其計算表達式為：

(3)

入口節(jié)點的TL(ti)的計算表達式如式(4)所示：

(4)

定義4.調(diào)度長度(makespan)：若Texit代表出口節(jié)點,FT(Texit,pj)表示整個調(diào)度的完成時間,若出口節(jié)點不止一個,可以添加零計算開銷、零通信開銷的偽節(jié)點作為最后的唯一出口節(jié)點,調(diào)度長度為：

makespan=max{FT(Texit,pj)}

(5)

調(diào)度的最終目的是將節(jié)點任務科學地分配到處理器上執(zhí)行，以達到最小化調(diào)度長度的目標.

定義5.調(diào)度效率：算法的調(diào)度效率(Efficiency)是指任務調(diào)度加速比與處理器總數(shù)量的比值，其取值范圍為0到100%.調(diào)度效率由DAG任務的完成時間和處理器的數(shù)量共同決定，其計算表達式為：

(6)

其中,m為處理器總數(shù),Speedup為加速比.加速比是指任務集的順序計算時間與調(diào)度長度的比值.

為了描述方便，我們將本文中可能使用到的符號和參數(shù)進行歸納，如表2所示.

表2 符號和參數(shù)定義
Table 2 Symbol and parameter definition

參數(shù)和符號定 義T任務集合ti第i個任務節(jié)點Pj第j個處理器wij任務節(jié)點ti在處理器pj上的計算開銷cij任務節(jié)點ti與節(jié)點tj的通信開銷pred(ti) 任務節(jié)點ti的前驅節(jié)點集合succ(ti)任務節(jié)點ti的后繼節(jié)點集合Wi平均計算開銷Tentry入口節(jié)點Texit出口節(jié)點Li劃分優(yōu)先隊列時借助的空隊列AECT(ti)任務節(jié)點ti的平均完成時間Mpred(ti)任務節(jié)點ti的直接前驅節(jié)點總和Mexit(Li)隊列Li的出口節(jié)點總和TL(ti)任務節(jié)點ti的t-level值

2.3 問題描述

人工智能的崛起和網(wǎng)絡邊緣設備的增加以及數(shù)據(jù)的大量產(chǎn)生，都離不開高性能計算中心的支持.數(shù)據(jù)的海量產(chǎn)生和高性能計算的高效要求，以及DAG任務圖的多變性，都對DAG應用程序的調(diào)度提出更高的性能要求.降低DAG任務圖節(jié)點任務的完工時間以及最大化算法的調(diào)度效率，本文側重于這兩個目標.為了達到所要求的目標，第一步在滿足約束條件下，對隊列進行劃分，提高任務間的并行性，以達到降低調(diào)度長度的目的.第二步在保證盡可能降低調(diào)度長度的前提下，將任務科學地調(diào)度到處理器上，以達到最大化處理器的資源利用率[13].

3 優(yōu)先隊列劃分調(diào)度算法(PQDSA)

眾所周知，異構計算環(huán)境下的任務調(diào)度問題是NP-hard問題[3].為了提高處理器的執(zhí)行效率和任務間的并行性，本文提出基于優(yōu)先隊列劃分的任務調(diào)度算法(PQDSA).PQDSA算法的主要思想是根據(jù)入口節(jié)點的數(shù)量，通過計算開銷和通信開銷來劃分合適的優(yōu)先隊列.該算法執(zhí)行步驟分為優(yōu)先隊列劃分、節(jié)點優(yōu)先級以及處理器選擇三個階段.首先，存在數(shù)據(jù)依賴關系的節(jié)點在不同的處理器上執(zhí)行時，會存在通信開銷.為了降低任務集的完工時間，將通信開銷較大的任務分配到同一臺處理器上執(zhí)行，以提高調(diào)度效率.然后，根據(jù)入口節(jié)點數(shù)量劃分的優(yōu)先隊列，計算隊列中節(jié)點的TL(ti)值，確定節(jié)點優(yōu)先級.最后，在處理器選擇階段，使用基于插入策略的思想，計算出任務完成時間最小的處理器，將其作為該節(jié)點的調(diào)度處理器，從而進一步縮短調(diào)度時間.

3.1 優(yōu)先隊列劃分階段

在優(yōu)先隊列劃分階段，針對復雜多樣的DAG任務圖，在任務執(zhí)行調(diào)度之前，首先根據(jù)入口節(jié)點的數(shù)量來決定劃分多少優(yōu)先隊列.在本文中，從DAG圖中的入口節(jié)點到出口節(jié)點，通信開銷和計算開銷之和最大的路徑稱為關鍵路徑.多于一個直接前驅節(jié)點的節(jié)點稱為關鍵節(jié)點.任務劃分的主要思想是將關鍵節(jié)點劃分到適合的隊列中，生成最佳的任務調(diào)度隊列，以提高任務的并行性.計算每個節(jié)點的平均完成時間(AECT)，根據(jù)AECT值對節(jié)點進行劃分，然后在調(diào)度到合適的處理器上執(zhí)行.劃分優(yōu)先隊列時需要借助空隊列Li(i=1，2，3…)，i的取值取決于實際入口節(jié)點的數(shù)量.參數(shù)Mexit(Li)表示隊列Li出口節(jié)點的總數(shù)，Mpred(ti)表示節(jié)點ti的直接前驅節(jié)點的總數(shù).對于多入口多出口節(jié)點的復雜任務應用程序，即存在多個入口節(jié)點和多個出口節(jié)點，可以采用零計算開銷和零數(shù)據(jù)傳輸時間的節(jié)點作為偽入口節(jié)點和偽出口節(jié)點，偽節(jié)點不影響整個調(diào)度過程.

任務的平均完成時間(AECT)從入口節(jié)點開始采用遞歸的方式進行計算，其表達式如式(7)所示：

(7)

對于入口節(jié)點Tentry,其平均完成時間AECT表示為:

(8)

在優(yōu)先隊列劃分的過程中，通過判斷整個DAG任務圖入口節(jié)點的數(shù)量，借助空隊列Li，選擇每個入口節(jié)點，放入空隊列中單獨成為一個隊列.從入口節(jié)點開始遞歸計算每個節(jié)點的AECT值，隊列中選擇節(jié)點時按以下方式處理：

1)如果節(jié)點ti只有一個直接前驅節(jié)點，則直接將該節(jié)點放入其前驅節(jié)點的隊列中；

2)如果節(jié)點ti有多個直接前驅節(jié)點，即Mpred(ti)>1時，則該節(jié)點為關鍵節(jié)點，比較其前驅節(jié)點的AECT值，將節(jié)點放入AECT值最大的節(jié)點隊列中.

關鍵節(jié)點根據(jù)其前驅節(jié)點的AECT值來選擇隊列，將復雜度較高的任務圖劃分成低復雜度的隊列，提高任務間的并行性.本文提出PQDSA算法的隊列劃分階段偽代碼如算法1所示.

算法1.隊列劃分算法

Queue dividing algorithm

Input：并行任務集G={T，E，W，C}

空隊列Li(i=1，2，…，n)，n為入口節(jié)點的數(shù)量

Output：優(yōu)先隊列劃分結果

1.從入口節(jié)點開始，向下遍歷計算所有任務節(jié)點AECT值.

2.forti=t1totn

3.ifMpred(ti)==0

4. 借助空隊列Li，將該節(jié)點放入空隊列中

5.elseifMpred(ti)==1

6. 直接將給節(jié)點放入其前驅節(jié)點所在隊列

7.else

8. 比較其直接前驅節(jié)點的AECT值

9. 將節(jié)點放入AECT值最大的節(jié)點所在隊列

10.endif

11.endfor

任務劃分隊列結果如圖3所示.

在算法1中，步驟1指從入口節(jié)點開始遍歷每個節(jié)點，并計算每個節(jié)點的AECT值.步驟3-10實現(xiàn)節(jié)點根據(jù)隊列劃分條件選擇優(yōu)先隊列，直至所有節(jié)點都在隊列中.

圖3 任務優(yōu)先隊列劃分結果Fig.3 Task priority queue division results

為了詳細地說明隊列的劃分過程，圖3所示為優(yōu)先隊列劃分的實例化例子.由給定的DAG任務圖2可知，圖中有兩個入口節(jié)點T1和T2，需要借助兩個空隊列L1和L2，將入口節(jié)點放入對應的空隊列中，即L1={T1}、L2={T2}.圖中節(jié)點T7有三個直接前驅節(jié)點，則該節(jié)點為關鍵節(jié)點，計算其直接前驅節(jié)點的AECT值，將節(jié)點T7加入AECT值最大的隊列中，因此將T7加入隊列L2中.初步得到隊列L1和隊列L2，最后檢查生成的優(yōu)先隊列，隊列L1存在兩個出口節(jié)點T8和T9，則添加一個零計算開銷和零通信開銷的偽節(jié)點作為隊列L1的唯一出口節(jié)點.最終劃分得到的兩個優(yōu)先隊列分別為L1={T1,T3,T6,T8,T9}、L2={T2,T4,T5,T7,T10}.

3.2 優(yōu)先級選擇階段

由入口節(jié)點數(shù)量確定優(yōu)先隊列的數(shù)目，根據(jù)通信開銷和平均計算開銷將節(jié)點添加到隊列中，從而提高任務間的并行性.由于關鍵節(jié)點的存在，隊列間的數(shù)據(jù)依賴并沒有完全消失.在確定任務集的調(diào)度順序時，需要對隊列中的所有任務節(jié)點計算TL(ti)值來確定任務的優(yōu)先級.處理器對任務進行調(diào)度時，首先要考慮當前調(diào)度中是否存在關鍵節(jié)點任務，如果關鍵節(jié)點任務的前驅節(jié)點尚未調(diào)度，那么需要先調(diào)度其前驅節(jié)點再執(zhí)行下一步.倘若該節(jié)點為關鍵節(jié)點，則表示該節(jié)點的直接前驅節(jié)點個數(shù)Mpred(ti)多于一個.倘若節(jié)點的直接前驅節(jié)點都來自同一隊列，那么直接調(diào)度該關鍵節(jié)點.倘若其直接前驅節(jié)點有來自其他隊列的節(jié)點任務，此時需要考慮該前驅節(jié)點是否已調(diào)度、數(shù)據(jù)是否已到達.在確定該前驅節(jié)點已經(jīng)調(diào)度且數(shù)據(jù)已經(jīng)到達之后，則該關鍵節(jié)點可以執(zhí)行調(diào)度.對TL(ti)值相同的節(jié)點，可采取隨機方式進行調(diào)度.

對于給定的DAG任務圖2，根據(jù)入口節(jié)點劃分兩個優(yōu)先隊列的實例圖如圖3所示.在任務的優(yōu)先級選擇階段，首先計算優(yōu)先隊列L1和L2中節(jié)點的TL(ti)值，然后將優(yōu)先隊列中節(jié)點根據(jù)TL(ti)值的大小按照升序排列，得到實例化優(yōu)先隊列L1和L2，對應的節(jié)點集合分別為{T1,T3,T6,T8,T9}、{T2,T4,T5,T7,T10}.

3.3 處理器選擇階段

通過對任務劃分優(yōu)先隊列，很大程度上降低了任務的相關性，提高了隊列的并行性，減少了節(jié)點的平均完成時間.再對隊列中的任務進行優(yōu)先級選擇，生成任務的拓撲順序，確保關鍵節(jié)點滿足優(yōu)先約束.這一節(jié)的重點是將任務調(diào)度到合適的處理器上執(zhí)行，進一步提前節(jié)點的完成時間.在DAG任務圖應用程序中，任務調(diào)度到某個處理器上執(zhí)行，必須等待其所有前驅節(jié)點執(zhí)行結束且相關數(shù)據(jù)到達其所在的處理器，該節(jié)點任務才可以開始執(zhí)行調(diào)度.兩個任務節(jié)點在同一個處理器上執(zhí)行時，其通信開銷為零.獲取DAG任務圖的關鍵節(jié)點，該關鍵節(jié)點在同層的節(jié)點中任務優(yōu)先級最高.

任務實際開始時間(AST)和任務實際結束時間(AFT)的計算表達式為：

AST(tentry)=0

(9)

AST(ti)=AFT(ti)-wij

(10)

(11)

當ti與其前驅節(jié)點tj在同一處理器上執(zhí)行，k=0；當ti與其前驅節(jié)點tj在不同處理器上執(zhí)行時，k=1.

如果隊列中任務都只有一個直接前驅節(jié)點，則可以將隊列中所有任務分配到同一處理器，此時沒有通信開銷，也不需要等待其他節(jié)點的數(shù)據(jù).如果任務直接前驅節(jié)點任務多于一個時，則該節(jié)點是關鍵節(jié)點，數(shù)據(jù)最后到達的前驅節(jié)點為關鍵父親節(jié)點.

針對存在關鍵節(jié)點的任務隊列，考慮到關鍵父親節(jié)點數(shù)據(jù)到達的時間，不能直接把所有任務分配到同一臺處理器上執(zhí)行.本算法采用基于插入的思想，在處理器上足夠大的時間槽空隙中插入任務.對于隊列中非入口節(jié)點，但沒有直接后繼任務，可以將其單獨放置于單獨的處理器，給其他節(jié)點任務釋放空間，進一步減少最終完成時間.PQDSA的全部偽代碼如算法2所示.

算法2.PQDSA算法

PQDSA algorithm

Input：并行任務集G={T,E,W,C}，

空隊列Li(i=1，2，…，n)，n為入口節(jié)點的數(shù)量

Output：DAG任務集的調(diào)度結果

1.從入口節(jié)點開始，向下遍歷計算所有任務節(jié)點的AECT值.

2.forti=t1totn

3. 滿足劃分隊列條件

4. 產(chǎn)生劃分結果，隊列L1，L2…

5.endfor

6.從每個隊列的入口節(jié)點開始,向下遍歷計算每個節(jié)點的TL(ti)值.

7.whileLi非空do

8. 按TL(ti)值升序排列

9.ifTL(ti)=TL(tj)

10. 隨機排序

11. 生成優(yōu)先級隊列

12.endif

13.end

14.whileLi非空do

15. 隊頭節(jié)點ti從隊列Li中出隊

16.for處理器集合P中每個處理器

17. 計算AST(ti)和AFT(ti)

18. 為節(jié)點選擇AFT(ti)值最小的處理器

19.endfor

20.end

3.4 PQDSA算法時間復雜度分析

在將n個任務調(diào)度到m個處理器上任務調(diào)度環(huán)境中，PQDSA主要包含優(yōu)先隊列劃分、優(yōu)先級選擇和處理器選擇三個部分，對這三個部分進行分析可得到算法總時間復雜度.

在優(yōu)先隊列劃分階段，DAG圖中邊之間的約束關系選擇鏈表方式進行存儲，該階段的時間復雜度為O(n+p)，其中n為DAG圖節(jié)點數(shù)量，p為處理器的數(shù)目.在優(yōu)先級選擇階段，計算節(jié)點TL(ti)值，其時間復雜度為O(n2).最后在處理器選擇階段，計算節(jié)點調(diào)度到每個處理器上的AST(ti)值和AFT(ti)值，在將任務調(diào)度到AFT(ti)值最小的處理器上，其時間復雜度為O(n2×p).由此可知，PQDSA算法的時間復雜度為O(n2×p).

3.5 PQDSA算法調(diào)度實例分析

首先使用圖2的實例化DAG任務圖進行分析以及對比調(diào)度長度，然后在劃分優(yōu)先隊列數(shù)量進行性能對比，以及節(jié)點數(shù)量不同和劃分優(yōu)先隊列數(shù)不同的情況下，來進行實驗比較分析.DAG實例化三個算法的調(diào)度長度對比圖如圖4所示.

圖4 三個算法的調(diào)度過程Fig.4 Scheduling process of three algorithms

針對圖2給出的實例化DAG任務圖，圖4為HEFT算法、PTSAC算法和PQDSA算法的調(diào)度效果.HEFT算法對節(jié)點任務進行優(yōu)先級排序，再采用基于插入策略將節(jié)點調(diào)度到處理器上.PTSAC算法通過通信開銷和計算開銷來確定相關性，判斷是否進行復制.本文提出的算法PQDSA首先通過入口節(jié)點的數(shù)量來確定劃分優(yōu)先隊列數(shù)，由圖2可知，有T1和T2兩個入口節(jié)點，因此可以劃分兩個優(yōu)先隊列L1和L2，將復雜多樣的DAG任務圖劃分成兩個相關性低的優(yōu)先隊列.然后按照節(jié)點劃分隊列的要求，將節(jié)點都放入到合適的隊列中，如圖3所示，生成最后的優(yōu)先隊列L1和L2.最后再將隊列中的任務調(diào)度到處理器上.由圖4可知，三個算法的調(diào)度長度分別為16、16和14，本文提出的算法的調(diào)度長度要比HEFT算法和PTSAC算法縮短了2個單位，相當于makespan降低了12.5%.

4 實驗部分

4.1 實驗環(huán)境

為了驗證本文提出的PQDSA算法的可行性和有效性，以及避免因實驗環(huán)境不同和對比的算法產(chǎn)生性能上的差異.本文采用相同的實驗環(huán)境來進行對比.實驗中使用Intel Core(TM)i5-9300H@ 2.40GHz四核處理器，16 GB內(nèi)存，python版本為3.7，系統(tǒng)運行環(huán)境為Windows 10.

4.2 實驗結果分析

本文主要采用調(diào)度長度(makespan)和調(diào)度效率(Efficiency)兩個參數(shù)作為衡量算法的性能指標，并選取HEFT算法和PTSAC算法來進行實驗對比分析.PQDSA算法的輸入為DAG任務圖，算法的輸出為DAG任務圖的調(diào)度結果.

4.2.1 任務調(diào)度長度

PQDSA算法主要側重于任務調(diào)度長度，基于調(diào)度長度從兩個方面進行實驗.第一組實驗是劃分優(yōu)先隊列數(shù)不同時的調(diào)度長度比較，第二組實驗是DAG節(jié)點數(shù)量不同時的調(diào)度長度比較，分別如圖5、圖6所示.圖5分別為劃分2、4、6、8、10個優(yōu)先隊列時3個算法的調(diào)度長度對比，圖6為DAG節(jié)點數(shù)量分別為10、20、30、40、50時3個算法的對比情況.

圖5 劃分隊列數(shù)不同時三種算法調(diào)度長度對比Fig.5 Makespan comparison of three algorithms withdifferent queue numbers

圖5的橫坐標為劃分優(yōu)先隊列數(shù)，是指由入口節(jié)點的數(shù)量來確定的優(yōu)先隊列數(shù)量，縱坐標為算法所需要的調(diào)度長度值.從實驗數(shù)據(jù)對比可以得出，在任務調(diào)度時間長度方面，PQDSA算法的調(diào)度時間比HEFT算法和PTSAC算法要低，隨著優(yōu)先隊列數(shù)的增加差距愈發(fā)明顯.PQDSA算法根據(jù)入口節(jié)點對任務進行劃分優(yōu)先隊列，將關鍵節(jié)點任務放入合適的隊列中.在任務調(diào)度之前提高任務的并行性，降低節(jié)點間的時間消耗，隨著優(yōu)先隊列數(shù)的增加，PQDSA算法的優(yōu)勢愈發(fā)顯著.由實驗數(shù)據(jù)可以得出，在劃分優(yōu)先隊列數(shù)時調(diào)度長度方面，PQDSA算法比HEFT算法最高降低了22.5%，最低縮短了1.3%；PQDSA算法比PTSAC算法最高降低了18.6%，最低縮短了8.4%.

圖6 不同DAG節(jié)點數(shù)量三種算法調(diào)度長度對比Fig.6 Makespan comparison of three algorithms withdifferent number of DAG nodes

圖6中橫坐標為DAG任務圖的節(jié)點數(shù)量，縱坐標為調(diào)度長度.由圖6的實驗結果對比圖可知，隨著DAG中節(jié)點數(shù)量的增加，HEFT、PTSAC和PQDSA算法的調(diào)度長度變化并不明顯.當節(jié)點數(shù)為10時，HEFT、PTSAC和PQDSA算法的調(diào)度長度差距并不明顯；當節(jié)點數(shù)為20時，PQDSA算法的調(diào)度長度要明顯低于HEFT和PTSAC算法.隨著DAG中節(jié)點數(shù)量的增加，與HEFT和PTSAC相比，PQDSA算法在降低調(diào)度長度方面的優(yōu)勢愈發(fā)明顯.當節(jié)點數(shù)為50時，PQDSA算法的調(diào)度長度要明顯低于HEFT和PTSAC算法.當節(jié)點數(shù)量為10時，PQDSA算法只比HEFT算法和PTSAC算法降低了2個單位.節(jié)點數(shù)量為30時，PQDSA算法分別比HEFT算法和PTSAC算法縮短了3個單位和12個單位.當節(jié)點數(shù)量達到50時，PQDSA算法分別比HEFT算法和PTSAC算法減少了6個單位和7個單位.由實驗數(shù)據(jù)不難得出，當DAG任務節(jié)點數(shù)量不同時，在任務調(diào)度長度方面，PQDSA算法要優(yōu)于前兩種算法.

4.2.2 調(diào)度效率

為了進一步驗證PQDSA算法的性能，分別采用3種算法對DAG圖進行調(diào)度，選擇調(diào)度效率作為算法性能測試指標.針對優(yōu)先隊列數(shù)和DAG節(jié)點數(shù)量進行兩組實驗，實驗結果分別如圖7、圖8所示.

圖7 劃分隊列數(shù)量不同時三種算法調(diào)度效率對比Fig.7 Comparison of scheduling efficiency of three algorithmswith different queue numbers

圖8 不同DAG節(jié)點數(shù)量時三種算法調(diào)度效率對比Fig.8 Comparison of scheduling efficiency of three algorithmswith different number of DAG nodes

圖7和圖8的縱坐標均為算法的調(diào)度效率，圖7的橫坐標為劃分優(yōu)先隊列數(shù)量，圖8的橫坐標為DAG節(jié)點數(shù)量.圖7為優(yōu)先隊列數(shù)分別為2、4、6、8、10時的調(diào)度效率對比.圖8展示了DAG中節(jié)點數(shù)量分別為10、20、30、40、50時的調(diào)度效率實驗結果對比.由圖7的實驗數(shù)據(jù)對比分析可以得出，在算法調(diào)度效率方面，PQDSA算法都要優(yōu)于HEFT和PTSAC算法.當劃分的優(yōu)先隊列數(shù)分別為2、4、6時，PQDSA算法相對于HEFT算法提高并不明顯，相對于PTSAC算法改善更為顯著，尤其當優(yōu)先隊列為6時.當優(yōu)先隊列數(shù)達到8或者10時，PQDSA算法明顯優(yōu)于HEFT算法.因此，我們可以得出結論，PQDSA算法特別適合優(yōu)先隊列數(shù)較多的DAG圖.由圖7的實驗數(shù)據(jù)對比可知，在劃分優(yōu)先隊列數(shù)不同時，PQDSA算法在調(diào)度效率方面比HEFT算法最高提升了5.76%，最低增加了1.33%.比PTSAC算法最高提升了15.47%，最低增加了5.87%.由圖8的實驗數(shù)據(jù)可以得出，當DAG節(jié)點數(shù)量不同時，PQDSA算法在調(diào)度效率方面比HEFT算法最高提高了11.23%，最低改善了4.13%.比PTSAC算法最高提高了13.82%，最低增加了5.31%.由圖7和圖8的實驗結果分析對比不難得出，PQDSA算法調(diào)度效率要優(yōu)于對比的兩種算法.其主要原因在于PQDSA算法采取劃分優(yōu)先隊列的方法，將關鍵節(jié)點放置于合適的隊列，再將任務分配到完成時間最小的處理器上，使得每一步都在降低任務的最晚完成時間.從整體上提高任務的并行性，減小任務的調(diào)度時間，提升任務的調(diào)度效率.

通過四組實驗分析對比得出，PQDSA算法在調(diào)度長度以及算法的調(diào)度效率兩個方面均優(yōu)于HEFT算法和PTSAC算法.在任務調(diào)度長度方面最大分別降低了22.5%和18.6%，在調(diào)度效率方面最大分別提高了11.23%和15.47%.PQDSA算法在調(diào)度長度以及調(diào)度效率等方面，均呈現(xiàn)比較理想的效果.

5 總 結

云計算和人工智能的高速發(fā)展，邊緣設備數(shù)量的劇增，這對高性能計算提出了更高的要求.異構環(huán)境下的任務調(diào)度問題是高性能計算中的研究重點.本文通過對DAG任務調(diào)度模型的研究，針對復雜多樣的DAG任務圖，本文提出一種基于優(yōu)先隊列劃分的調(diào)度算法(PQDSA).PQDSA算法針對多入口多出口節(jié)點的任務圖，根據(jù)入口節(jié)點采用劃分優(yōu)先隊列的方法，將高復雜度、低并行性的節(jié)點任務劃分成單獨的隊列.對于關鍵任務節(jié)點與其直接前驅節(jié)點存在依賴關系，劃分隊列時利用節(jié)點的平均完成時間將關鍵節(jié)點放入合適的隊列，降低任務的時間消耗.實驗結果的分析對比表明，PQDSA算法在調(diào)度長度和調(diào)度效率方面明顯優(yōu)于HEFT算法和PTSAC算法.