九种智能算法在科学工作流调度中的应用比较

马敬敬，阎朝坤, 郑金格

(河南大学 计算机与信息工程学院，河南 开封475000)

工作流作为一种面向过程建模和管理的核心技术，能有效地描述活动及活动间的复杂约束关系，已成为大规模科学应用的典型范式.由于涉及大量的数据集和复杂运算，对计算和存储能力有很高的要求.当前，科学工作流应用普遍被部署到一些网格系统中执行，如TeraGrid，EGEE，Open ScienceGrid 等.为了管理科学工作流的执行，一些工作流管理系统被构建，著名的有Khajemohammadi H[1],GrADS[2],Kepler[3],Pegasus[4],SwinDeW-G.作为科学工作流管理系统的一个重要组成部分，工作流调度的目的是为工作流的子任务选择最合适的资源执行，保障工作流的顺利完成并满足用户的QoS 要求，调度策略的优劣对系统性能有明显的影响.工作流执行时间通常是用户最为关注的QoS指标，其中以优化工作流执行时间为目标的研究已经很多.典型算法有：列表调度算法HEFT 和CPOP，基于分层技术的动态关键路径调度算法DCP和DLS等，这些都属于启发式算法.除此之外，智能算法在工作流调度中也日益受到关注，一些实际的工作流管理系统也开始加入智能算法.比如ASKALON系统，已经把遗传算法这一智能算法应用在实际科学工作流调度很多年了.笔者考虑了九种智能算法在工作流调度中的应用，并对其性能进行了比较.

1 相关研究

目前为止，很多智能算法应用于工作流调度中，智能算法在工作流调度中表现出良好的性能.如美国的J.H.Holland教授提出了基于遗传算法(GA)的工作流调度，相对于HEFT或CPOP算法来说，具有良好的全局搜索能力.Pandey S, Wu L[5]等人提出了将基于粒子群优化算法的启发式算法(PSO)用于云资源调度中.Yu J和Buyya R[6]等利用遗传算法解决有最后期限和费用约束的工作流调度问题.还有Chen W N和Zhang J[7]，通过优化蚁群算法(ACO)，解决了网格工作流调度问题上不同的QoS要求.

此外，许多启发于自然界和仿生物学的智能算法，在一些复杂的实际工程问题上有广泛应用.混合蛙跳算法(SFLA)[7]以其结构简单、参数少、全局搜索能力强，在水资源网络优化、函数优化、图像处理等问题方面应用良好.布谷鸟搜索算法(CS)[8]具有参数少、适应性好、搜索路径优的特点，多应用于工程优化问题和智能计算问题中.蝙蝠算法(BA)[8]以其结构简单、鲁棒性强的特点，则被广泛应用于全局工程优化问题、结构优化问题中.人工蜂群算法(ABC)[9]具有很强鲁棒性、算法灵活、适应性强，应用到神经网络训练、多图像处理、蛋白质检测等许多实际问题中.笔者对九种智能算法GA,PSO,SFLA,ACO,ABC,CS,BA,CRO以及MA在工作流调度中的应用[10]进行了分析和比较.

2 问题描述

2.1 系统模型

用户由系统接口输入要执行和测试的工作流,系统定义模块由收到的工作流信息对该工作流进行定义，并将定义好的工作流发送至执行引擎.执行引擎接收到工作流后，将工作流中的各任务映射到相应的系统资源上，再向调度引擎发送调度请求.调度引擎接收调度请求，并从资源管理器获取资源信息，调度完成相应任务.每次调度完成后调度引擎会将调度过的工作流信息反馈给执行引擎，以便执行引擎更新当前工作流执行状态，进行后续的调度请求工作，不断循环，直至完成工作流调度.工作流管理系统的系统模型如图1所示.

图1 工作流管理系统模型图

2.2 应用模型

