基于時隙堆棧搜索的異構集群DAG調度策略

薛亞非，馮 鈞

(1.南京師范大學 中北學院，江蘇 南京 210046；2.河海大學 計算機與信息學院，江蘇 南京 210098)

0 引 言

對于有向無環圖應用，任務調度問題是并行計算和分布式計算的基本問題之一，該問題一般是NP難的，最優解僅限于該問題限制情形，該領域中啟發式任務調度算法已得到廣泛研究[1,2]。

組合優化問題有許多技術，已被應用到任務調度制導搜索算法中，可分為兩類[3,4]：①隨機制導搜索，其中使用隨機過程，借助于候選解表示方法和隨機候選解攝動過程。例如，文獻[5]提出基于模擬退火算法的任務調度策略，通過涉及重復加熱和冷卻的退火過程使晶體結構處于更有序狀態的概念。文獻[6]提出基于禁忌搜索算法(Tabu)的任務調度策略，可避免在區域附近重復搜索。文獻[7]提出基于模擬進化算法(simulated evolution，SE)的任務調度策略，通過使用選擇和生成步驟從當前解決方案生成新的任務調度解決方案。②確定性制導搜索，使用確定性策略，對要解決問題的密切知識搜索候選解。例如，文獻[8]提出基于TASK算法(TASK algorithm)的任務調度策略，算法缺點是重復執行步驟過多，計算復雜度過大。同時，當任務調度問題采用隨機制導搜索策略時，存在問題[9,10]：①隨機性可防止搜索在適當的搜索方向上快速進行。根據沿途發現的隨機解，對于中型或大型網絡搜索時間變化很長。②通常需要大量控制參數，這些參數通常由實驗確定。這是嚴重的限制，因為反映實際執行環境的良好實驗對于獲得良好解決方案至關重要。

本文提出了基于時隙堆棧策略的確定性引導搜索算法，該算法對于異構集群系統的DAG調度特別有效，通過使用消除由慢速網絡鏈路互連的節點之間的通信需求的“填充”操作來解決上述問題，實現算法性能提升。

1 問題模型

1.1 模型定義

應用程序可利用DAG模型G=T,E表示[11]，其中T是一組NT任務集合，E是一組NE邊集。每個邊eij=ti,tj∈E表示優先約束關系，指示任務ti應該在任務tj開始之前完成執行。任務ti具有與基線處理器平臺上任務ti的執行時間相對應的權重τi1≤i≤NT，邊緣eij1≤i,j≤NT具有與從pi到pj要傳輸的數據量對應的權重εij。

目標異構集群系統可以由無向圖HC=C,LW分層表示，其中C=Ck1≤k≤NC對應于一組NC集群，而LW=lCiCjCi,Cj∈C對應于一組集群之間的WAN鏈路。每個集群Ck=P(k),L(k)包含一組處理器P(k)和用于在P(k)中的處理器之間進行通信的一組局域網(LAN)鏈路L(k)。

為了進行任務調度，異構集群系統可由非層次圖模型NHC=P,L表示，其中[12,13]

(1)

在這一特定鏈接表示，給定鏈接lpipj，如果pi,pj都屬于第k個簇C(k)，則該鏈接對應于L(k)中的LAN鏈接。否則，該鏈接對應于LW中的WAN鏈接。每個處理器pq都有一個(相對)計算功率因數wq；在處理器pq上執行任務ti需要τi·wq時間單位。同樣地，令λpq,pr表示pq和pr之間鏈路的帶寬的倒數，以便在εij·λpq,pr時間單元將εij從pq發送到pr。給定一個DAG模型G和一個異構集群模型NHC，本文解決的問題是找到一個高質量的調度，定義為從G到NHC的映射。解決方案的質量由最大完工時間、所產生的計劃的總長度決定。

1.2 調度方案求解

可使用諸如圖1所示的圖形結構來表示調度表。在這個圖中，虛線箭頭表示存在分配給同一處理器的兩個任務之間的執行順序。

圖1 關鍵路徑(厚實線)和時隙模型

定義1[14]給定分配在同一處理器上的兩個任務，tjl和tjm，對于tjl優先于tjm，表示為tjltjm，當且僅當l小于m時。符號“”用于表示執行順序。當秩不同時，可用代替“”。

