公有云環境基于路徑聚簇的工作流費用優化算法

王彬

（四川大學計算機學院，成都610065）

公有云環境基于路徑聚簇的工作流費用優化算法

王彬

（四川大學計算機學院，成都610065）

0　引言

計算科學家進行海量數據的復雜模擬和精確分析，常常用工作流來解決該問題[1]。航天學的Montage將一系列的FITS（彈性圖像傳輸系統，Flexible Image Transport System）格式的圖像合成外天空的星云圖；地震學的CyberShake利用PSHA(概率地震災害分析，Probabilistic Seismic Hazard Analysis)技術形象地刻畫地震災害情況。這些工作流需要大量的計算、內存、帶寬等資源，Montage是帶寬密集型的，CyberShake是內存密集型和帶寬密集型的。由于資源需求過大，工作流的高效資源配置難度增加。

虛擬化、高速網絡和安全技術的成熟，促使云計算的蓬勃發展。由于云計算的彈性使用、按使用量計費的特性，企業和機構逐漸將自身的應用遷移至公有云。云服務提供商擁有數以萬計的主機和存儲設備，向云用戶提供充足的計算資源和存儲資源。由于工作流對計算資源和存儲資源的海量需求，因而將工作流遷移至公有云平臺執行[2-3]。

工作流在公有云的資源分配，對于云服務提供商高效地使用公有云資源和計算科學家降低工作流的執行費用，是至關重要的。因此，資源分配時應充分考慮工作流本身的特性和公有云資源的特征，從而提高資源分配效率，降低工作流執行費用。

1　相關工作

目前，對于傳統的工作流調度算法，由于未考慮綜合工作流的資源需求特征和云服務提供商提供的供給資源的特征，使得工作流的任務資源分配低效，云用戶執行工作流的費用普遍很高，無法真正地將工作流部署至公有云環境[4]。Amazon Simple Workflow Service使用RoundRobin算法進行工作流的調度，將工作流的任務依次分配給未使用的虛擬機實例，并未考慮虛擬機實例的擁有計算資源。異構最早完成時間（HEFT，Heterogeneous Earliest Finish Time）[5]調度算法常用以工作流的調度，降低工作流的執行時間，并未能考慮公有云的計費和虛擬機間的性能干擾，導致執行工作流費用偏高。由于工作流的數據通信量過大，國內外學者也相繼提出了降低通信開銷的調度算法，主要思想是通過聚簇不同的任務成為新的任務集合，然后統一分配至同一資源，從而降低數據的通信量。聚簇算法分為水平聚簇和路徑聚簇，水平聚簇指將處于工作流同一層的任務聚簇，例如水平運行時間平衡算法 （HRB，Horizontal Runtime Balancing）[6]、水平影響因子平衡算法（HIFB，Horizontal Impact Factor Balancing）[7]路徑聚簇指將具有數據依賴關系的任務合合并，比如路徑啟發式聚簇算法（PCH，Path Clustering Heuristic）[8]。文獻[6-8]并未考慮云環境下的彈性資源配置、同構網絡、按使用量付費的特性，使得公有云執行工作流的費用增加，導致機構執行效率降低。

由于工作流的任務個數多、任務依賴和資源需求異構性，使得工作流的資源分配是NP-問題。針對數據密集型的工作流調度算法普遍存在以下問題：一是未考慮任務間的數據通信，導致依賴任務間延遲過大，如基于HEFT調度算法；而是未考慮公有云的計費策略，導致工作流的執行費用過高，如基于PCH調度算法。本文相較其他算法創新之處在于通過對工作流關鍵路徑的任務，根據任務優先級和最早結束時間來進行聚簇，根據工作流的任務需求特性和資源能力及相關費用，找出費用最低且能盡快完成任務的資源進行放置任務，從而降低工作流的總運行時間和運行費用，降低執行機構的費用支出，提高執行機構的執行效率。

2　基于改進PCH的費用優化調度算法

工作流workflow={T，D}可用有向無環圖DAG={V，E}進行表示。任務Task的計算量等同于結點Vertex的權重，任務間的數據通信量等同于邊Edge的權重。任務只有在它的所有前驅任務執行完成并且所需數據準備就緒后，才能開始執行。沒有前驅的任務節點成為開始結點，沒有后驅的任務節點成為結束結點。當存在多個開始結點時，新增一個虛擬開始結點和相應的依賴關系；同理，當存在多個結束結點時，新增一個虛擬結束結點和相應的依賴關系。

公有云向云用戶提供可彈性計算、按使用量付費的虛擬機實例資源。每類虛擬機實例資源擁有不同的計算資源CPU、內存資源MEM、網絡帶寬資源BW。根據虛擬機的處理能力，公有云服務提供商制定不同的價格，并向云用戶收取多個計費周期的費用。需注意的是，不滿一個計算周期的時間，按照一個完整地進行收費。

