更好的工作流执行时间估计方法的研究及其在云计算中的应用

© 2014年。出版社：Elsevier B.V.信息工程研究院负责评选和同行评议可在www.sciencedirect.com在线获取ScienceDirectIERI Procedia 10（2014）216 - 2232014未来信息工程一种更好的工作流执行时间估计阿特姆·M Chirkina，b，Sergey V. Kovalchuka， *aITMO大学，Birzhevaya线，4，199034，圣彼得堡，俄罗斯联邦b阿姆斯特丹大学，Spui 21，1012 WX，b阿姆斯特丹，荷兰摘要作者强调的重要性，估计工作流执行时间的调度问题和定价模型在云中。声称需要开发更好的方法来获得执行时间的精确估计。描述随机执行时间估计的直接回归。提出了一种Chebyshev类分布自由不等式和基于分布的方法的组合，以计算更好的置信界运行时的统计测试的结果的基础上。最后，作者解释了需要开发更好的算法来计算工作流的执行时间基于任务的执行时间的随机估计。说明了开发更好的工作流运行时间估计算法的必要性。最后，提出了一种基于任务执行时间随机估计的工作流执行时间估计方法版权所有© 2014作者.出版社：Elsevier B.V. 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究院负责评选和同行评议关键词：运行时，执行时间，工作流，调度1. 介绍如今，研究和生产计算问题需要更多的计算资源。因此，基于网格和云技术的异构系统（HS）变得越来越流行，因为它们* 通讯作者。联系电话：+7-962-687-0460;传真：+7-812-232-23-07。电子邮件地址：kovalchuk@mail.ifmo.ru。2212-6678 © 2014作者出版社：Elsevier B.V. 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究所负责的选择和同行评审阿特姆·MChirkin和Sergey V.Kovalchuk/IERI Procedia 10（2014）216217在扩展资源、使用大数据量、在不同计算机上运行单个服务作为复杂引擎的一部分的可能性方面提供高度灵活性[1]。这项工作解决的问题，估计在HS复杂任务的执行时间。在HS中执行的复杂任务通常由几个原子任务（阶段）组成，并形成一个工作流。我们将工作流称为任务和它们之间的信息依赖关系的集合;这些依赖关系对任务的执行顺序施加了一些限制。许多论文被写来描述工作流管理系统的不同实现（例如[2，3]）。研究人员在开发管理系统时要解决的主要问题是如何以最有效的方式调度工作流：最小化执行时间，成本，满足某些截止日期或其他约束[4，5]。我们说HS包含许多提供服务的包（应用程序）;工作流的每个任务都是单个服务的执行。此外，HS包含节点（计算单元）的数量。调度问题是将任务最优地映射到节点上。通常用于表示工作流的方法是有向无环图（DAG）[4，6，7]。众所周知，DAG中的一般调度问题的复杂性是NP完全的[8]，因此存在许多算法，可以为调度问题提供近似最优的解决方案。调度问题的重要部分是工作流执行时间的估计。我们假设运行时间估计问题不像调度问题那样发展得那么好，因为存在几种直接的技术，这些技术对于许多调度情况都具有可接受的性能。然而，我们声称，这些技术可能会失败，在某些情况下，特别是在最后期限约束设置。此外，在估计工作流执行时间时，还应考虑执行任务之间的相关性、任务与计算资源的异质性、工作流形式的多样性等因素。HS最重要的特点是，一些执行时间组件在其性质上是随机的（数据传输时间，开销等）。这些方面在现代研究中没有被考虑在一起，因此这个问题需要进一步的研究。除了调度，运行时间估计是由HS的客户端使用。云计算提供商创建定价模型，为客户提供计费信息[9];他们必须精确计算执行时间估计，以呈现用户执行工作流的预期价格根据估计的时间范围，可以使用[10]中描述的模型为用户提供预计费信息。这项工作的目的是突出常见的问题，估计工作流执行时间，并提出了一个解决方案，考虑到工作流过程的复杂性和随机性。2. 工作流调度工作流调度是一个复杂的问题，需要考虑不同的方面（如资源模型、工作流模型、调度准则等）。[4]的文件。因此，许多作者描述他们的调度系统的基础设施不专注于运行时间估计。我们将这两个问题分开，以便在一个专门研究一般工作流执行时间问题的研究中获得的结果可以用于复杂的调度系统已经存在或正在开发中。在这样的设置中，估计系统向调度系统提供目标函数（执行时间）的值，类似于调度系统已经在内部计算了它。此外，我们可以使用估计系统，以获得剩余的执行时间在任何阶段的工作流执行，以监控过程或重新调度剩余的任务。自然可以使用运行时间估计模块的任何实现的调度系统的一些示例是CLAVIRE（ITMO大学，圣彼得堡，俄罗斯）[2，11]，由Ling Yuan等人提出的框架。[3][12]《礼记·乐记》今天，已经研究了大量的各种调度算法。其中一些不需要估计工作流运行时间[13，14]，但这会降低调度程序的灵活性和最大可能的有效性[15]。大多数的时间假设可以按照时间假设的类型来分类。第一类假设只需要一个任务是否需要比其他任务更长的执行时间的信息（即，下令218阿特姆·MChirkin和Sergey V.Kovalchuk/IERI Procedia 10（2014）216任务列表），并用于任务级调度策略（不考虑工作流的执行时间）。在[16]中描述了这类调度算法的数量。第二类假设将任务运行时间视为常量值。这是对工作流时间建模的简单方法，但它不允许测量可能的估计误差。一些例子可以在[6，7，15]中找到。最后一种假设利用了执行时间的随机性，并有可能给出最准确的运行时预测。期望值和方差的知识允许测量工作流运行时的不确定性，使用Chebyshev不等式[17]对时间进行粗略的限制;或者，通过五分位数或分布近似，可以对执行时间进行相当好的置信区间，可以用于最后期限约束设置[18]。3. 运行时建模的随机方法除了程序的计算时间外，工作流执行时间还包括数据传输、资源分配等额外成本。因此，单任务处理可以被认为是计算服务调用过程，其执行时间可以用以下方式表示：TR TQ TD TE TO（一）给你，TR 是资源准备时间，TQ-排队时间，TD - 数据传输时间，TE - 程序执行时间，TO-系统开销时间（分析任务结构，选择资源等）。组件模型（1）的详细描述见[11]。如果我们认为成分是随机变量，我们应该分析它们的分布和依赖性。在所有分量都是独立的情况下，我们可以很容易地找到T的均值和方差：E[T][TR] E[TQ] E[TD][TE] E[TO]Var（T）Var（TR）Var（TQ）Var（TD）Var（TE）Var（TO）（二）然而，在因变量的情况下，方差相等是错误的-我们应该添加协方差计算Var（T）的条件。特别地，这与程序执行时间TE和数据传输时间TD：通常执行时间确实显著依赖于数据大小。在这里和后面为了简单起见，我们假设所有组件都包括在总任务执行时间T中。工作流执行时间建模需要解决两个主要问题：数据的统计充分性和假设，以及将任务的执行时间聚合到工作流估计中3.1. 任务执行时间第一个问题与表示执行时间的方式有关，当它适合观察到的数据时。将执行时间T表示为回归模型的最通用方法：DTf（X，）（三）这里X-任务执行参数，由任意空间中的k（）维向量表示;X由应用执行器控制，但可以从回归分析的观点TR-因变量（即执行时间）;f（X，）-回归（随机）函数阿特姆·MChirkin和Sergey V.Kovalchuk/IERI Procedia 10（2014）216219变量（T|Var（f（X，λ））|十）、指定的形式，因此T|X是随机变量; -函数f的未知参数，它们的形式取决于回归函数的表示。这个公式允许表示任何类型的运行时对任务参数的依赖，但很难使用。它可以重写为以下形式：D（X，）（X，）（，）（四）这里（X，）n [T |f（X，X）] n（X，）|X]- 有条件的期望;（X，标准差;X（X，X）-随机变量，在X和T上回归问题包括估计参数ε，从而估计均值、方差，和运行时的条件分发。 该模型可以以三种方式使用：仅计算平均值（X），并假设（X）（X）是无意义的误差（例如[15，19]）;计算平均值和方差，然后使用Chebyshev不等式（例如[15，19]）。[17]）;估计（X），然后计算五分位数[18]。现在假设我们已经完美地估计出了（X）和（X）（或者我们在理论上知道了它们我们可以很容易地证明，|X] E[] 0，Var（|X）Var（）1，Cov（X，）0。通常的方法是假设误差不依赖于输入X。然而，在一般情况下，X依赖于X-这意味着T的分布不仅随X移动或缩放，而且具有变化的形状。 因此，对于X的某些值，时间T可能具有显著更大的右“尾”。由于训练样本（观察到的执行）的大小很小，这会导致错过截止日期的概率出乎意料地高图1.一、Q-Q图- Weibull分布;样本量N = 60;独立性情况下k = 3;依赖性情况下k = 1：1：：3图1显示了合成测试示例中的所述现象。我们从威布尔分布中生成两个小样本来模拟具有不同参数X的运行程序：一个是 比例参数始终调整为Var（）≥1。在此设置中，对于X的高值，这种效果220阿特姆·MChirkin和Sergey V.Kovalchuk/IERI Procedia 10（2014）216如果我们观察整个执行样本（图1.a），则不明显，因为只有少数运行是在某些参数X80的情况下进行的。与此同时，如果我们得到X的缩小区域，我们看到“坏”分布并不完全符合理论上的五分位数（图1）。1.b）。为了检查样本（即程序的执行日志）是否满足独立性条件，应该使用统计假设检验。在连续数据的情况下，平滑的bootstrap检验表现最好[20]。通过对数据进行分类，可以使用Fisher精确上面我们解释了为什么拟合均值和方差来估计分布的直接方法应该谨慎使用，在某些情况下可能会给出错误的结果。如果在统计学上不能接受的分布不依赖于X，那么五分位数就不能直接计算;在这种情况下，独立于分布的不等式（例如，Chebyshev运行时边界。在我们的研究中，我们建议使用独立性检验的p值将分布依赖和分布无关的五分位数结合起来。更正式地说，我们假设以下面的形式估计运行时界限（4）的置信水平：P（TT）P（TT|H，{X n. n}）f（p）<$P（T<$T|n. n}）（1）f（p））（五）u u0n u0n这里p代表假设检验的p值;H0-独立性假设（零假设）; fn（p）- p的某个非减函数，它也取决于样本，表示从独立分布X和中抽取样本的概率。换句话说，我们使用全概率定律计算满足最后期限Tu的概率P（TTu）3.2. 工作流执行时间第二个问题包括工作流执行时间的估计界限。从随机运行时间的角度来看，工作流只是随机变量的和和最大值的组合。如果关于执行时间的唯一可用信息是均值和方差，那么问题的根源是max（E[T1]，E[T2]）E[max（T1，T2）]-并行分支的执行时间不能直接计算。一种解决方法是为每个任务分别计算置信区间。然而，它不能使用，因为它导致多次应用切比雪夫不等式并提高置信界的大小。另一种方法是计算工作流图中所有路径的执行时间的均值和方差（如[17]）。我们认为，在大型工作流的情况下，这种方法可能在计算上过于昂贵。图二. (a-c)三种基本的工作流类型;（d）提高了工作流执行过程中的估计精度;（e）工作流执行过程阿特姆·MChirkin和Sergey V.Kovalchuk/IERI Procedia 10（2014）216221我们提出了一个算法，需要两个描述的方法之间的地方。它包括五个阶段：1) 为计算其均值和方差的分支选择工作流中的所有fork-join部分;例如，在图2中，工作流（a）和（b）由一个部分组成，工作流（c）由三个部分组成（T1;T2和T3;T4）;此过程可以通过将任何任务替换为另一个子工作流来递归执行。2) 评估叉形连接结构的所有（k≤1）平行螺纹的平均值和标准差3) 估计fork-join部分执行时刻的上界和下界（均值和方差）。4) 在外部fork-joins中使用内部fork-joins的估计（最后估计工作流执行时间的时刻）。5) 使用均值和方差估计工作流运行时的界限。我们现在正在努力创建更好的几个变量的最大值的矩的界限，因为这些界限的精度对总估计有很大的影响。类似的方法可以用来直接计算五分位数，而不是使用矩。工作流执行时间估计系统的一个重要特征是当某些阶段被执行而其他阶段未被执行时在工作流执行期间改进估计的能力。我们开发了一个估计系统，它使用不同的方法来计算回归模型（4），总是使用在给定输入下表现最好的方法。为了实现使用实时执行数据的能力，我们在系统中包含了一个虚拟方法，如果一个包已经执行，它会给出观察到的执行时间。图3表示在工作流执行期间对系统的估计。我们模拟了由四个顺序连接的任务组成的简单工作流，将阶段k定义为k≥1的时间包已经执行。所有任务的执行时间大致相同，都是100秒左右（均值和方差各不相同）。我们在工作流执行期间执行剩余执行时间估计。图3.a显示了单个工作流执行;绿色垂直线分隔了各个阶段（即不同包执行的时间）。很容易看出，随着时间的推移，期望值越来越接近现实，但不一定总是改善，但置信区间总是改善。请注意，如果前一个任务花费的时间比预期多（少）得多，则上（下）置信度界限有可能上升（下降）而不是下降（增加）。图3.b表示不同阶段估计误差的相对偏差。对不同的试验取平均值，因此我们进行了40个顺序工作流程估计的1000个实验。通常，估计系统在这40次运行期间进行学习，然而，在绘制的情况下，任务模型太简单（即估计是简单平均，估计器几乎立即学习），无法观察学习过程。很明显，偏差随着级数的增加而减小，因为不确定性（剩余包装的数量）减小。注意，最后一个阶段的方差总是等于零（所有包都被执行）。4. 结论我们表明，执行时间估计在调度问题和HS定价模型中占有重要地位。研究人员在表示执行时间的方式上有所不同;许多调度算法不需要估计工作流运行时间，但这种估计在调度质量中起着关键作用[15]。此外，自定义运行时估计器可以在许多调度算法中使用，而无需修改它们。我们声称，需要开发更好的方法来获得精确的估计执行时间。我们提出了一个Chebyshev类分布自由不等式和基于分布的方法相结合，以计算更好的置信区间上运行时的统计测试的结果的基础上。因此，需要研究更好的工作流运行时间估计算法.最后，提出了一种基于任务执行时间随机估计的工作流执行时间估计方法222阿特姆·MChirkin和Sergey V.Kovalchuk/IERI Procedia 10（2014）216致谢。这项工作得到了俄罗斯联邦政府的资助，赠款074-U 01。引用[1] 尤文，Deelman E.云中的科学工作流网格、云和虚拟化，2011：71-91。[2] Knyazkov K.V. CLAVIRE：e-Science infrastructure for data-driven computing. Journal ofComputational Science，2012; 3（6）：504-510.[3] 袁L，何凯，Fan P.一个基于资源约束的网格工作流调度框架。消费电子、通信和网络国际会议（CECNet），2011：962-965。[4] Wieczorek M.，Hoheisel A.，普罗丹河网格环境下多准则工作流调度的一般模型。未来一代计算机系统，2009; 25（3）：237-256.[5] Kyriazis D.，在服务质量框架下的网格工作流映射机制。未来一代计算机系统，2008; 24（6）：498-511.[6] 陈伟N.，基于蚁群算法的网格工作流调度问题研究。IEEE Transactions on Systems，Man，andCybernetics，Part C（Applications and Reviews），2009; 39（1）：29-43.[7] 氨马拉替南D.I.G.，塞尔维足球会一种最小最大跨度网格工作流调度算法。IEEE计算机通信与信息学国际会议，2012：1-6。[8] El-Rewini H.，刘易斯·T·G Ali H.H.并行与分布式系统中的任务调度。普伦蒂斯-霍尔公司，上鞍河，新泽西州，美国，1994年。[9] Weinhardt C.等人，Cloud Computing A Classification，Busi- ness Models，and ResearchDirections，Business Information Systems Engineering，2009; 1（5）：391-399。[10] Sharma B. Pricing Cloud Compute Commodities：A Novel Financial Economic Model，12thIEEE/ACM International Symposium on Cluster，Cloud and Grid Computing，2012：451-457.[11] Kovalchuk S.V.，紧急计算网络基础设施中的截止日期驱动资源管理。ProcediaComputer Science，2013; 18：2203-2212.[12] Somasundaram T.S.，戈文达拉詹湾CLOUDRB：用于在科学云中调度和管理高性能计算（HPC）应用程序的框架。未来一代计算机系统，2014; 34：47-65。[13] 库欣河，基于预测的科学工作流程自动缩放。第九届网格、云和电子科学中间件国际研讨会论文集（MGC'11），2011年1.一、[14] 奥普雷斯库M. Stochastic Approaches to Self-Adaptive Application Execution on Clouds（云上自适应应用程序执行的随机方法）论文，自由大学，2013年。[15] Korkhov V.网格计算中的分层资源管理。论文，阿姆斯特丹大学，2009年。[16] Gutierrez-Garcia J.O.沈金明基于Agent的云任务袋调度的启发式算法族。IEEE InternationalConference on Cyber-Enabled Distributed Computing and Knowledge Discovery，2011：416-423.[17] Afzal A.，达林顿·J麦高夫A.网格计算环境下具有QoS保证的随机工作流调度。IEEE FifthInternational Conference on Grid and Cooperative Computing（GCC[18] Trebon N.，福斯特岛在现有的分布式计算基础设施中实现紧急计算，博士。论文，2011年。[19] Ichikawa S.，Takahashi S.，河合岛异构机群并行程序进程分配优化。并发与计算：实践与经验，2009; 21（4）：475-507。[20] 吴宜宏，Yu P.L.，李伟一种基于互信息的平滑独立性Bootstrap检验。阿特姆·MChirkin和Sergey V.Kovalchuk/IERI Procedia 10（2014）216223计算统计数据分析，2009; 53（7）：2524-2536.[21] Mehta C.R. Patel N.R.列联表中Fisher精确检验的网络算法Journal of the American StatisticalAssociation，1983; 78（382）：427-434.