有效的资源配置实时工作流在云

文摘

在大数据时代,采矿和分析大量的数据被广泛的用于支持决策。这个复杂的过程包括大量数据采集、存储、传输和分析可以建模为工作流。与此同时,云环境提供足够的计算和存储资源的大数据管理和分析。由于云提供现收现付制的定价方案,执行工作流在云应提供资源。因此,有效的资源配置工作流的云仍然是一个关键的挑战。同时,复杂的数据管理过程的反应通常需要实时。因此,期限是工作流执行的最重要的约束。为了解决的挑战,有效的资源配置,同时满足工作流执行的实时要求,提出了一种基于动态规划的资源配置策略,实现成本效益云工作流执行的工作流和基于关键路径的分区算法保证工作流可以在最后期限之前完成。评估我们的方法通过仿真实验实时工作流不同大小和不同的结构。结果表明,我们的算法优于现有的经典算法。

1。介绍

如今,大数据技术被用于广泛的应用程序包括复杂系统支持决策(1,2]。随着巨大的商业利益,科学的进步,管理效率、精度和分析大数据所带来的,这种新技术提出了许多具有挑战性的问题,如高成本和延迟的大数据存储、传输、加工(3- - - - - -5]。解决这些问题,云计算环境和工作流建模方法被认为是有效的方法。

许多大规模的科学应用领域,如天文学、生物信息学、和气象会生成和处理大量的数据;这样的应用程序包含大量的数据处理任务,经常被建模为工作流(6]。通常,工作流是由一个有向无环图(DAG)表示节点和边,边缘节点代表任务和表示数据/控制任务在一个复杂的应用系统之间的依赖关系。与此同时,一次时间关键型或实时应用系统(7,8)被建模为一个实时工作流,最后期限的约束可以有效地用于确保任务按时完成。

云计算正在调查是一种有效的平台,提供了硬件基础设施和软件应用程序作为服务任务的大数据管理和分析。和实时工作流可以在这样高性能计算环境中执行。有各种各样的云提供商提供大量的服务具有不同的服务质量(QoS) (9- - - - - -11),以及不同的价格。都作了很多的努力在该地区的服务推荐(12,13)基于QoS的服务提供商(14- - - - - -16),但很少有人关注都集中在如何选择基于QoS的服务云平台从用户的角度来看。特别是,云计算提供了一个灵活的定价模型(即。现收现付制和按需服务);用户指控基于他们各种资源的消耗不同的QoS。因此,最具挑战性的问题之一在云计算与实时工作流是得到一个具有成本效益的方式在规定期限内完成工作流(17]。

在现实中,有两个主要阶段当执行工作流在云计算环境中18]。第一个是资源配置阶段:在此阶段,从云计算资源将选择和保留为工作流的执行做准备。第二个是任务调度阶段:在此阶段,生成一个时间表和每个任务将映射到最适合的资源。第二阶段,决定何时何地工作流将执行每一项任务,而第一阶段决定什么类型和多少资源将从云服务提供商,因此租赁工作流的总成本主要是决定在这个阶段。为了解决这些区分任务调度和资源配置,我们在本文中提出一个新颖的成本只关注资源配置的优化算法。

为了满足实时工作流的最后期限,我们的建议分区原来的工作流到一些sub-workflows可以并行执行基于关键路径方法。然后我们使用动态编程背包算法提供资源云为这些sub-workflows总成本降到最低。评估我们的方法通过仿真实验实时工作流不同大小和不同的结构。结果表明,我们的算法优于现有的经典算法。本文的主要贡献表示如下:(我)全球资源配置实时工作流策略是解决deadline-constrained下成本优化。(2)工作流的分区算法提出了基于关键路径法得到一些sub-workflows被并行执行,以确保最后期限的约束。(3)动态编程算法用于sub-workflows提供最具成本效益的资源。(iv)我们执行广泛的模拟和展示我们的策略的效果在两个现有的算法,即只是DPK和IC-PCP。

剩下的纸是组织如下。部分2介绍相关工作问题规范部分紧随其后3。部分4该算法在部分解释道5介绍了评价算法的性能。最后,结论和未来的工作进行了总结6。

2。相关工作

成本优化工作流执行已被广泛研究。高效的资源利用并行和分布式计算环境成本效益的关键问题。为了解决这个问题,许多研究已经通过各种各样的云工作流调度方法。因此,大量的实时工作流调度算法关注减少整体实时提出了工作流的执行成本。Alkhanak et al。19)分类工作流在云计算环境下的成本优化方法分为两类:启发式方法和meta-heuristic方法。

Abrishami et al。17)提出了一个静态算法IC-PCP (IaaS Clouds-Partial关键路径)基于启发式的调度一个工作流实例在一个IaaS云。该算法考虑云的特性,比如VM异质性,现收现付制,时间间隔定价。他们试图最小化调度所有任务的执行成本部分关键路径在一个机器,可以完成这项任务之前他们最新完成时间(这是基于应用程序的最后期限和最快的计算可用实例)。在[20.Verma),和Kaushal提出了一种基于贪婪算法的经典分量提供一个合适的执行成本和时间之间的权衡。郑et al。21)提出了三个小说调度启发式算法来帮助用户安排他们的大数据处理工作流应用程序在云端,这样可以最小化成本和最后期限的约束可以满足;不同配置的CPU频率被认为是他们的工作。Meta-heuristic方法如基于遗传算法(GA) (22],基于蚁群优化(ACO) [23],基于粒子群优化(PSO) [24],共生有机体搜索算法是用来解决同一目标最小化工作流执行的成本,同时考虑到期限。吴et al。25)提出了一个算法meta-heuristic L-ACO以及一个简单的启发式proli带头工作流的执行成本降到最低期限约束下云;实验结果表明,该meta-heuristic L-ACO性能更好的执行成本和成功会议的最后期限,但启发式proli带头的比率更为高效。也就是说,meta-heuristic算法实现了改进的性能基于成本优化,但在执行时间上妥协。