工作流中的各个子任务和子任务执行次序的约束关系将转化为一个(有向无环图)DAG来表示[8].在DAG中，节点表示工作流中的各个任务，而有向边则用于表示各子任务间执行顺序的约束关系.以有向无环图G={V,E}为例，节点集合V={V1,V2,…,Vn}中，各元素分别表示工作流的每一个任务，有向边集合E={e12,e13,…,e(n-1)n}中，各元素分别表示工作流中事务流程的约束关系，即对于有向边eij=(vi,vj)，表示任务vi先于任务vj执行.对于表示整个工作流的DAG，还会增加两个虚拟节点，一个作为在工作流执行的起始节点，连接向入度为0的节点，另一个作为工作流执行的结束节点，连接向出度为0的节点.工作流调度中的虚拟机资源将转化相应的资源节点，工作流调度是用于子任务的映射.

2.3 调度问题

工作流调度问题的求解过程，可以描述为：在用户设定的QoS约束下，为工作流各子任务找到合适的资源节点，即寻找工作流各子任务到资源节点的映射方案，可以表示为：

S:{t1,…,tm}×{r1,…,rn}→{0,1}

m为子任务节点的个数，n为资源节点个数.

本文QoS主要针对工作流调度的完成时间，即：最小完成时间.

3 智能算法及应用

大多数智能算法启发于自然界，来源于仿生物学.人们通过模拟自然界中的生物进化过程，将抽象的优化思想运用到科学问题的求解中，从而得出了设计这样一类用来解决复杂优化问题的算法.近几十年来，人们不断提出了许多智能算法，各种智能算法也不断被改进.但智能算法的基本流程通常如上图2所示. 算法运行之初，要先初始化相关参数，用以随机或按一定规则产生一个初始种群或位置，即最初的解.然后，在整个解空间上按一定规则生成新的解，即进行解的全局搜索.直到判断得到更优解后，会根据解的不同情况，利用相应算子，在更优解附近进行局部搜索，进一步寻找最优解.直到求得最优解符合终止条件，则输出结束，否则进行下一代的搜索.

在工作流调度问题中，许多智能算法被应用，智能算法在工作调度中也表现出较于传统工作流调度算法更好的性能.蚁群优化算法灵感来源于蚂蚁在寻找食物过程中发现路径的行为，模拟蚂蚁以信息素获取较短路径信息的方法.在工作流调度中，通过优化工作流调度时的路径选择策略，提高了工作流调度的效率.化学反应算法模拟分子间化学反应而引起的分子间的各种相互作用，不断迭代和比较，可在工作流调度中避免搜索过程陷入局部最优，优化工作流调度费用.智能算法在工作流调度问题中的应用，极大地丰富和优化了求解策略，提高了服务质量.

智能算法的工作流调度与启发式不同，涉及解的构造，迭代过程,下面针对智能算法解的表示进行说明.

图2 智能算法基本流程图

任务的分配串和任务的调度串分别用于控制任务的资源分派和调度顺序,对工作流中的任务进行调度的求解过程即是对任务的分配串进行编码的过程.由于任务的调度串对任务的调度顺序进行了约束，则在构造用于任务到资源映射、控制任务资源分派的分配串时，就要保证该分配下对于某一任务的调度能够在其之前的约束任务全部完成后才可以开始.WorkflowSim工具包中设置了相关的组件来控制工作流的调度条件，如图3所示，是一个任务分配串的编码.

图3 分配串的编码方式

4 实验及分析

4.1 测试科学工作流模型

Montage是由NASA/IPAC红外科学馆创造了一个开源工具包，可用于生成自定义的天空镶嵌图案，用作输入图像在FITS中(Flexible Image Transport System)，如图4所示.Inspiral模型运行Pegasus于LIGO数据网格和开放科学网格，如图5所示.

CyberShake模型工作流是由南部加利福尼亚地震中心用来表征一个区域的地震危险性特征,这些工作流程来自2 011个包括了高频码生产运行，如图6所示.

图4 Montage模型图

图5 Inspiral模型图

图6 CyberShake模型图

4.2 参数设置

4.2.1 系统参数设置

实验中的任务参数的设置默认为WorkflowSim工具包下的工作流基本参数,而虚拟资源的数量为5个，每个资源的计算能力在400～1 200之间.

