基于多約束圖分割機制的科學工作流調度

王柳婧 蔣一翔 徐元根

(浙江中煙工業(yè)有限責任公司寧波卷煙廠 浙江 寧波 315504)

0 引 言

天文學、粒子物理學和生命科學等諸多科學領域的數(shù)據(jù)量正成爆炸式增長。這種數(shù)據(jù)密集型科學應用需要高性能的系統(tǒng)以科學工作流的形式最大化吞吐量[1]。而科學工作流系統(tǒng)的最關鍵問題即是工作流調度，其目標是決定資源與任務間的匹配與執(zhí)行。常見的調度算法如Min-Min算法[2]和HEFT算法[3]均以優(yōu)化工作流完成時間makespan為目標的，而makespan則取決于工作流任務的計算代價和通信代價。

文獻[4]提出一種基于圖割的調度算法，充分考慮了減少各個數(shù)據(jù)中心間數(shù)據(jù)的傳輸量，但沒有考慮各個數(shù)據(jù)中心的計算能力和負載情況。實際情況中，即使各個數(shù)據(jù)中心的計算能力相同，由于工作流任務的不同，其負載也可能不同。文獻[5]提出一種云工作流中間數(shù)據(jù)存儲算法，以降低工作流執(zhí)行開銷。該算法首先根據(jù)中間數(shù)據(jù)的起源生成中間數(shù)據(jù)關系圖，然后得出生成代價，再將生成代價和存儲代價對比作出是否存儲該數(shù)據(jù)的決策。文獻[6]將常規(guī)的圖分割方法應用于工作流調度中，算法賦予圖的頂點權值，并以此為根據(jù)進行邊的切割，得到權值最小的圖劃分情況。但算法僅考慮了一維權值，與實際的工作流任務調度場景并不符合。

本文重點關注于利用圖分割方法優(yōu)化工作流執(zhí)行過程中的數(shù)據(jù)傳輸量[7]。圖論是表示計算數(shù)據(jù)依賴性的常用模型，給定圖G=(V,E)，V表示頂點集合，V={v1,v2,…,vn}，E表示邊集，E=V×V。如果(vi,vj)∈E，則頂點vi和vj是鄰居節(jié)點。通常，可基于工作流中任務間的依賴性把工作流表示為有向無循環(huán)圖DAG，圖的頂點表示計算單元，邊表示任務依賴性。圖分割的目標是為了有效地并行計算決定計算與數(shù)據(jù)的分割，即通過將頂點集劃分為n個子集并均分至n個計算節(jié)點上，同時通過分區(qū)間的邊修剪最小化節(jié)點間的通信量。為了解決以上問題，本文設計了一種多約束圖分割的工作流調度算法，實現(xiàn)工作流中通信代價的最小化，并有效降低工作流執(zhí)行時間。

1 工作流中的數(shù)據(jù)傳輸

1.1 工作流調度及數(shù)據(jù)傳輸

工作流示例討論數(shù)據(jù)傳輸問題如圖1所示。該工作流請求一個存儲節(jié)點中存儲的四個輸入文檔數(shù)據(jù)，并由兩個階段組成：任務A和任務B。在任務A階段，每個任務接收一個輸入文檔。在任務B階段，每個任務接收來自于任務A階段的兩個輸入。所有任務執(zhí)行于包括兩個計算節(jié)點的分布式系統(tǒng)中。對于該工作流的調度，作如下兩個假設：(1) 分布式系統(tǒng)為同質的，且兩個計算節(jié)點擁有相同性能；(2) 每個階段中的所有任務需要相同的計算代價，且在每個階段中的所有數(shù)據(jù)傳輸擁有相同的通信代價。以HEFT作為調度算法進行該工作流的調度，首先計算任務的升秩值ranku，由于任務A1～A4的計算代價相同，故4個任務的ranku是相同的，此時，從任務A1～A4中隨機選擇一個進行調度。假設首先選擇任務A1。接下來基于最早完成時間EFT選擇執(zhí)行任務A1的計算節(jié)點。然而，由于只有輸入數(shù)據(jù)量均是相同的，無論節(jié)點如何分配EFT均是相同的，故任務A1的計算節(jié)點也是隨機選擇的。然后，其他節(jié)點被選擇執(zhí)行接下來被選擇的任務。最終，在HEFT算法下，任務A1～A2被隨機分配至計算節(jié)點。因此，圖1(a)和圖1(b)中任務分配的概率是相同的。同時，HEFT算法的目標函數(shù)執(zhí)行跨度makespan對于圖1(a)和圖1(b)也具有相同的值，如圖2所示。