任务调度将任务分配给最有效率的资源优化工作流的执行成本。但任务调度是一个著名的np难问题。没有调度算法,可以在多项式时间内获得一个最优解17]。否则,应对deadline-constrained工作流调度,deadline-distribution方法是应用最广泛的方法,基于meta-heuristic和启发式算法。deadline-distribution方法总是分配每个任务的最后期限比例最小执行时间(25]。在大多数情况下,这种方法忽略了任务可以并行执行的工作流,所以每一个任务的sub-deadline可能不合适。根据这些sub-deadlines,任务调度算法不能得到全局最优的结果,因为一个任务级别的优化使用,因此未能利用整个工作流的结构和特点。资源配置可以最低的成本,通过选择最优的装配资源的全局工作流执行。我们的建议的总成本最小化工作流执行从资源配置的角度对整个工作流程(或sub-workflows)没有关于每一个任务的资源映射,可以进一步提高资源利用率。

对成本优化、资源配置更有效率和有效的比为一个实时任务调度工作流在云计算环境中26]。许多研究已经完成的总体成本最小化的工作流资源配置(27,28]。静态和动态方法用于提供云资源(29日]。静态方法假设准确信息工作流和云资源调度之前可以获得性能。动态配置采用没有这样的假设。大多数科学家运行相同的工作流,从而使通过几种试验收集这样的信息。因此工作流(静态方法是一个适当的方法30.]。静态调度也减轻了,云提供商通常宣布他们的资源的性能规格。我们在本文中使用静态资源配置方法。

3所示。规范问题

为了方便阅读论文的,列出了所有在这一节中使用的符号表1。

3.1。相关的模型

3.1.1。工作流模型

实时工作流是指使用工作流建模技术的实时应用系统。即时态约束添加到原始使用DAG图的工作流模型。

定义1。工作流应用程序是由一个有向无环图(DAG)表示= (T,W,E), 是一组n的任务, 每个任务的计算工作负载在吗T, 是两个任务之间定向边的集合。一条边e_ij的形式(t_我,t_j)表示,数据之间的依赖关系t_我和t_j;t_我据说是父任务的t_j和t_j据说是孩子的任务吗t_我。这之间的关系t_我和可以表示为t_我=父(t_j),t_j=孩子(t_我)。的计算工作量是由mega-floating点的数量需要执行的操作。实时工作流的时间约束是用的最后期限D。基于这个定义,子任务无法执行,直到所有的父任务完成。图1显示了一个示例工作流与六个任务。t_条目和t_退出额外的虚拟节点和计算工作量0给整个工作流程的一个入口和一个出口。这个任务t₁之前必须完成的任务t₃和t₄可以开始了。同时,这两个t₃和t₄之前必须完成t₅可以开始了。然而,之间没有路径t₃和t₄。所以t₃和t₄不需要执行任何特定的顺序。因此,任务{t₁,t₃,t₄,t₅}可以作为执行t₁⟶t₃(t₄)⟶t₅。这意味着工作流t₁,t₃,t₅或t₁,t₄,t₅必须按顺序执行,但t₃,t₄可以并行执行。有两种典型类型的工作流过程在一个大型实时工作流如图2。一个是连续的工作流过程图2(一个)在所有的任务都必须按照一定的顺序一个接一个地执行。另一种是并行工作流过程图2 (b)可以同时执行的所有任务没有任何特定的顺序。

3.1.2。资源模型

本文在基础设施即服务(IaaS)云提供用户一个虚拟机(VM)的无限和异构资源池有不同的计算性能,内存容量,价格可以按需访问如Amazon的EC2 (Elastic Compute Cloud) [31日]。更好的计算性能或更多的内存意味着更高的价格。我们假设没有限制使用每个资源;也就是说,the workflow can order any number of resources from each cloud provider at any time. Based on the profiling results about workflows given in [1)和Amazon EC2提供的虚拟机类型,我们假设虚拟机有足够的内存来执行工作流任务。因此,内存容量的vm将不再被认为是。我们定义作为虚拟机类型的计算性能P_j和价格_j每账单周期τ时间单位。

为每一个某种类型的,我们假设的计算性能mega-floating点操作每秒(MFLOPS)可以从提供者或可以估计32]。此信息用于推导出计算性能P_j= MFLOPS_j∗τ,在那里τ表示的计费周期这是由云提供商指定的。每个用户的支付的使用基于账单周期τ。租赁的任何部分使用VM带电好像完整的计费周期消耗。例如,如果τ= 60秒和一个VM用于61秒,然后用户将支付两个60秒的周期,也就是120秒。也,我们假设没有限制的数量计费周期的vm可以租赁提供商。

定义2。假设有米类型的虚拟机可以由云提供商提供的;收集可用的vm将表示 。每个VM_j两个参数;一个是MFLOPS_j,另一个是价格_j。MFLOPS_j被定义为每秒mega-floating点操作的虚拟机吗_j,和价格_j价格是每τ秒的VM_j,在那里τVM的账单周期吗_j。P_j= MFLOPS_j×τVM的计算性能吗_j每个计费周期。

3.1.3。成本模型

通常情况下,最终成本不仅是基于计算资源的利用率,而且还在父任务及其子任务之间的数据传输。如果父和子任务都是在同一个VM,没有数据传输费用,因为任务共享相同的数据中心在一个VM。当父任务和子任务执行在不同的虚拟机,属于同一个云提供商,没有任何数据传输费用,因为大多数的公共云提供商,比如Amazon EC2,不收取内部数据传输在他们的计算资源。所以,当我们使用这些公共云计算资源,我们可以忽略数据传输费。本文的其余部分,我们将假设我们只利用计算资源从一个云提供商。

