王柳婧 蔣一翔 徐元根

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

0 引 言

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

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

本文重點關(guān)注于利用圖分割方法優(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é)點。通常，可基于工作流中任務(wù)間的依賴性把工作流表示為有向無循環(huán)圖DAG，圖的頂點表示計算單元，邊表示任務(wù)依賴性。圖分割的目標是為了有效地并行計算決定計算與數(shù)據(jù)的分割，即通過將頂點集劃分為n個子集并均分至n個計算節(jié)點上，同時通過分區(qū)間的邊修剪最小化節(jié)點間的通信量。為了解決以上問題，本文設(shè)計了一種多約束圖分割的工作流調(diào)度算法，實現(xiàn)工作流中通信代價的最小化，并有效降低工作流執(zhí)行時間。

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

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

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

(a) 低效任務(wù)分配

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

(a) 對應(yīng)圖1(a)的調(diào)度

(b) 對應(yīng)圖1(b)的調(diào)度圖2 調(diào)度結(jié)果

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

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

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

圖3 Montage工作流的DAG結(jié)構(gòu)

1.3 標準圖分割

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

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

圖4 標準圖分割

圖5 均衡圖分割

2 基于MCGP的工作流調(diào)度

2.1 多約束圖分割機理

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

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

圖6 多約束圖分割示例

2.2 決定任務(wù)階段

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

圖7 工作流DAG的權(quán)重矢量

2.3 權(quán)重矢量

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

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

3 仿真實驗

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

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

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

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

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

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

圖9 工作流調(diào)度時間

4 結(jié) 語

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