异构计算中基于遗传算法的服务流映射算法及性能优化

可在www.sciencedirect.com在线获取ScienceDirectFutureComputing and Informatics Journal 3（2018）341e347http://www.journals.elsevier.com/future-computing-and-informatics-journal/异构计算Ahmed A.AbdulHamed*，Medhat A.Tawfeek，Arabi E.凯什克埃及Menoufia大学计算机科学系接收日期：2018年4月1日;接受日期：2018年10月18日2018年10月30日在线提供摘要异构计算为许多应用需求提供了各种可伸缩的资源它的结构是基于互联机与几个处理能力分布在网络上。科学生物信息学和许多其他应用需要服务流处理，其中服务具有依赖性执行。这种计算环境适合于包含不同服务组的巨大计算需求。将服务流中的服务管理和映射到合适的候选服务提供者，属于NP完全问题。在异构环境中管理这种相互依赖的服务也需要考虑用户的服务质量提出了一种异构计算环境下具有服务成本质量需求的服务流管理模型。在此基础上，提出了一种基于遗传算法的服务流映射算法，以降低异构环境下应用程序的开销。该算法给出了一个强大的搜索技术，允许一个软成本的解决方案，从一个巨大的搜索空间的解决方案继承的进化概念。应用实验结果表明，遗传算法可以节省15%以上的成本，并且在加速比和SLR指标上优于比较算法。Copyright ©2018埃及未来大学计算机与信息技术学院由爱思唯尔公司制作和主持这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：异构计算;服务流;遗传算法;服务成本1. 介绍异构计算提出了完全多样化的计算节点，这些节点具有不同的能力和各种指令执行方式。获得各种计算节点的优点是性能提升和能量有效性[1]。多样性挑战存在于硬件层面和软件层面。这些挑战中最常见的两个是可扩展性和在各种候选者之间分配传入的工作负载以诱导高耸的性能[2]。异构计算可以是* 通讯作者。电子邮件地址：ahmed_abd1989@yahoo.com（A.A.AbdulHamed），medhattaw@yahoo.com （ M.A.Tawfeek ） 、 arabikeshk@yahoo.com（A.E.Keshk）。埃及未来大学计算机和信息技术系负责的同行审查考虑作为能够支持各种计算服务网络的服务支持模型。科学服务流通常需要不同的资源来管理大数据的计算活动。服务流管理系统用于通过隐藏异构服务容器提供的资源上的执行细节来管理这些应用[3]。为了限制服务流的价格，需要依靠元数据的有效策略来映射和管理服务[4]。本文提出了一种业务流管理模型。它包含四个独立的模块。从这些模块的管理模块被认为是大脑模块的建议模型。提出了一种基于预算QoS约束遗传算法（GA）是一种支持自然进化的元启发式技术。遗传算法结合了探索和开发的思想。探索从解域中发现新的解。剥削利用了最有效的https://doi.org/10.1016/j.fcij.2018.10.0042314-7288/Copyright © 2018埃及未来大学计算机与信息技术学院。Elsevier B. V.制作和托管这是CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。342A.A. AbdulHamed等人/Future Computing and Informatics Journal 3（2018）341e 347¼¼JSi：成本≤预算成本从以前的搜索解决方案解决方案由染色体表示[5]。根据当前的应用，染色体可以通过位串或符号表达式来描述寻找合适的染色体从初始染色体的群体开始当前的种群成员通过模拟生物进化的选择、变异和交叉操作来帮助产生新的种群[6]。采用适应度函数来衡量每一代染色体的质量遗传算法已被应用于各种优化，如机器人控制，并取得了巨大的成功[7]。本文其余部分安排如下。第2节介绍了提出的服务流管理模型和服务流映射问题。第三节介绍了最重要的相关工作，并对标准遗传算法进行了综述.第4节详细介绍了服务流管理的遗传算法在第5节中，通过各种实验讨论了所提出的遗传算法的性能。第六部分是对全文的总结和展望.2.异构服务流模型存储库。用户所需的服务由N个服务组成，服务流被建模为FS，FS由有向无环图（DAG）FS1/4（V，A）表示，其中V{S1，S2，弧A的集合表示服务之间的优先关系。图2呈现了包含七个服务的FSFS中的每个服务Si具有表示服务候选SC{C1，C2.Cm}的选择域，使得SC表示合适的服务候选的集合，服务流管理模块的主要目标是找到一个最佳的映射到FS，满足QoS和优化用户指定的目标。在本文中，我们的浓度仅基于成本约束。服务流FS.cost的成本不应超过SLM中用户指定的预算FS.成本是计算Eq。（一）.XNFS：cost¼J提出了异构服务流管理模型。该模型由四个模块组成：服务仓库模块、管理模块、代理模块和服务水平监控模块。1. 服务存储库包含各种异构服务。2. 管理模块维护一个管理算法，根据用户的QoS需求生成最佳映射3. 代理模块从存储库中收集QoS需求和所需服务的所有合适的候选者，并将这些信息转换到管理模块。4. SLM模块负责对服务的执行过程进行监控，并将监控结果反馈给代理模块。提出的异构环境下的服务流管理模型如图所示。1.一、用户提交一个单独的服务或服务流与QoS需求规范的基础SLM的代理模块。Broker模块从存储库中复制分离服务或服务流所需的服务，然后将分离服务或服务流以及合适的服务候选列表发送给管理模块。Broker模块还根据用户与服务器之间的SLM协议为用户协商和配置服务。管理模块根据当前场景生成最佳映射。之后，它根据到达映射将服务传输到合适的候选者，并确认代理。SLM模块监控和跟踪执行，并将跟踪结果反馈给代理模块。本文中的服务被建模为S，Scost代表服务成本。SN是Service其中Si是映射到候选Cj的服务Si。这是从Eq。（1）对于成本优化，管理算法的目标是找到满足成本约束或最小化FS.cost值的映射。3. 相关工作和标准遗传算法（SGA）概述3.1. 相关工作对于任务调度和工作流调度方面的异构计算调度的研究很多，而对于服务流管理方面的研究较少。这一小节介绍了异构计算中最流行的调度相关工作.参考文献[3]中的MineMin和参考文献[8]中的Max-Min用于满足QoS的各种约束，例如时间和/或成本。研究工作在参考文献。 文[4，9]利用马尔可夫决策的分支模型，依靠成本目标的迭代方法，解决了多任务分段调度问题。基于遗传算法的优化技术也被用来解决网格调度问题. [7，10，11]。 这些方法虽然在网格环境下有效，但不能直接应用于解决异构计算环境下的调度问题。文献[12]提出了基于工作流的粒子群优化算法（PSO），该算法以降低应用程序执行成本为目标。参考文献[13]中的蚁群算法用于解决网格计算中具有不同QoS需求的工作流。文献[14]的研究工作提出了一种多QoS约束的云计算多工作流调度策略来解决工作流调度问题。参考文献[15]中的ACO，GA和PSO用于解决云工作流管理。结果表明，蚁群算法的性能优于粒子群算法和遗传算法。文献[2]提出了一种新的工作流管理算法--贪婪蚂蚁算法，●●●●1/1●A.A. AbdulHamed等人/Future Computing and Informatics Journal 3（2018）341e 347343图二.服务流程示例流程图。Fig. 1.提出的服务流程模型。4. 服务流的遗传算法服务流管理的重点是映射和管理依赖于不同候选者的服务的执行。为了利用遗传算法的概念来解决服务流映射问题，需要确定种群中的染色体表示、适应度函数和遗传操作。详情见以下小节。4.1. 染色体表示最小化应用程序在异构环境中的总执行时间。3.2. 标准遗传算法（SGA）概述SGA是一种基于生物进化的高效搜索方法。SGA通过迭代重组和突变当前最佳染色体的部分来产生后继染色体。该算法通过重复更新染色体池（称为种群）来运行。每个种群中的所有染色体在每次迭代时都由给定的适应度函数进行排序。适应度值显示了染色体与群体中其他染色体相比的质量[16]。然后通过从现有群体中选择特定的染色体来制造新一代。这些选择的染色体中的一些被复制到下一代群体中，而其他染色体用于交叉和突变操作以创建新的后代染色体[5]。SGA的流程图如图所示。 3.典型的SGA包括以下步骤[5][6]：1. 随机创建染色体的初始种群2. 估计当前种群中各染色体的适应度值，并保存最佳值。3. 通过应用遗传算子（选择、交叉和变异）生成新的后代。4. 重复步骤2和3，直到算法终止。种群中的每个染色体代表问题的一个可行解，并且由用于服务分配的合适候选者的向量组成。图4示出了染色体图示。从图4中可以看出，每个服务都有一组候选项，染色体被表示为所选候选项的向量。向量长度等于N，表示FS中的服务数量，如图2底部所示。 四、4.2. 适应度函数与选择适应度函数用于测量当前世代中每个染色体的质量。由于遗传算法的目标是使FS执行的总代价在计算每个染色体的适应度之后，应用选择操作所提出的遗传算法依赖于轮盘赌轮选择方法，其工作原理如下。染色体被包装成连续片段的圆，使得每个片段与染色体适应度成比例。生成随机数，并选择其片段跨越所生成的数的染色体重复该过程，直到选择特定数目的染色体4.3. 遗传算子遗传操作包括现有种群中的染色体并产生新的染色体。两个基因算子：S1S3S5S7S2S4S6344A.A. AbdulHamed等人/Future Computing and Informatics Journal 3（2018）341e 347…一套服务一套服务二套服务服务序列号集候选人C2C4…CWC5颈7…振英C1C3…Cx图三.标准遗传算法（SGA）流程图。见图4。染色体表现。对FS映射问题进行了交叉和变异操作。杂交用于通过组合所选染色体的特定部分从当前世代产生新染色体。交叉的主要目标是产生高质量的染色体。所提出的基于遗传算法利用基于顺序的交叉方法的工作原理如下。从一条染色体（亲本1）中随机选择几个基因，然后将这些基因的顺序强加给另一条染色体（亲本2）中的相应基因。举例来说染色体（亲本1）：75 0 36 1 4 2为简单起见，从染色体表示中删除了字母C粗体的基因是随机选择的现在，顺序5，0，然后6应用于Parent2中的相同基因，以给出后代染色体如下：染色体（亲本2）：4 3 6 7 2 5 1 01：4 3 5 7 2 0 1 6在这两个父母之间应用相同的步骤，反过来得到第二个后代。在所提出的遗传算法中，变异被用来探索一个新的解决方案。它允许特定的后代获得父母没有的新特征。该遗传算法采用插入变异方法。这是一种非常有效的突变方法，操作如下。只有一个基因（即3）被选择被置换并插入到相同的染色体中，如下所示：1 2 3 4 5 6 0 7从序列中去掉3，1 2 4 5 6 0 7然后在随机选择的位置重新插入3：1 2 4 5 3 60 7所提出的用于服务流管理过程的遗传的伪代码在图1中示出。 五、5. 实施和实验结果为了测试服务流的拟议GA，我们在参考文献[17]中构建了基于CloudSim模拟器的模拟器。PC的配置是双核与4GB RAM与Windows 7操作系统.建议的遗传算法是在我们的模拟器上开发的JAVA。我们还实现了一个时间优化算法，异构最早完成时间（HEFT）[2]和贪婪成本（GC）[7]。HEFT算法是一种列表映射算法，它试图在异构环境中以最小的执行时间分配相互依赖的任务。但在本文中，它用于映射相互依赖的服务，而不是任务。GC方法是通过将任务分配给成本最低的资源来最小化工作流执行成本。此外，它在这里是为FS而不是工作流实现的。的度量进行比较。● 总成本● 调度长度比（SLR），● 加速比A.A. AbdulHamed等人/Future Computing and Informatics Journal 3（2018）341e 347345投入：FS和候选人名单输出：候选项上FS的最佳映射步骤：1-第二部分：阈值：确定停止标准。p：群体大小表示染色体数目。r：被Crossover取代的人口百分比m：突变率。p=随机生成p个染色体评估：对于P中的每个染色体ch，计算Fitness（ch）。将最大健身量保存在Bsolution中。2-迭代部分：B解阈值（Bsolution Threshold）做创建一个新的人口pn：1. 从P中选择（1-r）.p成员并使用轮盘将其插入Ps2. 杂交：从p中选择（r/2）.p对染色体。对于每一对（chl，ch2）应用基于顺序的交叉以生成两个后代。3. 将所有后代加到p n。4. 突变：选择p n的百分之m的染色体。 然后对它们进行插入变异。5. 求值：对于Pn中的每个染色体ch，计算Fitness（ch）。6. 将最大健身量保存在Bsolution中。7. 更新：pn和p3- 完成部分：把溶液退回去。图五、提出了基于遗传伪码的业务流管理接下来的实验包括不同的服务流（FS），其包括从10到100个服务的服务。如参考文献[7]所述，服务流被分类为平衡结构或非平衡结构。本文只处理平衡结构。表1示出了所提出的遗传算法（GA）的所选择的最佳参数，其通过实验确定用于服务流管理。建议的遗传算法的人口规模p被设置为20，交叉率为0.8，变异率为0.1，并选择成本最小化作为目标函数的建议的遗传算法，所以它是运行与一个固定的迭代次数被设置为100作为停止标准。我们假设，对于每个候选人是已知的，在本文中，它由一个随机值分配。所提出的GA、HEFT和GC算法的总成本如图6所示。所提出的遗传算法消耗更少的成本比HEFT和GC算法。表1建议GA选择参数。参数选定值p 20第8条规则m. 1迭代100346A.A. AbdulHamed等人/Future Computing and Informatics Journal 3（2018）341e 347¼加速比vi2V完工时间调度长度比（SLR）：它是基于完工时间的调度算法的关键度量。调度长度比（SLR）由等式2定义（2）在Ref。[1]的文件。完工时间SLR¼Pvi2CPminminmt2MfWi;tgð2Þ除数是FS上服务最小计算的总和。SLR值越低，映射算法的性能越好。所提出的GA、HEFT和GC算法的SLR如图所示。第七章所提出的遗传算法具有更少的SLR比HEFT和GC算法，表明所提出的遗传算法的更好的性能。加速比：加速比值定义为顺序执行时间与并行执行时间之比，可以通过公式计算（3）在Ref。[7]的文件。图八、所提出的GA、HEFT和GC算法的平均加速比6. 结论和今后的工作提出了一种异构服务流模型，最小海拔2米。PWi;t该模型包含四个模块，如服务再分配，ð3Þ存管模块、管理模块、经纪人模块和SLA监控模块。在那之后，遗传算法其中，分子表示通过将所有服务分配给单个候选服务来计算的顺序执行时间，这里的并行执行时间由完工时间表示所提出的GA、HEFT和GC算法的加速比如图8所示。与HEFT和GC算法相比，该算法具有更高的加速比，表明了该算法的有效性。图第六章提出的GA，HEFT和GC算法的总成本图第七章所提出的GA、HEFT和GC算法的平均SLR提出了业务流管理。它有助于在异构环境中基于服务成本和质量要求的服务流执行和管理。它的主要目标是通过考虑用户指定的预算使服务流的总费用最小化。为了测试建议的遗传性能，我们的模拟器为基础的CloudSim模拟器开发。实验包括不同的服务流，包括10到100个服务。其中有些是均衡的服务流，有些是不均衡的。通过实验确定了遗传算法的参数选择值。结果表明，该算法在总费用、调度长度比和加速比方面优于HEFT和GC算法。响应时间、安全约束和不平衡结构等问题可在今后的工作中加以处理。引用[1] Topcuoglu H，Hariri S，Wu M.面向异构计算的低复杂度高性能任务调度。IEEE跨并行分布式系统2002;13（3）：260e 74.[2] 向 斌 ， 张 碧 波 ， 张 琳 。 Greedy-ant ： Ant colony system-inspiredworkflow scheduling for heterogeneous computing ， vol. 5;2017. p.11404年第12期。[3] Tracy DB，Howard JS，Noah B.将一类独立任务映射到异构分布式计算系统的十一种静态算法的比较。并行分布式计算杂志2001;61（6）：810e 37.[4] YuJ，Buyya R，Tham CK. 公用事业网格上科学工作流应用的基于成本的调度。第一届IEEE电子科学和网格计算国际会议，澳大利亚墨尔本;2005年12月。p. 140E 7。[5] 吴安，余华，靳S，林开成，斯齐亚沃尼G.多处理机调度的增量遗传算法。IEEE跨并行分布式系统2004年9月;15（9）：824e 34.[6] ZomayaAY，Teh YH. 关于使用遗传算法进行动态负载平衡的观察。IEEE跨并行分布式系统2001年9月;12（9）：899e 911.[7] YuJ，Buyya R. 用遗传算法调度有期限和预算约束的科学工作流应用。科学计划J，IOS出版社2006;14：217e 30。8007006005004003002001000分量GC建议GA102030405060708090100FS中的服务数量765分量43GC2建议GA110 20 30 40 50 60 70 80 90 100SF中的服务数量2.32.1分量1.9GC1.71.5建议GA1.31.10.9电话：+86-21 - 8888888传真：+86-21 - 88888888SF中的服务数量总成本单反加速比A.A. AbdulHamed等人/Future Computing and Informatics Journal 3（2018）341e 347347[8] Yu J，Buyya R.网格计算中的工作流调度算法。分布式计算环境中调度的元算法。ISBN：978-3-540-69260-7。Berlin，Germany：Springer;2008.[9] Sakellariou R，Zhao H，Tsiakkouri E，Dikaiakos MD.具有预算约束的调度工作流。CoreGRID网格计算综合研究讲习班。技术报告TR-05-22。意大利：比萨大学; 2005年。第347和57页。 十一月[10] KimS，Weissman JB. 一种基于遗传算法的可分解数据网格应用调度方法。MD：ICPP.IEEE计算机协会：银泉; 2004年。p. 406年第13期。[11] 叶G，饶R，李明. 网格环境下基于遗传算法的多目标资源调度方法。第五届网格与协作研讨会国际会议，湖南，中国; 2006年。 p.504E 9.[12] 潘迪·苏拉吉，吴琳琳，古鲁·西德斯瓦拉，布亚·拉杰库马尔。Aparticleswarm optimization （ PSO ） -based heuristic for schedulingworkflowapplications in cloud computing environments”，技术报告，CLOUDS- TR-2009-11，云计算和分布式系统实验室。澳大利亚墨尔本大学; 2009年10月。[13] Talukde Khaled Kirley Michael Buyya Rajkumar“全局网格上调度工作流应用的多目标差分进化”，并发性和计算：实践和经验，第21卷。NewYork，USA：Wiley Press. 卷13，pp：1742e 1756.[14] 徐梦，崔丽珍，王海洋，毕雁冰。一种多QoS约束的云计算多工作流 调 度 策 略 。 IEEE International Symposium on Parallel andDistributedProcessing with Applications，2009。p. 629年第34期。[15] 吴 章 俊 、 刘 晓 、 倪 志 伟 、 袁 栋 、 杨 云 。 “A market-orientedhierarchical scheduling strategy in cloud workflow systems”，Journal ofsupercomputing ， special issue on advances inNet-work&Parallelcomptg，to be appeared. 2010年。[16] Mandal A，Kennedy K，Koelbel C，Marin G，Mellor-Crummey J，Liu B等，将应用程序工作流映射到网格上的调度策略。在：IEEE高性能分布式计算国际研讨会（HPDC 2005）; 2005年。[17] 放大图片创作者：Kristan T，Kristan T.“Approaches to improve theresourcemanagement in the simulator CloudSim”in ICICA 2010 ，LNCS6377. 2010. p. 189E 96.