定義2[15]在同一處理器上連續分配的一組任務由tjl::tjm表示，其中tjl和tjm是分別具有最小和最大秩的兩個任務。這個集合可被認為是一個時隙堆棧。時隙堆棧的頂部和底部元素分別是tjl和tjm。

1.3 調度計劃評估

調度質量可用列表啟發式方法評估。令AST(ti)和AFT(ti)表示任務ti的指定開始時間和分配完成時間。Tdata(ti)是從處理器φ(ti)執行任務ti的接收所有數據所需時間，Tavailφ(ti)是處理器φ(ti)可用時間。則可得

(2)

式中：compti,φ(ti)任務ti在處理器φ(ti)上的計算時間。下面列出其它有關定義。

定義4 計劃調度的關鍵路徑CP是任務和邊緣的路徑，從而導致該調度具有最小完成時間。CP中任務被稱為關鍵任務。CP長度是進度的最大化。

定義5 給定任務ti，ti的關鍵前置任務(cpt(ti))是ti的前置任務，它最遲在ti的所有前置任務中完成數據傳輸。Tdata(ti)由ti的關鍵前置任務決定。

1.4 調度過程改進

在基于搜索的調度算法中，常用技術包括試圖通過修改當前最佳任務調度來找到改進的任務調度，然后測試新調度是否優于當前最佳調度。如果新的調度計劃更好(或者至少不是更壞)，那么在下一次迭代中，它被認為是當前最佳計劃。新的調度表被認為是可接受的。如果新的調度表是可接受的，它將在下一次搜索迭代期間替換當前最佳調度。

該“修改和測試”方案導致在每次迭代中找到連續更好的任務調度的可能性。但是必須有一種方法生成新的調度計劃，以有效方式搜索可能的解決方案空間。此外，生成的新調度必須具有有效的表示形式。下面給出如下兩個表示函數：

函數1：ψ′1=ReassignR→pjψ。此函數通過使用以下步驟將集合R中的所有任務重新分配給處理器pj來更改調度方案ψ。

步驟1 每當調度ψ下任務tjk,tjk+1不是E∈G的元素時，將該對作為零加權偽邊添加到DAG模型G中。

步驟2 按照拓撲順序對得到的DAG模型進行排序，并構造包含一系列匹配對ti,pj的字符串。該匹配意味著任務ti被映射到處理器pj。

步驟3 替換pj匹配的處理器部分；亦即，對于tk∈N利用tk,φtk替換tk,pj。

步驟4 基于拓撲排序和在修改后的字符串中使用的匹配來構造新的調度。

這4個步驟通過在DAG中維護任務之間的優先約束來保證生成有效的調度。該函數的時間復雜度為O(TlogT)，其中T是任務的總數。這源于在步驟2中在DAG拓撲模型中對所有T任務排序所需的時間。

2 基于時隙堆棧的任務調度算法

2.1 算法描述

在所提基于時隙堆棧的任務調度算法中，可利用兩個步驟獲得高質量的解決方案：①使用基線算法生成基線調度。最近開發的算法，例如HEFT或HCPT算法[13,14]，可以快速地為大多數類型的目標計算環境生成良好的任務調度，可以用作基線算法。②使用確定性搜索過程改進基線調度。其實質為協調搜索過程，試圖通過利用任務調度問題和目標計算環境先驗知識來迭代地改進當前最佳解決方案。

所提算法采用兩種技術以提高基線調度：①涉及找到當前調度的關鍵路徑，并試圖通過將任務移動到其它處理器來縮短完工時間，從而減少關鍵任務分配開始時間。②包括找到給定時間表中的所有可行時隙(在兩個指定任務之間的處理器時間中的空閑間隙)，并檢查是否有可能將一組任務插入到這些時隙中。如果成功地將任務插入時隙可顯著縮短完成時間(執行DAG應用程序中的所有任務所需的時間)。這兩種技術，分別稱為推送和填充過程，以迭代方式執行，直到在搜索解決方案中沒有進一步改進為止。算法1給出了任務調度的時隙堆棧過程形式化描述。

算法1：時隙堆棧過程形式化描述

(1) 利用現有算法(基于列表的啟發式算法)生成調度計劃ψ。