假定，工作流的所需初始數據和輸出數據都被存放在云存儲服務里，由于數據存儲費用和公有云和云用戶間的數據傳輸都是存在的，公有云內部的數據傳輸是免費的。

2.1概念定義

定義1給定一組虛擬機實例，未調度任務的最早開始執行的時刻被稱為任務最早開始時間ESTTi（Earliest Finish Time）。工作流的任務越早執行完成，其后繼任務被執行的時間就會提前，因而每個任務的最早開始時間決定著整個工作流的執行時間。任務Ti最早開始執行時間ESTTi可由公式 （1），（2），（3），（4）計算而來。

定義2某個任務Ti的最早完成時間EFTTi，其計算如公式（5）所示。任務的最早完成時間越小，其后繼任務的開始執行時間將提前，能有效降低工作流的執行時間。

定義4給定一個工作流和多個虛擬機實例資源，工作流每個任務Ti放置在某個虛擬機實例VMj用∏i表示，工作流調度算法∏用公式（7）表示。

2.2基于改進PCH的工作流調度算法

PCH調度算法從未調度的任務中選擇優先級高和最早開始時間之和最高的進行任務聚簇，但PCH調度并未考慮資源的使用情況和資源費用，從而可能導致任務的執行費用增高。針對PCH的改進主要在①針對工作流所有未調度的任務進行優先級和最早結束時間進行任務排序選擇，聚簇優先級和最早結束時間最大的任務成任務集合;②根據虛擬機的運行情況和費用，綜合考慮任務執行時間和費用的虛擬機資源進行任務放置。基于改進PCH的工作流調度算法如算法1。首先，初始化工作流所有任務的CT、EST、EFT、Pi，此時計算資源和網絡資源按照最好的資源進行計算；其次，根據改進的PCH算法聚簇任務集合，根據執行費用和時間選擇最優的虛擬機實例放置任務；然后，更新所有未調度的任務的EST、EFT；最后，直到所有任務都被調度完成，返回調度策略∏。

基于改進PCH的工作流調度算法：

算法1：

Workflow Scheduling Based on Improved PCH

Input:Workflow，VMs

Output:∏

∏=?;

initialize workflow's tasks'CT，EST，EFT，Pi;

While（tasks is not empty）

get next Cluster which composed of unscheduled tasks having highest EFT and Pi on the same path;

get best resource from VMs based on smallest EFT and Cost;

schedule cluster on best resource，add task allocation to schedule;

updated unscheduled tasks’EST，EFT;

end While

return∏;

3　試驗仿真與分析

為了驗證提出的算法有效性與正確性，故采用CloudSim[9]模擬工作流在公有云的調度。CloudSim專業用于模擬工作負載在數據中心運行的工具。工作流采用Pegasus[10]所產生的兩類科學工作流Montage和CyberShake，Montage的任務節點數量有 25、50、100和1000，CyberShake的任務節點數量有 30、50、100和1000，每個工作流的節點數、計算總量、依賴文件數和數據通信總量見表2。虛擬機實例類型選擇當前A-mazon EC2的計算優化實例，其vCPU個數為2，內存為3.75GB，帶寬量為25Mbps，價格為0.3$/h。文獻[11]指由于虛擬化技術，使得公有云中虛擬機實例的處理能力出現波動。因而，每個虛擬機每隔半小時處理器性能按照變化幅度0.054和帶寬性能按照變化幅度0.04進行動態調整。

表1　

本文對比指標包括執行工作流花費Cost和考慮時間和花費的綜合性能比P。工作流費用由公式（8）計算，其中，TimeVMi表示VMi所使用的時長，T表示公有云服務商計價周期，CostVMi表示VMi在一個計價周期的費用。

綜合性能比P由公式（9）來計算，其中Cost∏為調度算法∏的費用，MakeSpan∏為調度算法∏的執行時間。P值越低，調度算法的綜合性能越高。

改進算法分別與RoundRobin調度算法、HEFT調度算法、PCH調度進行了對比。其一，在執行工作流花費方面，圖1是工作流Montage在不同調度算法下的花費對比圖，圖2是工作流CyberShake在不同調度算法下花費對比圖。PCH和改進PCH優于RoundRobin 和HEFT算法，而改進PCH略低于PCH在Montage工作流調度的花費，但改進PCH在工作流CyberShake明顯優于PCH。其二，在執行工作流的綜合性能比方面，圖3是工作流Montage在不同調度算法下的綜合性能比圖，圖4是工作流CyberShake在不同調度算法下的綜合性能對比圖。改進PCH與HEFT具有較穩定的綜合性能比，優于RoundRobin和PCH，改進PCH在大部分情況下優于HEFT。因而，改進PCH調度算法比其他算法更好地降低工作流執行費用，并且提高機構的執行效率。

