王彬

（四川大學(xué)計算機學(xué)院，成都610065）

公有云環(huán)境基于路徑聚簇的工作流費用優(yōu)化算法

王彬

（四川大學(xué)計算機學(xué)院，成都610065）

0　引言

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

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

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

1　相關(guān)工作

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

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

2　基于改進PCH的費用優(yōu)化調(diào)度算法

工作流workflow={T，D}可用有向無環(huán)圖DAG={V，E}進行表示。任務(wù)Task的計算量等同于結(jié)點Vertex的權(quán)重，任務(wù)間的數(shù)據(jù)通信量等同于邊Edge的權(quán)重。任務(wù)只有在它的所有前驅(qū)任務(wù)執(zhí)行完成并且所需數(shù)據(jù)準(zhǔn)備就緒后，才能開始執(zhí)行。沒有前驅(qū)的任務(wù)節(jié)點成為開始結(jié)點，沒有后驅(qū)的任務(wù)節(jié)點成為結(jié)束結(jié)點。當(dāng)存在多個開始結(jié)點時，新增一個虛擬開始結(jié)點和相應(yīng)的依賴關(guān)系；同理，當(dāng)存在多個結(jié)束結(jié)點時，新增一個虛擬結(jié)束結(jié)點和相應(yīng)的依賴關(guān)系。

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

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

2.1概念定義

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

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

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

2.2基于改進PCH的工作流調(diào)度算法

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

基于改進PCH的工作流調(diào)度算法：

算法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]模擬工作流在公有云的調(diào)度。CloudSim專業(yè)用于模擬工作負載在數(shù)據(jù)中心運行的工具。工作流采用Pegasus[10]所產(chǎn)生的兩類科學(xué)工作流Montage和CyberShake，Montage的任務(wù)節(jié)點數(shù)量有 25、50、100和1000，CyberShake的任務(wù)節(jié)點數(shù)量有 30、50、100和1000，每個工作流的節(jié)點數(shù)、計算總量、依賴文件數(shù)和數(shù)據(jù)通信總量見表2。虛擬機實例類型選擇當(dāng)前A-mazon EC2的計算優(yōu)化實例，其vCPU個數(shù)為2，內(nèi)存為3.75GB，帶寬量為25Mbps，價格為0.3$/h。文獻[11]指由于虛擬化技術(shù)，使得公有云中虛擬機實例的處理能力出現(xiàn)波動。因而，每個虛擬機每隔半小時處理器性能按照變化幅度0.054和帶寬性能按照變化幅度0.04進行動態(tài)調(diào)整。

表1　

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

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

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

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

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

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

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

4　結(jié)語

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

[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-），男，四川廣安人，在讀碩士研究生，研究方向為云計算資源調(diào)度

2015-12-18

2016-01-10

針對工作流在公有云環(huán)境執(zhí)行的費用過高問題，提出基于路徑聚簇的費用優(yōu)化調(diào)度算法。算法結(jié)合工作流的任務(wù)資源、任務(wù)依賴等特征，計算任務(wù)的最早開始時間、最早完成時間和優(yōu)先級，聚簇最早完成時間和優(yōu)先級高的任務(wù)進行統(tǒng)一放置，從而減少任務(wù)間的數(shù)據(jù)通信量，降低工作流的執(zhí)行時間和費用，從而提高機構(gòu)的執(zhí)行效率。平臺仿真顯示改進后算法可有效地降低執(zhí)行工作流的花費，提高執(zhí)行工作流的綜合性能比。

公有云；工作流調(diào)度；路徑聚簇；費用優(yōu)化

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.