英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料
云计算中基于神经网络的动态工作流调度的多目标进化算法
【摘要】
工作流调度是云计算中一个研究较多的课题，其目标是通过考虑QoS中指定的目标来利用云资源完成工作流任务。本文将动态工作流调度问题建模为动态多目标优化问题(DMOP)，其中动态的来源是基于资源失效和目标数量随时间的变化。软件故障和/或硬件故障可能导致第一种类型的动态性。另一方面，在执行工作流的过程中，面对云计算中的真实场景可能会改变目标的数量。在本研究中，我们将人工神经网络与NSGA-II算法相结合，提出一种基于预测的动态多目标进化算法，即NN-DNSGA-II算法。针对动态工作流调度问题，提出了五种主要的基于非预测的动态调度算法。以最大完工时间最小化、成本最小化、能量最小化和不平衡度最小化为目标，给出调度问题的求解方法;以及可靠性和利用率的最大化。基于Pegasus工作流管理系统的实际应用的实证研究表明，在大多数情况下，我们的NN-DNSGA-II算法在用于具有未知的真正帕尔托最优前沿的DMOPs的度量(包括非支配解决方案的数量、Schott间距和超容量指示器)方面显著优于其他备选方案。
- 介绍
云计算是一种面向科学和商业社区的大规模异构和分布式计算基础设施，它以最少的硬件投资提供高质量和低成本的服务。基础设施即服务(IaaS)、平台即服务(PaaS)和软件即服务(SaaS)是云计算通过internet交付的最流行的服务层。在本文中，我们将主要讨论IaaS，客户可以在IaaS上访问硬件资源，可以在IaaS上部署应用程序。
工作流是在不同研究领域构建大规模计算和数据密集型应用的常用技术。应用程序工作流使用有向无环图建模，其中图的节点是通过计算资源或数据资源互连的任务。云计算中的工作流调度问题旨在将给定应用程序的任务映射到可用资源上[1-4]。这是一个np完全问题[1]，为了优化QoS中指定的目标，任务执行的编排是主要关注点。
周期性工作流调度主要涉及定期提交给系统的应用程序，这些应用程序在不同的领域中越来越多地遇到。他们出现在物理的引力波每年[5]，商业的财政分析每月和气象的天气预报和风暴潮预测每日或每小时[6]。应用程序中任务的工作负载可能在每个时间段内根据它们收集的数据量而变化。这些不可预测的波动导致了基于周期的调度，其中任务应该根据每个时间段的最新工作负载重新调度。
我们在本研究中所考虑的工作流调度中的动态概念是双重的。第一种动态类型是随时间变化的瞬时资源故障，在这种情况下，资源可以动态地连接到云，也可以动态地离开云。它们可能由一些事件引起，如软件故障(bug、溢出等)或硬件故障(不正常的电力、硬盘故障等)。工作流调度问题中动态的另一个来源是在工作流执行过程中改变目标的数量。云计算面临着真实的场景，其中目标的数量可能会随着[7]的变化而变化。例如，在一个工作流程的最大完工时间没有被考虑，直到一个工作流程的最后期限被提交执行。也强调了云的重要性
计算是一个开放的主题，可以考虑更多变化的目标。目标可以被几个外部因素忽略或考虑，包括功耗水平、资源间工作负载的不平衡水平或QoS要求的变化。这种动态性对不同时期的最优工作流调度解决方案的选择产生了影响。
据我们所知，我们的论文是第一批尝试将云计算中的工作流调度问题建模为动态多目标优化问题(DMOP)的论文之一，将资源失效和目标数量的变化视为动态的主要来源。本文提出了一种新的基于预测的动态多目标进化算法，即NN-DNSGA-II算法，该算法将人工神经网络与非优势排序遗传算法(NSGA-II算法)相结合。NN-DNSGA-II算法将神经网络的强度与动态NSGA-II相结合，揭示了优化环境中的变化规律。它利用任务-资源对之间的相关性和两个连续优化环境之间的相关性来估计最优解的未来位置。
另外，我们从文献中引用了五种不需要预测的动态多目标算法，包括DNSGA-II-A、DNSGA-II-B、DNSGA-II-HM、DNSGA-II-RI算法和DMOPSO算法的动态变化。它们包含在不可预测的场景中的更改类型中，在这些场景中，它们具有不同类型的响应机制来应对更改。DNSGA-II-A、DNSGA-II-RI和DMOPSO基本上是插入随机解以使种群重新多样化，而DNSGA-II-B则插入种群中现有解的突变版本。最后，DNSGA-II-HM利用环境中突变率的适应性。
通过大量的实证研究，证明了该算法的性能，其中优化目标包括极小化最大完工时间、成本、能量和不平衡;以及可靠性和利用率的最大化。资源规范基于Amazon EC2;Pegasus工作流管理系统的工作流程是测试平台。对多目标优化问题的非支配解的个数、肖特间距和超体积三个指标进行了比较。通过实验验证，我们的NN-DNSGA-II算法在不同的变化频率下，在30例中有24例优于自适应算法，在不同的变化严重程度下，在45例中有35例优于自适应算法。
论文的其余部分组织如下。第二部分是对相关工作的回顾。在第3节中，我们介绍了工作流应用模型、工作流执行的体系结构和本研究考虑的目标。第4节提出了动态工作流调度问题，然后提出了NN-DNSGA-II算法，并对文献中五种动态多目标算法进行了修改。第5节介绍了实验设置和本研究考虑的度量的定义。实证研究的结果和讨论见第6节;第七部分是本文的结论。
- 相关工作
分布式资源的工作流调度是一个被广泛研究的np完全问题。虽然存在少数单目标工作流调度问题[8,9]，但现有的研究大多具有多目标特征[1,10,11]。虽然它们中的一些线性组合多个目标[12,13]，它可能不适合的性质在某些条件下的现实问题。一个限制是使用正确的值设置权重参数。此外，目标的线性组合可能无法收敛于位于帕累托最优前沿凹部的最优解。对于云计算中的工作流调度问题，文献中最常见的目标包括完工时间、成本、可靠性、能量和利用率。
动态工作流调度是指一种具有基本概念差异的特殊调度技术。对于一类动态工作流调度问题，资源的价格会随着市场的供求关系而变化。另一方面，对于某些问题，工作流的信息，包括它们的到达、大小和特性，是事先未知的;调度决策是在运行时做出的[14-16]。在本研究中，我们将动态工作流程排程问题的定义加以扩展，藉由考虑资源的失效与基于工作流程执行需求变更的QoS目标数目的变更。
尽管已有文献对云计算进行了建模并提高其可靠性，但资源故障仍然具有挑战性。为了了解故障的特征，Iosup等人基于长期跟踪评估大型系统中的资源可用性数据，并为故障的频率、持续时间和大小提供足够的统计背景。为了应对这些故障，容错调度主要被认为是一种有效的技术，在很大程度上避免了云计算中金钱、时间和精力的浪费。Zhu等人尝试将扩展的主备份调度技术应用到云计算的实时调度中，以容忍工作流执行过程中的错误。另一方面，Plankensteiner等人的[19]使用任务重新提交技术，提出了重新提交对可靠的工作流执行的影响，同时在云中满足他们的最后期限。
多目标优化中目标数量的动态变化在文献中很少被考虑。首先，Chen等人强调了改变云的目标数量的重要性，因为不同的调度场景可能会出现在云[7]中，目标的种类更多。分析了它对问题的帕累托最优前沿的潜在影响以及算法的性能。Chen et al.[20]和Zille et al.[21]分别尝试将其应用于距离最小化和调度问题。然而，由于没有研究涉及两个以上目标的场景，云计算方面的现有工作仍然有限。另外，本文动态改变目标的主要动机是在环境中寻找可行的解决方案，在此环境中之前没有可行的解决方案。然而，在找到至少一个可行的解决方案后，它就不再考虑改变目标了。
云计算一般是一个随机环境，可能会有几种类型的延迟和不确定性。主要的延迟包括虚拟机(VMs)的配置延迟和取消配置延迟，而主要的不确定性包括任务运行时、资源和网络性能的变化，文献[22 - 24]中有几篇论文解决了这些问题。然而，如果在调度过程中充分考虑了延迟和不确定性，则可能会对基本解决方案的效率产生负面影响。这可能会导致解决方案的预期结果和实际结果之间的差异
文献中现有的动态多目标进化技术根据其处理动态的方式可以分为几个类别。其中一个主要类别是基于预测的模型，随着机器学习技术的日益普及，这些模型受到了特别多的关注[25-30]。的prediction-based该领域的模型可用于预测环境变化的时间或跟踪随时间变化的移动最优解。Liu等人利用神经网络预测最优解的变化方向，在单目标优化问题的动态环境中跟踪最优解的变化方向，从以前的环境中提取有用的知识，对未来的环境进行预测。另一方面，Jiang等人([30])将支持向量机(SVM)应用于NSGA-II算法来解决动态多目标优化问题，其中过去的Pareto最优前沿的解被标记为正，其余的解被标记为反例。
本研究的主要区别在于，我们将资源失效和目标数量变化这两种动态模型结合起来，对云计算中的动态工作流调度问题进行建模。此外，我们还提出了一种新的基于预测的动态多目标进化算法，NN-DNSGA-II。此外，我们采用现有的动态多目标算法从文献。他们优化了六个不同的目标，包括极小化最大完工时间、成本、能量和不平衡;以及可靠性和利用率的最大化。算法在调度工作流时也考虑了延迟和不确定性。
3.云计算中的工作流调度问题
3.1。应用程序模型
工作流应用程序G= (T, D)是通过有向无环图建模的，其中有向无环图= (T, T，hellip;) 12，t)为任务集，D = (dij | ti, tjisin;t)为前向约束任务的边集。n任务的权重由其引用执行时间(以秒为单位)定义，边缘的权重由其输出数据大小(以字节为单位)定义。对于任务t, pred(t)是其直接前辈的集合，succ(t)是其直接后继者的集合。iii没有前任的任务为tand没有后续的任务为t。一个任务只能调度到一个云资源。entry exit 但是，通过一次最多处理一个任务，每个资源可以执行多个任务。任务一旦启动，就不能被任何其他事件打断。
周期性工作流是任务周期性到达系统的特定类型的应用程序，是本文研究的工作流。参考执行时间和通信数据大小可能会根据每个周期阶段收集的信息量在一定程度上自然地波动。它们遵循高斯分布，就像现实世界中的大多数情况一样。这种变化导致了基于周期的工作流调度概念，其中任务需要根据最新的工作负载在每个单独的时间段重新调度。表1列出了论文中使用的所有关键符号。
表1符号。
|
象征 |
定义 |
|
RT (t)i 圣(t, r)ik PT (t, r)ik TT (t, t)ij 英国《金融时报》(t, r)ik |
任务t的参考时间i 资源中任务的开始时间ri k 任务对资源的处理时间ri k 任务t和任务t的传输时间i j 资源任务的完成时间ri k |
|
铜k |
资源r的计算单位k |
|
Ck |
资源成本rk |
|
Nk |
ris规定的计费周期数k |
|
B |
系统带宽 |
|
戴斯。莱纳姆: |
延迟 |
|
迪 |
不平衡度 |
|
R |
可靠性 |
|
E tau; |
能源消耗 计费周期 |
3.2。系统模型
设R= (R, R，hellip;)12， r)表示一组异构计算资源。mIaaS平台提供了一系列具有不同资源属性组合的类型，如价格和计算单元(CU)，这是一个相对性能指标。这些资源是完全相互连接的，并且一次只能包含一个虚拟机(VM)。在这方面，任务吨资源ris的处理时间计算如下:i k
(1)
两个任务之间的传输时间取决于带宽，而整个系统的带宽是相同的;模型中忽略了资源间的传输。两个相关任务之间的传输时间tand tover a链路与带宽B之间的传输时间计算如下:i j
(2)
在我们的研究
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[238345]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
