王彬

（四川大学计算机学院，成都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.