使用成本的计算资源从资源占领时间乘以计算资源的价格。资源占用时间,用RT,不仅关注任务执行时间(ET),而且数据传输时间(TT)和初始启动时间(BT)的每个资源配置工作流。因此,RT = BT + TT +等。然而,随着码头工人技术的发展,虚拟资源的初始启动速度秒或毫秒的顺序。它太小而工作流的执行时间,它可以被忽略。也就是说,我们可以假定BT = 0。当父母之间的数据传输发生的任务t_我及其子任务t_j,传输时间只取决于数量的数据转移和云提供商提供的带宽。这些值都是固定的,无论哪一类型的虚拟机配置的工作流程。因此,每个任务的数据传输时间的价值t_我可以用TT_我VM-independent。对于一个虚拟机_j可以用,资源占用时间 ,在哪里等_ij任务的执行时间吗t_我(1≤我≤n在虚拟机_j和TT_我的数据传输时间吗t_我这是VM-independent。每个任务t_我(1≤我≤n)可能是也可能不是由VM执行_j(1≤我≤米)。让一个_ij是一个0 - 1变量指明t_我VM上执行_j;当t_我是由虚拟机执行_j,一个_ij= 1,否则,一个_ij= 0。所以每个VM的成本_j可以用 。为了优化总成本,我们需要最小化C_j。的公式C_j,我们看到,等_ij和一个_ij是两个变量,依靠t_我和VM_j,而TT_我只取决于t_我但不是虚拟机_j。因此,TT_我可以被视为一个常数的成本优化的观点。剩下的纸,我们可以忽略TT_我。

实际上,任务不需要完全由一个虚拟机执行。它可以按顺序执行几个虚拟机只要执行恰逢一个计费周期。例如,假设t_我一个VM上执行了一个计费周期尚未结束;然后它住在同一个VM的选择下一个计费周期或切换到不同的虚拟机。让等_我表示任务的执行时间t_我。然后,t_我将被 计费周期,天花板等_我由于VM的最后账单周期吗_j(假设VM_j是最后一个VM配置t_我)。因此,资源配置的成本任务t_我可以表示为C_我=⌈等_我⌉×价格,价格是价格向量 。所以, 。一个工作流的总成本可以被定义如下:

定义3。假设有一个工作流 与n任务描述的定义1,虽然有米 中定义的定义2可以配置工作流 。资源配置工作流的总成本是 ,在哪里,x_ij计费周期的虚拟机的数量吗_j这规定的任务t_我。所以, 。让 ,我们有。
注意,在上面的定义,我们认为,没有两个任务结合在一起。例如,假设有两个任务t₁和t₂1.5计费周期的每个要求执行。如果我们将两个任务结合在一起,它只需要3.0计费周期。然而,在上面的定义中,他们将需要4个计费周期,两个计费周期为每一个任务。我们将讨论如何将两个任务结合在一起在以后的部分。

3.2。有效的资源配置

3.2.1之上。优化目标

在云计算环境中资源配置可能有不同的目标。这项工作重点是找到一个供应战略执行工作流等IaaS云总执行成本最小化和最后期限是满足。我们假设米类型的虚拟机;计算每账单周期的性能和价格 被定义为在定义2。根据定义3,成本优化的目标是找到一个资源配置 满足以下几点: 在哪里是所有任务的总和的工作量,x_jVM使用的计费周期的数量吗_j对于所有的任务,D工作流程的最后期限吗中定义的定义1,工作流程的总执行时间吗 。它通常是知道的不仅是受每个任务的执行时间也与工作流中的所有任务的执行顺序。也就是说,sequencial工作流的执行时间,如图2(一个)将每个任务的执行时间之和,而并行工作流如图2 (b)需要最长的运行任务的运行时间作为它的执行时间。所以一个工作流的执行时间定义如下:

定义4。假设有一个工作流 与n任务描述的定义1。如果工作流是一个连续的过程,可以表示为执行时间 。如果工作流是一个平行的过程,执行时间可以表示为 。等_我在这两个公式表示工作流中每个任务的执行时间。所以,如果工作流包含相同的任务并行工作流的执行时间必须小于顺序工作流。
表所示2是一个例子的三种类型的虚拟机计算性能P_j价格和价格_j每个计费周期。在这个例子中,我们假设账单周期是一个小时。
当我们提供这三种类型的虚拟机的任务示例工作流如图1每个VM上,每个任务执行的成本如表所示3。从这个表可以看出,当 ,配置虚拟机₃需要1小时是0.1,而配置虚拟机吗₁或虚拟机₂需要不到1小时但被指控0.8或0.4。因此,最优配置t₁是一个虚拟机₃和0.1。在表3,每个任务的最优单VM配置以粗体显示。请注意,对t₁,t₂,t₃,t₅,他们每个人的最优配置是使用一种类型的虚拟机。为t₄,最优配置是使用一个虚拟机₁和一个虚拟机₂1.2的总电荷。为t₆,最优配置是使用一个虚拟机₂和一个虚拟机₃0.5的总电荷。
所有任务的总工作量的工作流程如图1是146。最优配置是使用五个VM₁4.0的总电荷。注意,这是不到的总和4.2每个任务的最优配置。这是因为每个个体最优配置可能有空闲时间。例如,对于t₅,我们使用一个虚拟机₁可以执行30 MFLOPS一小时,但t₅只有一个工作负载的26 MFLOPS。所以,4 MFLOPS浪费。列世界基督教联合会和新南威尔士州将在稍后解释。

3.2.2。成本优化策略

被认为是需要提供的计算工作量。决策变量x_k计费周期的虚拟机的数量吗_kIaaS提供商租用的。让虚拟机按照nonincreasing性能与价格;也就是说,P₁/价格₁≥P₂/价格₂≥…≥P_n/价格_n。虚拟机被认为是在这个秩序。也就是说,VM₁被认为是第一,紧随其后的是虚拟机₂,等等。最优值函数当限制使用kvm可以定义由以下方程。

最优值函数是由 。求解方程(2通过考虑VM)我们使用动态编程₁第一。如果有一些空闲时间在使用VM₁(因为它不使用完整的计费周期),VM₂将考虑使用VM留下的剩余时间₁。如果虚拟机₂还有空闲时间,VM₃会被认为是下一个。重复这个过程,直到我们达到VM_米。以下是动态规划算法求解方程(2)。

最后一个的最低成本是供应吗米类型的虚拟机实现的计算工作量 。

vm配置单独的任务可能导致空闲时间,除非能匹配计算任务的计算工作负载的性能vm配置。但这个匹配的概率很低。如果我们一起组装一些任务提供虚拟机,可以显著提高资源利用效率。如表所示3最优成本和分别是0.1和0.8。然而,如果我们把和在一起,总工作量是30。因此,最佳的结果是使用一个虚拟机₁这将花费0.8。这样的成本是低于配置vm的总成本和分开。结果,更多的任务我们可以组装配置作为一个整体,我们可以省钱的租赁资源。为了最小化工作流执行的总成本,这将是更好的提供所有任务工作流作为一个整体。如果我们组装所有的任务作为一个单独的任务,它将要求所有任务顺序执行。执行时间可能超过时间约束的工作流。根据定义4从这个顺序,一些任务应该分区过程,而其他任务可以并行执行。为了减少总执行时间满意时间约束,一些工作流分区战略将在下一节中讨论。

3.2.3。最后期限保证方法

当大于时间约束的工作流 ,工作流不能在最后期限之前完成工作。在现实生活中,会议的最后期限的约束是非常重要的,因为许多实时工作流是紧迫的计算(33)支持紧急计算如恶劣天气预测飓风、洪水、地震等。因此,时间约束是一个非常重要的维度对工作流的服务质量(QoS)。时间约束的工作流执行时必须考虑优化成本。保证工作流可以在最后期限之前完成,工作流可以分割成几个sub-workflows,每个sub-workflow可以并行执行,所有任务在一个sub-workflow应该执行顺序没有超过时间限制。每个sub-workflow执行时间将确保整个工作流的最后期限前完成。这样一系列的时间限制为每个sub-workflow必须定义。

关键路径之间的最长的工作流执行路径的入口和出口任务工作流(34]。属于关键路径的所有任务被称为关键任务。之和计算工作负载的关键任务是最大而其他路径的工作流。关键任务顺序执行,因为它们之间的亲子关系。关键路径的执行时间表现最好的VM不得超过时间约束D。否则,没有解决方案,能满足最后期限的约束。在本节的其余部分,我们认为关键路径的执行时间不超过D。

假设工作流划分为若干sub-workflows。sub-workflows之一包含所有的关键任务和其他一些(可能没有)非关键任务。这sub-workflow将称为临界sub-workflow(世界基督教联合会)。不包含关键任务被称为非关键的sub-workflows sub-workflow(新南威尔士州)。只能有一个世界基督教联合会r(r≥0)新南威尔士州。

假设有一个世界基督教联合会 。如果我们提供表现最好的VM产生的总执行时间如果≤D,然后会有一个成功的配置,可以保证工作流在最后期限之前完成,因为其他的新南威尔士州可以与世界基督教联合会在并行执行。另一方面,如果 ,是不可能获得成功的配置vm的世界基督教联合会因为违反了最后期限。在这种情况下,我们必须分区这个世界基督教联合会变成新的新南威尔士州和日间召开包括更少的任务。新的世界基督教联合会包括所有关键任务少但非关键任务。这个过程可以重复直到世界基督教联合会可以在最后期限前完成。同时,任何其他新南威尔士州的执行时间必须满足时间约束进行了分层的方法。

作为一个工作流,必须有一个结构,决定了每个任务的执行顺序的工作流。实际上,所有父任务应该完成子任务之前就可以开始了。我们可以使用一个分层的方法来确保这样一个序列。工作流可以分为几个层面(层),将顺序执行。同时任务在一个水平不相互依赖,这样他们就可以并行执行。

定义5。假设有一个工作流中定义的定义1。定义层0退出任务。层d由所有的任务都有最长路径d边在工作流层0 。因此,层d定义一个年代 ,在哪里 例如,工作流如图1可以分为五个层次,如图3。只要执行任务级别从高到低,所有父任务之前将完成子任务开始。没有执行顺序的任务在同一水平。因此,示例工作流如图3可以安排一个序列:t₁⟶t₂⟶t₃⟶t₄⟶t₅⟶t₆或t₂⟶t₁⟶t₄⟶t₃⟶t₆⟶t₅。
为了保证可以满足最后期限,我们必须有 ,在哪里sub-workflow是至关重要的。此外,所有任务的总执行时间在每一层的每个新南威尔士州不得超过所有任务的执行时间在同一层世界基督教联合会。因此,根据世界基督教联合会的执行时间,我们呈现层最小执行时间(LMET)如下:

定义6。假设一个工作流中定义的定义1分为l层是提单(0)、提单(1),提单…(l−1)。如果 ,任务层的数量在哪里d是年代,然后提单的层最小执行时间(d)是 ,在哪里P_jIaaS可以提供最佳的性能和吗的工作负载 。
至于新南威尔士州,如果ET(提单(d)≤LMET (d), ,然后新南威尔士州能满足的时间约束。否则,部分新南威尔士州应该分区从原来的新南威尔士州。重复这个过程,直到不平等等(提单(d)≤LMET (d)可以满足。
把示例工作流如图1例如;我们假设最后期限是四个小时。使用表现最好的虚拟机,虚拟机₁,如表所示2要执行此工作流,结果(TW列表所示3)表明,使用一个虚拟机₁将会有五个计费周期= 4.87 >D。所以工作流必须被分割成两个sub-workflows。基于关键路径t₂⟶t₄⟶t₅,我们可以得到一个世界基督教联合会和新南威尔士州,如图4。这个分区后,= 3.87 <D,而ET (t₁)< LMET(3) = 1和ET (t₃)< LMET (2) = 1.47。所以,新南威尔士州如图的时间约束4可以满足。每个sub-workflow的成本也表所示3(世界基督教联合会和新南威尔士州列的表3)。世界基督教联合会和新南威尔士州4的总成本等于最优成本。所以工作流分区如图4是一个成功的成本优化方案。

4所示。有效的资源配置算法

4.1。算法设计

全球资源配置算法的基本思想是,对于一个给定的工作流程所示的定义1,使用动态规划方法来优化资源配置的成本,和基于关键路径的工作流分区技术是用来保证的期限要求实时工作流。具体来说,期限是否满足必须由资源配置在并行算法采用动态规划过程;一旦不能满足最后期限,一个工作流分区程序是用来将工作流划分为一些sub-workflow;每个sub-workflow能够满足自己的时间约束;那么这些sub-workflows可以应用动态规划背包算法获得最具成本效益的资源配置方案。这些算法都是基于工作流层算法。因此,我们的策略是在细节的整个过程如下。

我们首先把工作流l层根据定义5。第二,使用动态规划算法在前一节中,我们提供米类型的vm工作流好像所有任务执行顺序从提单(l−1)提单(0)。如果 ,配置失败。然后我们工作流分割成一个世界基督教联合会和新南威尔士州。而 ,我们保持分区,直到对于每一层 我们有ET(提单(d)≤LMET (d)。现在我们将动态编程算法应用于提供vm世界基督教联合会和所有的新南威尔士州。 该算法得到的最优资源配置的结果,和最低成本 。该算法可以实现全局优化的成本,这是表示在全球资源配置实时工作流算法所示算法1。

被调用过程WorkflowLayer ( )在GRP4RW算法层工作流根据定义5。WorkflowLayer算法显示了算法的伪代码2。

首先,(2 - 8行)计算每个任务的最长路径t_我来t_退出双相障碍(t_我)。接下来,(第四行)分配BD的任务相同的值(t_我)同一层。然后,在nonincreasing任务在同一层的工作负载(12行)。这个分区的影响更大的任务sub-workflow sub-workflows的数量降到最低。以这种方式成本优化将会更有效率。使用该算法,工作流可分为l层,每一层包含所有具有相同长度的任务t_退出。

下一个被调用过程ParallelProvision (虚拟机,D)在GRP4RW算法实现并行配置资源的多个sub-workflows为了保证每个sub-workflow的成本效益的前提下会议的最后期限。资源配置并行算法的伪代码所示算法3。

该算法首先尝试动态编程背包算法(DPK)所示的算法4提供虚拟机原工作流(2 - 3行)。如果成功,它将返回优化的条款X(4 - 5行)。否则,它调用分区工作流算法(PartitionPath)所示的算法5分区工作流和(第7行),然后递归地调用ParallelProvision过程分别为世界基督教联合会和新南威尔士州(8 - 12行),直到所有sub-workflows成功提供vm。至于 ,时间约束总是最后期限。的时间约束可以从一层最小执行时间根据定义呢6。

这种动态编程背包算法是基于动态规划的思想阐述了方程(3)。首先,该算法将判断工作流可以在固定时间内完成约束D(2行)。如果使用VM和最好的计算性能执行工作流将不会满足最后期限的限制,程序将返回失败(第3行)。否则,它利用动态规划的方法来找到VM配置向量X然后返回(5 - 20行)。请注意,D是一个实数表示的计费周期的数量。

分区的任务工作流算法是当前工作流或sub-workflow分割成两个部分:和 。的包括,但不限于,关键的任务。另一部分, ,不包含任何重要的任务。我们使用一个布尔变量t_我.assigned表示的可行性t_我在 。因为所有关键任务不能投入 ,的初始值t_我.assigned应该设置为“false”,除了关键任务(2 - 9行)。我们选择的非关键路径之间的两个关键任务的基础(10-31行)。一次任务t属于 ,父母的任务t尚未分配必须属于(11行)。这样一个原则可以使sub-workflow尽可能大分配性价比最好的资源部分中解释3.2.2。与此同时,父母和孩子的任务属于一个sub-workflow能保证正确的任务执行顺序(父任务完成子任务之前)。

4.2。算法分析

我们现在考虑我们的算法的时间复杂度。我们假设在工作流任务的数量是n的最大数量,类型的虚拟机米。最耗时的部分全球资源配置实时工作流(GRP4RW)算法WorkflowLayer和ParallelProvision程序。剩下的部分GRP4RW算法的时间复杂度O(米)。

WorkflowLayer算法的第一部分(1 - 4行)是一个计数循环的时间复杂度O(n)。另一个计数循环(6 - 9行)会重复l次,根据工作流程分为层数。l将不超过n因为必须有至少一个任务在每个层。所以总WorkflowLayer过程的时间复杂度O(n)。

ParallelProvision过程是一个递归过程。首先,它调用DPK过程,规定每种类型的vm只有一次。所以,DPK过程的时间复杂度O(米)。然后,另一个程序PartitionPath可能会被称为,时间复杂度O(n)。这是因为每个任务属于或 ,和每个任务将只分配一次。因为工作流将划分为两个sub-workflows通过调用PartitionPath过程,的最大数量乘以ParallelProvision过程将被调用 。因此,ParallelProvision过程的时间复杂度O(米⋅n+n⋅n)=O(n⋅(米+n))。因此,全球资源配置的总体时间复杂度算法实时工作流O(n)+O(n⋅(米+n)+O(米)=O(n⋅(米+n))。

5。绩效评估

在本节中,我们提出我们的全局资源配置问题的实证研究实时工作流算法。

5.1。仿真设置

我们评价资源配置算法,测量其性能在一些示例工作流。Deelman等人开发了一个工作流生成器,它可以创建任意大小的人工工作流,类似于现实世界实时工作流。使用这个工作流生成器,他们创造了四种不同大小为每个工作流应用程序的任务的数量。这些工作流在DAX指数(XML)中有向无环图格式从他们的网站35]。对于我们的实验中,我们选择了三种尺寸小(约50个任务),中等(约300任务),大(约1000)的任务。与此同时,为了探索不同的工作流结构对算法性能的影响,三种不同长度的关键路径担心在我们的模拟。然而,每一种工作流的关键路径长度由这个工作流生成器是固定的和小于10个任务,所以我们必须组织几个工作流构建关键路径的时间越长,我们需要。例如,我们可以连接5关键路径长度为8和1关键路径长度为10的端到端,以便得到一个关键路径长度为50。

对于我们的实验中,我们模拟一个IaaS提供商提供一个数据中心和六种不同类型的虚拟机与不同的处理器速度和不同的价格。VM配置是基于当前Amazon EC2服务。我们使用的工作Ostermann et al。32)估计的计算性能MFLOPS基于EC2计算单位的数量。实验的另一个重要参数是一个计费周期的时间单位。大多数当前的商业云,如亚马逊、收费用户计费周期的基础上一个小时。因此,我们使用一个VM账单周期的一个小时。

工作流的大量不同的属性是用于我们的实验,是很重要的正常化每个工作流执行的总成本,以便清楚地分析成本优化问题。出于这个原因,我们首先把所有的任务工作流作为一个整体,并使用动态规划方法来解决它。我们定义这种成本低廉的成本(CC)。注意,最便宜的成本是通过忽略最后期限的约束。工作流执行的标准化的成本(NC)被定义为数控=(总成本提供vm) / CC, CC在哪里最便宜的成本相同的vm配置工作流。注意配置vm在数控的最后期限的总成本约束。由于最后期限的限制,显然我们有数控≥CC。

评估算法,我们需要为每个工作流分配一个最后期限。为了设置一系列适当的期限对我们的实验中,我们定义一个上界的期限的时间最便宜的成本(CC)情况和一个下界的考最好的火蚁超人VM上的关键路径执行的顺序排列的。D_U和D_l分别表示的上下界的最后期限。设置最后期限工作流程中,我们使用期限的因素α,我们设置一个工作流的最后期限 ,在0≤α≤1。我们让α上升的步骤0.1;也就是说,α= 0,0.1,0.2,0.9,1.0,…。

我们所知,许多作品结合资源配置和任务调度工作流执行的成本降到最低;IC-PCP算法是经典的这些作品之一。因此,我们采用IC-PCP算法作为基准来评估我们的算法。就像前面提到的2IC-PCP算法旨在最小化工作流执行的成本,同时满足用户定义的最后期限(17]。该算法首先计算(最早开始时间),EFT(最早完成时间),和融通(最新完成时间)的每个任务。然后找到相关的部分关键路径EST, EFT和融通。每条路径上的任务是安排在同一个VM,最好是分配给一个已经租赁实例可以满足任务的融通的EST的值时,小蜥蜴,融通的每个未分配的任务的更新。最后,每个未赋值的计算任务调度路径和重复这个过程,直到所有任务已经安排。的这个过程中,每一个任务被分配一个虚拟机,并与之关联的开始和结束时间。IC-PCP算法也旨在优化成本但专注于任务调度。IC-PCP算法的时间复杂度较高,它缺乏灵活性。此外,我们使用简单的DPK算法的每个任务工作流作为另一个比较参考清单全球成本优化思想的重要性。

5.2。仿真结果

图5显示之间的关系成本GRP4RW算法和优化资源配置的最后期限。图5(一个)显示结果与不同大小:小尺寸(50个任务),中等大小(300任务),和大尺寸(1000任务)。这些不同大小的变化趋势相似的归一化成本与每个不同的截止日期。工作流任务越多,越温柔的归一化成本的变化与不同期限。工作流程的规范化变动成本最小的尺寸是显而易见的。图5(一个)显示的性能成本优化我们的算法更加稳定作为工作流的规模更大。

图5 (b)显示了不同结构的工作流影响标准化的成本的变化。因为大尺寸工作流显示更稳定的标准化的成本,我们使用三个大型工作流任务(1000)与不同长度的关键路径(CP)。关键路径的长度是50个任务,任务,100和200的任务。结果表明,有一个几乎成反比标准化之间的线性关系成本和工作流的期限最长的关键路径。然而,工作流的关键路径最短最加快收敛到优化随着最后期限越来越大。因此,我们提出成本优化算法可以更有效截止日期设置为低水平的工作流关键路径较短。

因为成本优化的性能较大的规模和较长的关键路径更好、更稳定,我们带着一个工作流1000任务关键路径的长度是200年作为仿真实例来比较性能三个成本优化算法:GRP4RW, IC-PCP,只是DPK。图6显示的结果比较。简单的归一化成本DPK算法不不同期限的变化因素,它总是保持高价值。IC-PCP算法的标准化的成本随期限的增加而减小。GRP4RW算法的标准化的成本减少有一定期限的变化和成本的值通常是低于IC-PCP和简单DPK算法在每一个最后期限。这些结果有三个原因。首先,简单DPK算法使用动态编程背包方法每一个任务的工作流。因此,其优化效果温和和deadline-invariant。第二,IC-PCP包含合并后的想法使用部分关键路径算法为优化单位。这使得优化效果显著提高,但动态编程方法不利用该算法导致次优的规范化不同期限的成本。最后,全球思想和动态编程背包方法用于GRP4RW算法。 So the optimization effect achieves the optimal result. In conclusion, global idea is the most important force in the cost optimization of resource provisioning algorithm for real-time workflow. At the same time, dynamic programming knapsack method also plays a positive role in the whole process.

考虑到计费周期的长度会影响成本优化算法的性能,我们研究了影响计费周期的长度之间的关系和任务的执行时间工作流通过仿真实验对算法的性能。任务的执行时间严重取决于任务的工作量,我们使用三种不同的工作流不同工作负载的任务:一个工作流表示工作流与小工作量超过90%的任务负载小于1 MFLOPS,另一个工作流表示工作流与中等负荷超过90%的任务1 - 5 MFLOPS,第三个工作流表示工作流与大工作量超过90%的任务负载超过5 MFLOPS。同时我们用30秒、60秒,120秒、300秒、600秒、1200秒计费周期的不同长度。实验结果如图所示7。它表明,计费周期的长度对算法性能的影响;与计费周期的长度的减少,成本优化效果的算法在一定程度上得到改善。当账单周期是30秒的长度,这些算法是最优的性能。当账单周期的长度3600秒,算法的性能简单DPK显著减少,而算法IC-PCP和GRP4SW还说得过去。也就是说,当任务的执行时间非常小于账单周期如工作流与小负载的情况下账单周期的长度是3600秒(见图7(一)),计费周期的长度对算法的性能影响是更重要的,我们的算法GRP4SW最优势条件。

6。结论

在本文中,我们提出了一个全球资源配置算法执行实时工作流在云。我们建模问题作为一个优化问题,旨在得到一个有效的资源配置执行工作流,同时满足最后期限的约束。解决了这个问题通过使用动态编程背包算法。我们的方法体现了基本的IaaS云属性资源异构性和弹性等性能和现收现付价格机制的模型。

我们使用三种不同的大小和执行仿真实验分别三种不同结构的实时工作流。我们的结果表明,我们建议的解决方案的成本优化改善随着期限的增加。我们比较算法的性能与其他两个算法(只是DPK和IC-PCP)。我们的结果表明,我们建议的GRP4RW算法整体比简单地DPK和IC-PCP算法更好的性能在每个期限限制。

对于未来的工作,我们要改善我们的策略,优化数据存储和数据传输实时工作流执行的成本。此外,越来越多的研究集中在优化目标对安全或能耗的QoS (36,37];最重要的问题是实现多目标优化。

数据可用性

本研究中使用的工作流可以通过访问网站http://confluence.pegasus.isi.edu/display/pegasus/WorkflowGenerator。

的利益冲突

作者宣称没有利益冲突。

确认

这部分工作是由中国国家自然科学基金(项目没有。61972001)。

引用

1. A . Ramlatchan m .杨问:刘,m . Li j . Wang和y,“矩阵的调查完成推荐系统的方法,”大数据挖掘和分析,1卷,不。4、308 - 323年,2018页。视图:出版商的网站|谷歌学术搜索
2. m . c . Zhang杨、j . Lv和w·杨,“一种改进的混合协同过滤算法基于标签和时间因素,”大数据挖掘和分析,1卷,不。2、128 - 136年,2018页。视图:出版商的网站|谷歌学术搜索
3. x徐、刘问:y罗et al .,“在大数据计算卸载方法IoT-enabled cloud-edge计算,”未来一代计算机系统卷,95年,第533 - 522页,2019年。视图:出版商的网站|谷歌学术搜索
4. x, s .傅l . Qi et al .,“IoT-oriented数据放置方法和隐私保护在云环境中,“网络和计算机应用》杂志上卷,124年,第157 - 148页,2018年。视图:出版商的网站|谷歌学术搜索
5. m . c . Zhang杨、j . Lv和w·杨,“小说深度混合动力与神经协同过滤推荐系统基于auto-encoder,”大数据挖掘和分析,1卷,不。3、211 - 221年,2018页。视图:出版商的网站|谷歌学术搜索
6. x, r·莫f .戴w·林,s .广域网和w .窦,“动态资源配置与容错数据密集型气象工作流在云,“IEEE工业信息2019年出版社。视图:出版商的网站|谷歌学术搜索
7. j .周x胡,y, j .太阳,t·魏和美国,“提高可用性的多核实时系统遭受永久性和瞬态故障”IEEE计算机,卷68,不。12日,第1801 - 1785页,2019年。视图:出版商的网站|谷歌学术搜索
8. j .周j .太阳x周et al .,“资源管理对提高软件出错和生命周期的可靠性实时MPSoCs,”IEEE计算机辅助设计的集成电路和系统,38卷,不。12日,第2228 - 2215页,2019年。视图:出版商的网站|谷歌学术搜索
9. 问:他y, k . Wang et al .,“Covering-based web服务质量预测通过neighborhood-aware矩阵分解,“IEEE服务计算2019年出版社。视图:出版商的网站|谷歌学术搜索
10. 崔张y, g,邓,f . Chen y . Wang,问:他“高效查询服务组合的质量相关,”IEEE服务计算2018年出版社。视图:出版商的网站|谷歌学术搜索
11. w·龚、l . Qi和y,“Privacy-aware多维移动服务质量预测和推荐雾在分布式环境中,“无线通信和移动计算卷,2018篇文章ID 3075849、8页,2018。视图:出版商的网站|谷歌学术搜索
12. Y.-W。张,y y。周,这。王,z的太阳,问:他,”服务推荐基于商空间粒度分析和覆盖算法在火花,“以知识为基础的系统卷。147年,25 - 35,2018页。视图:出版商的网站|谷歌学术搜索
13. 吴y, c .阴问:问:他和h·朱,“位置感知的深度服务建议,协同过滤”IEEE系统,人,和控制论:系统2019年出版社。视图:出版商的网站|谷歌学术搜索
14. l .气他,f . Chen等人”找到你所需要的:web api推荐在web通过关键词搜索的东西,“IEEE计算社会系统》第六卷,没有。5,1063 - 1072年,2019页。视图:出版商的网站|谷歌学术搜索
15. l .七张x, s, s .广域网,y,和w·龚“时空数据驱动的服务推荐与隐私保护,”信息科学卷,515年,第102 - 91页,2020年。视图:出版商的网站|谷歌学术搜索
16. h . h . Liu口,c .严,l .气”链接预测纸引文网络构建关联图,“EURASIP无线通讯和网络》杂志上,卷2019,不。1、2019年出版社。视图:出版商的网站|谷歌学术搜索
17. s . Abrishami m . Naghibzadeh和d·h·j . Epema”Deadline-constrained工作流调度算法基础设施作为服务云,“未来一代计算机系统卷,29号1,第169 - 158页,2013。视图:出版商的网站|谷歌学术搜索
18. m·a·罗德里格斯和r . Buyya”,期限为科学工作流资源provisioningand调度算法基于云,“IEEE云计算,卷2,不。2、222 - 235年,2014页。视图:出版商的网站|谷歌学术搜索
19. e . n . Alkhanak s p·李,r·雷和r . m . Parizi”成本优化方法在云计算和网格计算科学工作流调度:复习一下,分类,和开放的问题,“系统和软件杂志》上卷。113年,1-26,2016页。视图:出版商的网站|谷歌学术搜索
20. Verma a和s Kaushal花费的时间高效的调度计划执行工作流的云,“《网格计算,13卷,不。4、1 - 12,2015页。视图:出版商的网站|谷歌学术搜索
21. w·郑y秦,e . Bugingo d . Zhang和j·陈,“成本优化deadline-aware调度在云端的大数据处理工作,“未来一代计算机系统卷,82年,第255 - 244页,2018年。视图:出版商的网站|谷歌学术搜索
22. c·杨和x张,“基于遗传算法的工作流任务调度优化的云,”学报2018年IEEE国际会议上云计算和大数据分析,页6 - 10,成都,中国,2018年4月。视图:谷歌学术搜索
23. 李振国陈,k . j . Du z h·詹和j·张,“最后期限限制云计算资源调度基于动态目标成本优化遗传算法,”学报2015年IEEE国会进化计算(CEC)仙台,页708 - 714年,日本,2015年5月。视图:谷歌学术搜索
24. Verma A和s Kaushal混合多目标粒子群优化科学工作流调度,“并行计算卷,62 - 2017页。视图:出版商的网站|谷歌学术搜索
25. 问:吴,石川,问:朱,y夏,和j .温”Deadline-constrained成本优化方法在云工作流调度”IEEE并行和分布式系统,28卷,不。12日,第3412 - 3401页,2017年。视图:出版商的网站|谷歌学术搜索
26. j .史j·罗、f .董和j .张“预算和最后期限意识到科学工作流资源配置和调度机制,云,”学报2014年IEEE 18国际会议在计算机支持的协同工作的设计(CSCWD)新竹,页672 - 677年,台湾,2014年5月。视图:谷歌学术搜索
27. 诉Arabnejad、k . Bubendorfer和Ng,“云资源调度期限约束科学工作流动态供应,”未来一代计算机系统卷,75年,第364 - 348页,2017年。视图:出版商的网站|谷歌学术搜索
28. 诉辛格。古普塔,p . k . Jana”小说的方法deadline-constrained工作流调度资源的动态配置,“未来一代计算机系统卷,79年,第110 - 95页,2017年。视图:出版商的网站|谷歌学术搜索
29. 美国穆罕默迪、h . Pedram和l . Pourkarimi“整数线性programming-based成本优化调度的科学工作流在多重云环境中,“《华尔街日报》的超级计算,卷74,不。9日,第4745 - 4717页,2018年。视图:出版商的网站|谷歌学术搜索
30. j . j . Durillo r . Prodan和j·g·巴博萨,”帕累托权衡的工作流调度联合商业云,“仿真建模实践和理论58卷,第111 - 95页,2015年。视图:出版商的网站|谷歌学术搜索
31. Amazon Elastic Compute Cloud, 2016,http://aws.amazon.com/ec2。
32. s . Ostermann A . Iosup n . Yigitbasi r . Prodan t . Fahringer和d . Epema”EC2云计算服务的性能分析科学计算,”学报2009年云计算国际会议施普林格,页115 - 131年,班加罗尔,印度,2009年9月。视图:谷歌学术搜索
33. r . Tolosana-Calasanz j . A。Banares、c·范教授和o . f . Rana”执行QoS在科学工作流系统实施在云基础设施,“计算机与系统科学杂志》上,卷78,不。5,1300 - 1315年,2012页。视图:出版商的网站|谷歌学术搜索
34. s . Abrishami m . Naghibzadeh和d·h·j . Epema“成本驱动的网格工作流调度使用部分关键路径,”IEEE并行和分布式系统,23卷,不。8,1400 - 1414年,2012页。视图:出版商的网站|谷歌学术搜索
35. Workflowgenerator, 2014,http://confluence.pegasus.isi.edu/display/pegasus/WorkflowGenerator。
36. j .周j .太阳,p .丛et al .,“强调安全节能意识任务调度在物联网异构实时MPSoCs”IEEE服务计算2019年出版社。视图:出版商的网站|谷歌学术搜索
37. l .气y, y元,s .傅张x, x徐,“QoS-aware虚拟机节能调度方法在基于云的cyber-physical系统中,“万维网,23卷,不。2,第1297 - 1275页,2019年。视图:出版商的网站|谷歌学术搜索

版权

版权©2020吴Lei et al。这是一个开放分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。