(2) Repeat

(3)利用推送過程獲得新調度方案ψ′；

(4)利用填充過程獲得新調度方案ψ″；

(5)在ψ,ψ′,ψ″中選取最佳調度→ψ；

(6) UntilK步迭代后→ψ不發生變化；

(7) Returnψ(當前最佳調度方案)

最初，該算法使用基線算法(例如，基于列表的啟發式算法)獲得基線調度。接下來，它重復時隙堆棧過程，直到K步迭代過程中解的質量沒有改善為止。K是該算法中唯一的控制參數(通常設置為一個小值，如K=4或5)。當算法終止時，它返回迄今為止找到的最佳調度。算法中ψ′即為函數1～函數2中所定義的ψ′1和ψ′2。

觸發任務與目標任務集定義方面，時隙堆棧操作試圖通過重新分配任務來減少調度長度。在這些操作中，激勵這種重新分配任務ti被稱為觸發任務，且由觸發任務重新分配的相同處理器上連續分配一組任務，例如R=[tjl::tjm]，被稱為目標任務集。對于所有推拉操作，都需觸發任務ti和目標任務集R。

2.2 推送操作

給定觸發任務ti和R中的目標任務，涉及觸發任務ti目標任務到另一處理器上的操作稱為推送操作。因此，推送操作可表述如下

(3)

圖2 推送操作

示例中，假設觸發任務是t5，目標任務集R具有t3和t4。由于t5推送t3和t4，兩個目標任務被重新分配到產生最佳結果調度的任何處理器(在p1、p2和p3之間)。圖2給出推送結果。任務t3和t4分別被移動到p1和p3，這導致了最大完工時間減少。

為執行推送操作，需一個目標任務集，可通過觸發任務ti和目標任務tk之間的下列先決條件完成的，須滿足：①tk和ti彼此獨立；②φtk=φ(ti)；③tkti。推送操作目的是通過將目標任務推離當前處理器來更早地執行觸發任務ti。為此，增加第3個條件。上述3個條件均滿足ti和Bitsk(ti)位之間的任務tk。因此，Bitsk(ti)用作推送操作中給定任務ti的匹配目標集R。該算法過程見算法2所示。

算法2：推送操作

ProcedurePush_optc,Bitsktc→P

(1)R←Bitsktc；

(2) whileR≠? do

(3)在R中選取任務tr；

(4)P′←P中候選處理器；

(5)repeat do

(6) 在P′中選取處理器pj；

(7)ψ′←Reassigntr→pjψ；

(8) ifψ′可接受 then

(9)ψ←ψ′；

(10)P′←P′-pj；

(11)untilψ′可接受；

(12)R←R-tr；

(13) endwhile

在最壞的情況下，所有新生成調度都是不可接受的，該算法的時間復雜度是ORPTlogT。然而，由于新生成的調度可以在內環內被接受，所以平均時間復雜度會更小。

必須將Bitsktc的所有任務重新分配到P中處理器中。由于在典型的異構集群環境中存在大量的處理器，因此希望限制要考慮的處理器集。因此，對于給定目標任務，只有以下處理器被視為候選處理器，表示為P′：①分配至少一個任務的處理器；②在每個集群中沒有任務分配的處理器中最快的處理器(具有最低的wq)。

以這種方式選擇候選處理器原因如下：①如果在給定處理器上分配任務，則在該處理器上執行其它任務可以消除通信延遲。②可能還有其它有用的處理器，在這些處理器上還沒有分配任務。當計算和通信成本都被考慮時，在可用處理器集合中每個集群中最快處理器也可能對某些任務有益。利用該操作，推送操作時間復雜度變為ORP′TlogT。

2.3 填充操作

給定分配給處理器pi的觸發任務ti和分配給處理器pk≠pi的目標任務集R=tjl::tjm，涉及觸發任務填充設置到處理器pi的目標任務的動作被稱為填充操作。因此，該操作可以表述如下

Pull_opti,R≡ReassignR→φ(ti)

(4)

當填充目標任務時，將被重新分配給觸發器任務處理器。這使得觸發器任務和目標任務在同一處理器上執行，從而消除了它們之間的通信成本。填充運算的時間復雜度為OTlogT。