圖1　工作流Montage的花費對比圖

圖2　工作流CyberShake的花費對比圖

圖3　工作流Montage的綜合性能比圖　

圖4　工作流CyberShake的綜合性能比圖

4　結語

本文提出了基于改進的路徑聚簇啟發式工作流費用優化調度算法，根據工作流的任務資源需求和任務數據依賴關系，考慮虛擬機的處理能力和費用，為工作流每個任務選擇合適的虛擬機實例資源，降低工作流的執行花費，提高機構的執行效率。實驗仿真表明該調度算法在工作流Montage和CyberShake上能高效地資源分配和任務調度，降低執行工作流的花費，同時提高工作流的綜合性能比。

[1]Juve G,Chervenak A,Deelman E,et al.Characterizing and Profiling Scientific Workflows[J].Future Generation Computer Systems, 2013,29(3):682-692.

[2]Lee Y C,Han H,Zomaya A Y,et al.Resource-Efficient Workflow Scheduling in Clouds[J].Knowledge-Based Systems,2015,80: 153-162.

[3]Zhao Y,Li Y,Raicu I,et al.Enabling Scalable Scientific Workflow Management in the Cloud[J].Future Generation Computer Systems, 2015,46:3-16.

[4]Liu L,Zhang M,Lin Y,et al.A Survey on Workflow Management and Scheduling in Cloud Computing[C]//Cluster,Cloud and Grid Computing(CCGrid),2014 14th IEEE/ACM International Symposium on.IEEE,2014:837-846.

[5]Durillo J J,Prodan R.Multi-objective Workflow Scheduling in Amazon EC2[J].Cluster Computing,2014,17(2):169-189.

[6]Chen W,da Silva R F,Deelman E,et al.Using Imbalance Metrics to Optimize Task Clustering in Scientific Workflow Executions[J]. Future Generation Computer Systems,2015,46:69-84.

[7]Chen W,Da Silva R F,Deelman E,et al.Balanced Task Clustering in Scientific Workflows[C].eScience(eScience),2013 IEEE 9th International Conference on.IEEE,2013:188-195.

[8]Bittencourt L F,Madeira E R M.A Performance-Oriented Adaptive Scheduler for Dependent Tasks on Grids[J].Concurrency and Computation:Practice and Experience,2008,20(9):1029-1049.

[9]Calheiros R N,Ranjan R,Beloglazov A,et al.CloudSim:a Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms[J].Software:Practice and Experience,2011,41(1):23-50.

[10]Deelman E,Vahi K,Juve G,et al.Pegasus,a Workflow Management System for Science Automation[J].Future Generation ComputerSystems,2015,46:17-35.

[11]Bux M,Leser U.DynamicCloudSim:Simulating Heterogeneity in Computational Clouds[J].Future Generation Computer Systems,2015,46:85-99.

Public Cloud;Workflow Scheduling;Path Clustering;Cost Optimaztion

Workflow Cost Optimization Scheduling Algorithm Based on Path Clustering in Public Cloud

WANG Bin
（College of Computer Science，Sichuan University，Chengdu 610065）

1007-1423（2016）03-0008-05

10.3969/j.issn.1007-1423.2016.03.002

王彬（1991-），男，四川廣安人，在讀碩士研究生，研究方向為云計算資源調度

2015-12-18

2016-01-10

針對工作流在公有云環境執行的費用過高問題，提出基于路徑聚簇的費用優化調度算法。算法結合工作流的任務資源、任務依賴等特征，計算任務的最早開始時間、最早完成時間和優先級，聚簇最早完成時間和優先級高的任務進行統一放置，從而減少任務間的數據通信量，降低工作流的執行時間和費用，從而提高機構的執行效率。平臺仿真顯示改進后算法可有效地降低執行工作流的花費，提高執行工作流的綜合性能比。

公有云；工作流調度；路徑聚簇；費用優化

To solve outrageous cost of workflow execution in public cloud environment,proposes a workflow scheduling algorithm based on path clustering on the same path.Combining tasks’resources requirements and tasks dependence of workflow will be scheduled,computed earliest start time,earliest finish time and priority of tasks,clustered tasks have the highest earliest finish time and priority,thus reduces data traffic between tasks,shortens workflow makespan and reduce workflow running cost,and improves organization efficiency.Platform emulation shows that the improved algorithm can effectively reduce cost of executing workflow,improve the comprehensive performance of workflow execution.