4.2.2 算法参数设置

实验中各智能算法的参数设置如表1所示.

4.3 实验结果分析

4.3.1 Montage工作流调度实验结果分析

表2、表3、表4记录了在Montage模型下任务量分别为25，50和100时各算法完成时间的Min、AVG和MAX值.

表1 智能算法参数设置表

表2 Montage_25工作流完成时间优化结果

从上面的表格可以看出，当任务数为25和50时，ABC和ACO的各类完成时间较短.如表3，ABC和ACO的平均完成时间较BA和GA提高40%.然而，当任务量增加时，如表4所示，ABO较所有算法平均完成时间最长，其完成时间明显增加，时间效率降低.反观CRO，在任务数为25和50时完成时间就比较短.在表4中任务数为100时，其平均完成时间更是达到最短，和其他算法相比，CRO在工作流完成时间上更高效.

表3 Montage_50工作流完成时间优化结果

表4 Montage_100工作流完成时间优化结果

4.3.2 Inspiral工作流调度实验结果及分析

在Inspiral模型下任务量分别为30，50和100时各算法的完成时间如表5、表6、表7所示.

表5 Inspiral_30工作流完成时间优化结果

从上面的表格可以看出，当任务量为30和50时，ABC,GA和SFLA三种算法的完成时间都相对较短.例如，在表5中，MA的平均完成时间只有PSO的0.6倍.但是，在任务量为100的情况下，ABC和GA的平均完成时间达到6 037.07和5 527.5，与除CS外的其他算法相比平均完成时间最长.可见，随着任务量的增加，各个算法的运行时间也会随着任务量的增加而增加.而对于CRO，在任务量为100时，平均完成时间最短，仅有CS平均完成时间的四分之三.

表6 Inspiral_50工作流完成时间优化结果

表7 Inspiral_100工作流完成时间优化结果

4.3.3 CyberShake工作流调度实验结果及分析

表2、表3、表4记录了在CyberShake模型下任务量分别为30，50和100时各算法完成时间的Min、AVG和MAX值.

表8 CyberShake_30工作流完成时间优化结果

表9 CyberShake_50工作流完成时间优化结果

表10 CyberShake_100工作流完成时间优化结果

从上面的表格可以看出,ABC和MA在任务量为30和50的时候，完成时间都相对较短.例如，在表8中，ABC和MA的最小完成时间和平均完成时间在所有算法中是最短的.在表9中ABC的平均时间性能更是比SFLA提高了25%.而在任务量变为100时，ABC和MA平均完成时间较除BA外其他算法最长，算法时间性能不再突出.只有CRO在各任务量情况下，其完成时间始终保持相对较短，时间性能稳定.

4.3.4 工作流调度的MinMakespan值结果及分析

表11对比了不同模型下各算法的MinMakespan值.

表11 任务数量100时工作流调度的MinMakespan值

从上面的表格可以看出,在不同的模型下，ABC和ACO的完成时间始终相对较长.如图11，在Inspiral模型下，ABC的MinMakespan值更是达到7 230.14.而SFLA、PSO和CS的在不同模型下的完成时间都比较不稳定，例如，SFLA在CyberShake 模型下的完成时间较所有算法除CRO外较短，而在Inspiral模型下，其完成时间达到了6 500以上.只有CRO，在三种工作流模型条件下，其完成时间较其他算法始终较短，时间性能更为良好和稳定.

5 结论

通过对以上九种算法在Montage,Inspiral和CyberShake三种不同工作流模型和不同任务量的情况下完成时间的实验数据可以看出：混合蛙跳算法、蚁群优化算法和粒子群算法的完成时间相对较小，但却在不同任务量和不同工作流模型下表现不稳定.只有化学反应算法无论是在不同的任务量条件下，还是在不同的工作流模型条件下，无论是极端的最值时间，还是平均时间，都相对较短.可以说，在完成时间上，对比其他算法，化学反应算法最为高效和稳定.