圖3給出了填充操作的一個例子。在這個例子中，假設觸發任務是t7，目標任務集R包括t3、t4和t5。因為t7填充R=t3,t4,t5，將3個目標任務重新分配給p7，從而減少最大完工時間。

圖3 填充操作

要執行填充操作，填充操作需要一個目標任務集。這是通過在R=tjl::tjm中的觸發任務ti和目標任務tk之間滿足以下前提條件來實現的，必須滿足以下條件：①必須存在一個邊緣ejmi；②φ(ti)≠φtk。這兩個條件稱為填充條件。

給定目標任務ti，使用以下方法來確定目標任務集。首先，選擇一個具有φ(ti)≠φcpt(ti)的任務cpt(ti)作為第一目標任務，這對應于R中的tjm。這種選擇的原因是ti的指定起始時間嚴重依賴于cpt(ti)。如果通過填充操作消除了這兩個任務之間的通信成本，則預期會有益處，因為任務ti可以更早地執行。

如果只填補目標任務cpt(ti)，就會出現問題。假設cptcpt(ti)、cpt(ti)最初運行在同一處理器上。如果ti填充cpt(ti)，則不會消除cpt(ti)和cptcpt(ti)之間的通信成本，即使它消除了ti和cpt(ti)之間的通信成本。cptcptcpt(ti)與運行在相同處理器的cptcpt(ti)存在相同的情況。

解決這個問題的方案是將整個關鍵前端任務鏈(在單個處理器上分配)視為一組目標任務。設R為目標任務集，tr為cpt(ti)。目標任務tr擴展為一組目標任務R，包括cpttr、cptcpttr等。在填充操作中，R中所有任務都被認為是填充候選。因此，填充操作中任務ti的目標任務集為R=tjl::tjm，其中對于l≤r≤m-1，存在tjm=cpt(ti)，φcpt(ti)≠φ(ti)，tjr=cpttjr+1，φtjr≠φtjr+1。

在填充過程中，只有在通過可行性檢查和新的時間表是可接受的情況下才執行填充操作。如果當前堆棧R的可行性和可接受性檢查失敗，則移除堆棧R的頂部并重復該過程，直到通過檢查或堆棧變空。整個過程如算法3所示。

算法3： 填充操作

(1)N←T中任務的拓撲排序列表；

(2) whileN≠? do

(3) 選取N中的第一個任務tk；

(4) 尋找滿足填充條件的tk,R對；

(5) whileR≠? do

(6) if 插入R可行 then

(7)ψ′←Pull_optk,Rψ；

(8) ifψ′可接受 then

(9)ψ←ψ′， 跳轉步驟(2)；

(10) 移除R的最頂端；

(11) endwhile

(12)R←R-tk；

(13) endwhile

3 實驗分析

3.1 實驗設置

所使用的調度算法在公共計算平臺上進行了仿真：CPU雙核英特爾Xeon(3.0 GHz)服務器PC，內存為6 GB ddr4-2400k，系統為win7旗艦。兩個基于列表的啟發式算法，異質性最早完成時間算法(HEFT)和異質性關鍵父樹算法(HCPT)，被用作基線算法，因為它們是迄今為止針對異構系統提出的性能最好的算法之一。兩種算法實現過程如圖4所示。

圖4 HEFT和HCPT實現過程

考慮圖4所示示例，為一個簡單的DAG和一個由兩個處理器組成的計算系統，兩個處理器通過一個鏈路相連。當使用HEFT算法時，生成的調度如圖4(a)所示。該算法根據任務優先級形成一個任務序列，然后按順序逐個分配給處理器。當使用HEFT算法時，生成的調度如圖4(b)所示。該算法根據任務優先級形成一個關鍵父樹任務序列，然后按照父樹子樹模式逐個分配給處理器。

表1 參數值集

使用參數值集的所有組合(總共11 520個測試用例)來創建應用程序DAG模型G和異構集群圖模型HC。相對于最小關鍵路徑SLR的調度長度是用于評估DAG調度算法的常用性能度量。然而，由于推送-填充算法被設計用于提高由基線算法生成的調度完整性，所以另一個性能度量，改進SLR，也用于評估考慮的調度算法[15,16]

