兼顧費用與公平的帶通信開銷的多有向無環圖調度
2015年全國開放式分布與並行計算學術年會(DPCS2015)論文
作者：王宇新曹仕傑郭禾陳征陳鑫
摘要：針對雲環境下多有向無環圖（DAG）工作流的調度算法應考慮執行時間、費用開銷、通信開銷、公平性等多個指標的問題，在模型帶通信開銷的DAG（CADAG）的基礎上結合公平性算法提出一種優化完成時間的後向求異（BD）原則與兼顧費用和公平的多DAG調度策略CAFS。CAFS調度策略分為兩個階段：預調度階段利用帶通信開銷的工作流費用優化（CACO）算法在考慮通信開銷的同時求解所有任務的最優服務並優化費用，采用fairness算法得到較公平的調度順序；調度階段采用BD原則，根據在預調度階段得出的調度順序進一步優化整體的完成時間並執行調度。實驗結果表明，CAFS調度算法具有較好的公平性，在不提高費用的基礎上時間減少19.82%。
關鍵詞：多有向無環圖調度；通信開銷；費用；公平；工作流
中圖分類號： TP393
文獻標誌碼：A
0引言
雲環境中用戶對使用的服務付費已經成為一種趨勢。雲服務提供商在大型服務器上部署多種服務[1]，根據各個服務的服務質量（Quality of Service， QoS）製定收費標準。用戶向服務商提交的工作流由這些服務完成，每個工作流中包含多個任務，每個任務可以由若幹個服務完成。雲環境下對多個用戶提交的工作流及其中的任務調度應考慮執行時間、費用開銷、通信開銷、公平性等多個指標，通常是一個NPhard問題[2]。單個工作流通常使用有向無環圖（Directed Acyclic Graph， DAG）描述。工作流調度是指從雲環境中的眾多服務中根據用戶的特定需求確定最優服務並假定所有服務都能提供與承諾一致的服務質量。針對單DAG截止前約束的優化調度已有諸多學者作了研究，苑迎春等[2-4]提出的DBL（Deadline Bottom Level）基於分層算法，在分層之後逐層進行局部優化；在此基礎上又提出了BSRD（Backward Serial Reduction with Deadline）對分層算法中的時間窗口重新定義，能為一個串歸約得到局部最優解。劉燦燦等[5-6]的截止期約束逆向分層（Temporal Consistency based Deadline Bottom Level， TCDBL）算法基於DBL，研究工作流的時序特征，進一步優化了工作流的執行費用。然而上述算法均沒有考慮到任務間跨節點的數據傳輸帶來的不可忽視的通信開銷[7]。郭禾等[8]提出的帶通信開銷的工作流費用優化（Communication Aware Cost Optimization，CACO）基於分層算法，並提出FC（Forward Consistent）規則求解考慮通信開銷情況下的最小完工時間，優化了執行費用。上述這些算法都是考慮單DAG在一組資源下的調度執行，而在雲環境下往往需要同時調度多DAG。多個DAG共享一組分布式資源，由於不同DAG間的競爭，必然存在調度時間上的公平性問題[9]。Zhao等[10]提出了DAG滯後程度（Slowdown）的定義，並提出基於Slowdown的公平性算法，有效地解決了多個DAG的公平性問題。Henri等[9]提出了一種不折中公平性且能優化並行任務調度性能的方法。田國忠等[11]提出的PDTC（based on the Probe of the Total Cost Decrease）使用吞吐量最大化算法預調度工作流，若仍有冗餘時間則具備優化的條件；但其目標均為單一優化最小完成時間，沒有考慮到雲環境中各任務的執行費用問題。
綜上，本文提出CAFS（Communication Aware Fair Scheduling）將CACO應用於雲環境下的考慮通信開銷的多DAG調度以優化執行費用，使用公平性算法調度多個DAG以提高公平性，提出後向求異（Backward Difference， BD）原則用於優化CACO在公平性算法下的時間性能。實驗表明，CACO運用於公平性算法比DBL、正向分層算法（Deadline Top Level， DTL）、TCDBL性能好，CAFS能夠在不增加費用和不降低公平性的基礎上優化工作流的完成時間。
1帶通信開銷的多工作流模型
帶通信開銷的DAG工作流模型CADAG（Communication AwareDAG）[8]假設n個用戶提交的DAG（G1，G2，…，Gi，…，Gn）在雲環境下的q個服務資源（M1，M2，…，Mi，…，Mq）上同時進行調度[11]。帶通信開銷的DAG模型可以表達為G=〈V，E，S〉，其中V={0，1，…，v}表示DAG中的任務；E={eij}（i、 j∈V）為有向邊的集合，eij為節點i、 j的通信開銷；S表示服務集，任務i的一個候選服務集合表示為S（i）={Sik|Sik∈S}，k∈[1，S（i）]，S（i）為服務集合的規模。Sik=〈t，c，m〉表示可以完成任務i的一個服務，Sik.t為使用此服務執行i的執行時間；Sik.c為執行費用（模型中的時間與費用均是相對的，沒有具體單位）；Sik.m為此服務所在的服務資源編號。多工作流模型由多個CADAG構成。通信開銷是任務之間進行數據傳輸所需的時間，當兩個具有數據依賴的任務所選的服務位於不同的服務資源時，就會產生通信開銷。i， j∈V且i∈pre（j），若任務i、 j選定服務Sip∈S（i）與Sjq∈S（j），此時兩個任務間的通信開銷可由式（1）確定：
Trans（i， j）=0，Sip.m=Sjq.meij，其他 （1）
2CAFS調度算法
2.1CACO算法
本課題組在文獻[8]中提出CADAG與一種基於CADAG的費用優化算法CACO。CACO第一步利用FC原則在考慮通信開銷的基礎上確定最小完工時間，FC原則是指：采用遞歸的方法確定每個任務的最快服務（使任務最早完成的服務）及最早完成時間，僅當此任務的所有前驅任務的最快服務都確定下來才能確定此任務的最快服務。CACO調度分為兩個階段：分層階段和調度階段。分層階段按照DBL的逆向分層方法，求解每一層的時間窗口，進一步求得最小完工時間TBLmin。當給定截止期δ>TBLmin存在冗餘時間時，可以進一步對其進行費用優化。CACO調度階段采用動態規劃的方法調整所有任務的最終最早開始時間和最晚結束時間，這樣可以利用任務在其時間窗口內的“時間碎片”以得到截止期內的費用最優服務，任務i的最優服務Sbest-i表示若任務i選擇該任務能得到當前局部最優解。CACO的時間複雜度是O（v2），v為DAG的任務數量，又知先前基於分層算法的時間複雜度也為O（v2），可得CACO沒有增加時間複雜度。