(a) 低效任務分配

(b) 高效任務分配圖1 任務分配與數(shù)據(jù)傳輸

(a) 對應圖1(a)的調度

(b) 對應圖1(b)的調度圖2 調度結果

然而，圖1(a)和圖1(b)中的數(shù)據(jù)傳輸量是不同的。圖1(a)中數(shù)據(jù)傳輸有三次，而圖1(b)僅有一次。該示例表明先前階段中任務A的節(jié)點分配對于接下來的依賴性中(即A1,A2→B1)的通信代價擁有重要影響。

1.2 Montage科學工作流的數(shù)據(jù)傳輸

以下以更為復雜的科學工作流結構Montage[8]作為示例進行說明，其結構如圖3所示。Montage工作流由包括若干任務的8個階段組成。例如：第一階段為mProjectPP，即在目標飛行器上設計一個任務代表一個鏡像。在每個階段中的任務數(shù)量取決于輸入文檔的數(shù)量(或數(shù)以萬計)。圖3中兩個并行階段擁有與圖1中相似的依賴模式，即單個任務接收前任任務的多個輸入，如mProjectPP→mDiff和mBackground→mAdd1(前一mAdd)。這些階段通過任務依賴性進行分布，并構建為單個工作流DAG。為了最小化這種復雜工作流結構中的數(shù)據(jù)傳輸，需要基于DAG的所有依賴性決定如何將節(jié)點分配至任務。

圖3 Montage工作流的DAG結構

1.3 標準圖分割

圖分割是復雜工作流中為了最小化數(shù)據(jù)傳輸分配任務至計算節(jié)點的常用方法[9]。給定圖G=(V,E)，V為頂點集，E為邊集，將V平均劃分為n組，V1,V2,…,Vn，即|V1|=|V2|=…=|Vn|，使得在尾節(jié)點屬于不同子集的同時其邊的數(shù)量達到最小。以上的圖分割問題為NP-完全問題，可擴展為圖中每個頂點或邊擁有一個權重的情形。如果頂點擁有權重，則每個子集中頂點的權重之和是相等的；如果邊擁有權重，則其尾節(jié)點屬于不同子集的邊的權重之和是最小化的。定義以上分割為標準圖分割。

對于工作流DAG，頂點和邊分別代表任務和數(shù)據(jù)依賴，本文以最小化數(shù)據(jù)傳輸為目標，等同于最小化邊的剪切數(shù)。當應用標準圖分割方法至Montage工作流的DAG結構時，其結果如圖4所示。圖中顯示出前任任務被分派為右側的兩組，終端任務被分派為左側的一組，這是由于所有頂點被平均劃分，而未考慮任務階段，即標準圖分割無法反映任務的并行性。圖5是本文設計的分割結果，其頂點在每個階段是均衡的。因此，工作流DAG的分割算法需要考慮每個并行階段中任務的均分要求，使得邊修剪最小化。

圖4 標準圖分割

圖5 均衡圖分割

2 基于MCGP的工作流調度

2.1 多約束圖分割機理

比較標準圖分割中頂點權重為單一的一維數(shù)值，多約束圖分割MCGP中的頂點權重為包括多個值的矢量。MCGP的目標是均衡每一維度中的權重值之和。圖6為MCGP的實現(xiàn)范例。范例中，圖中的頂點被賦予二維權重矢量，圖6(a)是邊修剪數(shù)為4得到的分割，然而，此時第二維的權重和分別為26和14，這是一種不均衡分割。圖6(b)是邊修剪數(shù)為5(在于圖6(a)中的4)得到的分割。然而，兩個維度上的權重之和是均衡的，這即為MCGP的分割方法，其目標是使所有維度上的權重矢量被同步得均衡。