(5)

式中：SLRBA是基線算法產生調度方案的關鍵路徑SLR，SLRGSA是使用引導搜索算法產生的調度方案的關鍵路徑SLR。

3.2 結果分析

對比算法選取模擬退火(SA)[17]，禁忌搜索(Tabu)[18]，TASK算法[19]，模擬進化(SE)[20]。在SA算法中，初始溫度被設定為初始計劃的完工時間。下一代的解決方案是概率接受的。在Tabu算法中，試圖找到更好的解決方案的跳數決定了調度開銷。在SE中，控制解的搜索時間的選擇偏差B設置為0。參數Y是根據特定任務在所有處理器上的執行時間分配給它的處理器數量。在設置中，Y是20，這表示只有在異構集群系統中考慮的最好的20個處理器。

在圖5中，在平均和最大SLR改進方面比較幾種引導搜索算法的性能。

圖5 作為任務數量函數的SLR改進

根據圖5實驗結果可知，在與選取的SA算法，Tabu算法，TASK算法以及SE算法對比實驗過程中，結合異質性最早完成時間算法(HEFT)和異質性關鍵父樹算法(HCPT)的實驗對比結果分別如圖5(a)～圖5(b)所示。從圖5(a)可以看出，在HEFT框架下，本文算法的SLR指標提升幅度顯著的高于選取的SA，Tabu，TASK算法以及SE幾種對比算法，這表明本文算法的最小關鍵路徑SLR的調度長度提升幅度最高，體現了所提時隙堆棧算法在任務調度算法上的有效性。以上分析結果同樣適用于HCPT框架下的實驗對比分析結果，上述結果驗證了所提算法的有效性。

選取HEFT作為基線算法，利用其它參數值獲得的性能結果趨勢如圖6所示。

圖6 度量指標SLR改進效果對比

根據圖6結果可知，SA算法、Tabu算法、TASK算法、SE算法以及本文算法的SLR指標提升幅度均隨著簇大小參數的增加，這表明增加簇大小參數有助于SLR改進得到提升，因為存在更多的處理器導致更多的機會增加并行性。在圖6(b)中，隨著出度outdegree參數增加，所提算法SLR指標提升幅度增加，大大優于其它算法，而選取的對比算法在出度outdegree參數增加后均出現下降趨勢，這是因為對比算法并未考慮出度outdegree參數的優化問題，而本文算法在設計過程中考慮到了出度outdegree參數問題。這個結果暗示了所提算法在改善外延DAG的調度長度方面優于其它引導搜索算法。圖6(c)中，隨著異構性參數的增加，幾種對比算法的SLR指標提升幅度均出現下降趨勢，但是本文算法相對于選取的對比算法具有更佳的性能表現，上述實驗結果驗證了所提算法的有效性。

同時，為驗證所提算法的計算性能優勢，這里選取上述幾種算法在HCPT和HEFT框架下的計算時間進行實驗對比分析，結果見表2。

根據表2所示算法計算效率實驗對比結果可知，在HCPT和HEFT框架下，本文算法的計算時間分別為2.13 s和3.17 s，均不高于10 s，而選取的幾種對比算法在上述算法框架下的計算時間均高于10 s，相對于本文算法的計算時間均高出近4倍以上，這表明本文算法在上述算法框架下的計算效率要顯著優于所選取的對比算法，主要原因是本文采用的是列表式計算方法，繼承了該類算法的計算效率優勢，而選取的對比計算方法采用的均是進化計算方法，具有較高的計算復雜度，上述實驗結果體現了算法的計算效率優勢。

表2 計算效率對比

4 結束語

針對異構集群系統，提出了一種基于引導搜索策略的靜態調度算法，稱為時隙堆棧算法。該算法從基線算法生成的初始解中搜索改進的解。通過在一個給定的調度計劃中迭代地推送和填充任務，實現試圖改進初始解的效果。該算法在改善諸如HEFT或HCPT等列表調度算法生成的初始解方面特別好，因為時隙堆棧操作修復了列表調度算法的主要缺點。最后通過實驗仿真過程，對所提算法的有效性進行了驗證。下一步研究，主要集中在應用系統開發以及算法理論分析兩個角度，對所提算法進行深入拓展。