為了最小化復雜工作流結構中的數(shù)據(jù)傳輸，需要基于DAG中所有任務間的依賴性決定如何將節(jié)點分配至任務。本文以最小化數(shù)據(jù)傳輸為目標，等同于最小化邊的剪切數(shù)。相比傳統(tǒng)圖分割方法的不均衡分割，MCGP算法可以通過所有維度上權重矢量的同步均衡，使得代表任務的頂點間的數(shù)據(jù)傳輸量是所有可能邊修剪情形中最小化的，更加準確地描述工作流結構中任務的并行性并將任務并行擴展至最優(yōu)，從而降低任務間的通信代價(邊權重即代表通信代價)。

圖6 多約束圖分割示例

2.2 決定任務階段

在利用MCGP對工作流DAG進行分割前，需要定義任務階段，在任務階段中任務可基于工作流的依賴性并行執(zhí)行。該過程等同于工作流DAG的頂點集V被劃分為子集P1,P2,…,Pl。任務階段的具體定義方式如下：不存在前驅任務的任務定義為第一階段，表示為P1={vk|(vj,vk)?E，vj∈V}。緊鄰第一階段的任務定義為第二階段任務。因此，第i階段Pi可通過遍歷任務依賴性得到。如果一個任務依賴于不同階段的多個任務，則其階段定義為最大階段的下一階段。該算法可表示為Pi={vk|(vj,vk)∈E，vj∈Pi-1且不存在vj∈Pi′，i′≥i，i≥2}。圖7是Montage工作流的任務階段定義結果。

圖7 工作流DAG的權重矢量

2.3 權重矢量

以上定義權重矢量wi。權重矢量的長度為Q中階段的數(shù)量，即|Q|=max{di}。則于第i階段Pi∈Q，wi的di維度設置為1，wi的其他所有維度設置為0。對于其他階段Pi?Q，權重矢量wi設置為0矢量。例如：如果|P1|≥n，|P2|

以下分析算法在每個階段中的工作機制。考慮一個權重DAG，每個頂點權重以權重矢量的第di維度的值代替，那么，第i階段的頂點權重為1，其他階段為0。如果應用標準圖分割進行劃分，頂點均分僅在第i階段可完成，且其他階段的劃分不存在約束，其權重為0。同時，最小化邊修剪的目標可應用于整個DAG。而MCGP算法可在所有階段同步實現(xiàn)均分，并最小化邊修剪量。該算法中，權重矢量的維度在任務階段中未被分配，且頂點數(shù)量小于分割量，即|Pi|

3 仿真實驗

本節(jié)利用一個集群系統(tǒng)以Montage工作流作為測試源進行實驗分析，工作流的輸入數(shù)據(jù)為2MASS影像數(shù)據(jù)集的子集[10]，表1給出了該數(shù)據(jù)集的具體參數(shù)[11]。表2給出了集群環(huán)境的相關性能配置，共使用8個計算節(jié)點進行工作流執(zhí)行，因此，工作流DAG可分割為8個分組。在初始狀態(tài)下，所有輸入文檔存儲于單個節(jié)點上。

表1 輸入數(shù)據(jù)集

表2 集群系統(tǒng)配置

實驗通過以下三種算法進行工作流的任務分配：輪轉調度算法[12]、異構最早完成時間算法HEFT以及本文提出的MCGP算法。輪轉調度算法是一種最簡單最公開的任務調度方法，該算法將所有的就緒任務按照先來先服務的原則組織成一個隊列，然后為所有任務分配一個時間段(即時間片)，依次在時間片結束前進行相應任務的調度與執(zhí)行。HEFT算法主要是通過賦予任務不同的秩值，定義任務的優(yōu)先級，決定任務最優(yōu)的調度次序，然后以最早完成時間為標準選擇執(zhí)行任務的節(jié)點，可以以較低的時間復雜度得到更少的任務執(zhí)行時間。選擇兩種算法的依據(jù)在于：前者是任務調度系統(tǒng)最為公平的算法，尤其適合于調度串型結構的任務；后者是任務調度效率較高的經(jīng)典算法，但僅考慮了任務執(zhí)行的代價問題，未考慮任務結構間的通信問題。由于所測試的工作流結構為Montage工作流，其結構中混合具有串型和并型任務，利用這兩種算法執(zhí)行工作流可以觀察算法對相應工作流結構的適應情況，進而得出本文算法的優(yōu)勢所在。

此外，本文研究了可產(chǎn)生相同結果影像數(shù)據(jù)的兩種不同模式的Montage工作流，區(qū)別在于mAdd1階段。該階段中，目標區(qū)域被劃分為n×m個子區(qū)域，重疊部分的輸入影像在mAdd程序中被聯(lián)立為子影像。子區(qū)域的大小配置為工作流的一個參數(shù)。實驗中，分別研究4×4和8×4兩種模式的工作流。由于實驗配置部分在集群系統(tǒng)中執(zhí)行工作流的節(jié)點數(shù)量設置為8，為了使單個節(jié)點上分配的子區(qū)域數(shù)量為整數(shù)，工作流模式需要設置為8的倍數(shù)，則以上兩種模式下分配于每個節(jié)點上的子區(qū)域數(shù)量分別為2和4。可進一步增加8×8模式的工作流，但此時單個節(jié)點上的子區(qū)域數(shù)增加至8，子區(qū)域的增多可能帶來遠程數(shù)據(jù)訪問的增多，這對于算法而言，在降低數(shù)據(jù)傳輸量上是不利的。

實驗1觀察在每種算法進行工作流調度時所訪問的文檔數(shù)據(jù)量的變化。每種情況下，所有數(shù)據(jù)訪問的總量為24 GB。工作流執(zhí)行過程中遠程數(shù)據(jù)訪問的比率如圖8所示。在4×4模式中，遠程數(shù)據(jù)訪問比率為：1) RR算法為87.9%；2) HEFT算法為47.4%；3) MCGP算法為14.0%。結果表明MCGP算法可以極大地降低節(jié)點間的數(shù)據(jù)訪問比率。HEFT算法的性能差于MCGP，這是由于MCGP擁有更好的初始節(jié)點分配模式。在8×4模式中，MCGP算法的遠程數(shù)據(jù)訪問比率為15.4%，大于4×4模式，這是由于區(qū)域的擴大本身會帶來最多的遠程數(shù)據(jù)訪問，但仍然小于另種兩種算法。綜合來看，MCGP在降低工作流執(zhí)行過程的數(shù)據(jù)訪問量是有效可行的。

圖8 遠程數(shù)據(jù)訪問比率

實驗2觀察每種算法進行工作流調度的時間變化，結果如圖9所示。對于MCGP算法，調度時間中包括約0.03 s的圖分割時間，該時間遠小于整個工作流的調度時間。在4×4模式中，MCGP算法比較RR算法和HEFT算法在調度時間上分別降低了31%(53 s)和22%(34 s)，表明MCGP在調度效率性能是更優(yōu)的。調度時間的降低比率31%小于遠程數(shù)據(jù)訪問比率74%，這是由于調度時間包括數(shù)據(jù)讀、寫和計算等時間，而遠程數(shù)據(jù)訪問比率的降低僅影響數(shù)據(jù)讀取時間。從4×4模式到8×4模式下MCGP的調度時間增加較小是由于分割執(zhí)行較差，但調度效率仍然可以得到提高。同時，MCGP算法中53 s的調度時間降低僅通過0.03 s的圖分割代價得到。綜合分析，MCGP在改進工作流執(zhí)行效率的性能也是有效可行的。

圖9 工作流調度時間

4 結 語

為了降低工作流應用中節(jié)點間的數(shù)據(jù)通信開銷，本文設計了一種基于多約束圖分割的工作流調度算法。算法通過多維度的頂點權重矢量機制和有向邊的修剪機制，在所有維度上實現(xiàn)了權重和的均衡，進而得到了最小化的任務間數(shù)據(jù)傳輸量，降低通信代價。利用Montage工作流進行實驗，結果表明，算法在降低數(shù)據(jù)通信量和工作流調度效率方面是有效可行的。