异构云计算平台中任务调度的优化算法及应用

沙特国王大学学报异构云计算平台Reza NoorianTalouki，Mirsaeid Hosseini Shirvani，Homayun Motameni伊朗萨里伊斯兰阿扎德大学萨里分校计算机工程系阿提奇莱因福奥文章历史记录：收到2021年2021年5月13日修订2021年5月27日接受2021年6月26日在线提供保留字：启发式列表调度云计算异构系统任务复制A B S T R A C T云计算环境下的任务调度问题是该领域的重要研究课题之一。因为任务调度器应该了解底层平台异构性、任务相互依赖性和虚拟机（VM）变量配置。对于异构资源上的依赖性任务，高效的任务调度算法可以为了减少云计算中的最小总执行时间，最大完工时间，在文献中提出了许多算法，但许多算法的效率很低。针对异构云计算系统中相关任务的调度问题，提出了一种新的任务优先级策略和应用任务复制方法本文的创新之处在于提出了一种新的表调度算法，该算法采用了新的任务优先级策略，并应用了精确的任务复制技术。本文使用乐观成本表向下（OCTd）和乐观成本表向上（OCTu）的过程中优先级的任务在一个有效的有序列表，然后，它利用异构最早完成时间（HEFT）的复制方法执行任务复制技术，显着减少完工时间。为了验证该建议，我们用不同的科学工作流，如分子，LU-样，FFT和蒙太奇数据集实验分析了所提出的调度算法。新的启发式调度算法对其他现有的方法的性能比较证明了该算法的优越性，在最大完工时间，加速比，SLR，和效率，这是突出的调度评价指标。版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍任务调度问题是典型的分布式系统中最重要的问题之一，诸如由大量异构计算资源组成的云计算系统（Alsaidy等人，2020; Bansal等 人 ， 2003; Farzai 等 人 ， 2020; Gkoutioudi 和 Karatza ， 2010;Hosseini Shirvani等人， 2020年）。任务调度就是在一定的约束条件下，以最小化任务的执行时间和最大完工时间为目标，将任务分配给资源，并确定每个任务执行的开始和结束时间。任务调度算法是实现高性能的重要手段*通讯作者。电子邮件地址：mirsaeini_hosseini@iausari.ac.ir（M. Hosseini Shirvani）。沙特国王大学负责同行审查制作和主办：Elsevier异构计算资源（Hosseini Shirvani和Amin，2009; Shirvani等人，2017; Amalarethinam和Selvi，2012）。适当的调度算法对减少完工时间度量具有显著影响，其中对于所请求的有向无环图（DAG）应用，在异构计算系统上执行，在每对任务之间可能存在异构系统是一种使用多种计算资源的系统，这些资源具有不同的执行时间、速度和体系结构。在异构系统上为给定DAG的相关任务进行工作流调度以找到最小总执行时间是NP-Hard 问题（Abrishami 等人， 2013;Akbari等人，2017; Hosseini Shirvani，2015，2018）。为了解决云环境中的问题，已经做了大量的工作，以最小化在虚拟机上运行的DAG应用程序的完成时间，makespan。在已经针对异构计算资源上的排序问题提出的各种排序中，通常分类的方案是基于优先级的列表排 序 ， 诸 如 HEFT 、 RHEFT 和 PEFT （ Arabnejad 和 Barbosa ，2014;Topcuoglu等人，2002年; Thaman和Singh，2017年）和任务https://doi.org/10.1016/j.jksuci.2021.05.0111319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comR. NoorianTalouki，M. Hosseini Shirvani和H. 莫塔梅尼沙特国王大学学报4903.Σ2ð×þ þÞ.10月2 日d ×n 阿卢尔茨河基于复制的方案，但大多数效率较低。在工作流调度中，数据传输成本的降低对最小化云调度任务的完工时间大多数研究集中在最小化云调度的制作跨度没有使用任务复制来减少总运行时间上的数据传输时间所带来的开销。使用任务复制方法减少了传递前趋任务选择最佳的复制任务是获得合适时间表的关键如果不太重要的任务被复制，则虚拟机中的早期空闲时隙被占用。在网络中的异构虚拟机中进行计算和通信之间的权衡并且花费不同的时间量来执行相同的任务的一些提议已经在以下文献中被利用（Ahmad和Kwok，1998; Kruatrachue和Lewis，1987; Lopes Genez等人，2018年; Ranaweera和Agrawal，2000年）;提出的论文通过选择重复的任务来减少等待时间，同时在虚拟机之间传输数据以满足优先级约束。为了弥补这一差距，提高工作流调度的效率，提出了一种新的混合启发式调度算法本文的创新之处在于提出了一种新的基于乐观代价表OCTd和OCTu的任务优先级策略，使调度优先级更加合理，并利用了相应的任务复制技术。在这项研究中，所提出的方法已经实现使用MATLAB编程环境。实验结果表明，与现有的基于列表和启发式的调度方法相比，该方法在调度评价参数方面对工作流调度问题有一定的本文其余部分的结构如下。第二介绍相关工作。在第三节中，提出了应用和调度模型。第4节致力于数学问题的制定以及提出的启发式算法。第五节讨论了实验和数据分析。最后，第6节是结论和未来的工作方向。2. 相关作品列表调度器的主要目的是提供一个待调度任务的列表，并为每个任务分配优先级权重;然后，在列表排序器的一些典型类别是异构最早完成时间（HEFT）（Topcuoglu等人， 2002），其通过在向上方向上从退出任务到进入任务探索任务图来递归地计算每个任务的等级值，以及处理器上的关键路径（CPOP）方法（Topcuoglu等人，2002年）。在这一行中，基于标准偏差的任务调度算法（SDBATS）算法（Munir等人，2013）将研究中任务在可用处理器上的预期执行时间的标准偏差值应用为用于向任务分配优先级的突出特性。此外，可预测最早完成时间（PEFT）程序（Arabnejad和Barbosa，2014）根据处理乐观成本表（OCT）的测量来工作该预测表用于为任务分配等级，也用于处理器选择。在这问候，鲁棒的非均匀最早收敛时间（RHEFT）（Thaman and Singh，Nov. 2017）、具有改进的任务优先级（HSIP）的异构调度算法（Wang等人，2016）;使用任务重复的HEFT（HEFT-TD）（Lopes Genez等人，2018）和使用任务复制的Lookahead HEFT，Lookahead HEFT-TD（Lopes Genez等人，2018）是其他著名的启发式调度算法， 其中一 些 使用集群调度表1算法的定义算法时间复杂HEFT-U（Topcuoglu等人， 2002）On2ω pHEFT-D（Topcuoglu等人， 2002）On2ω pCPOP（Topcuoglu等人， 2002）On2ω pPEFT（Arabnejad and Barbosa，Mar. 2014）Ov2ω pRHEFT（塔曼和辛格，11月。 2017）Ov2ω pHSIP（Wang等人， 2016）Ov2ω pHEFT-TD（Lopes Genez等人， 2018）O rnrCLookahead-TD（Lopes Genez等人， 2018）O. r2×nnrcOCTuO r2×nnrc（Gkoutioudi和Karatza，10月10日） 2010）;（Mishra等人，2012 ） ; （ Amini 等 人 ， 2011 ） 和 基 于 任 务 复 制 的 调 度 技 术（Ranaweera和Agrawal，2000）;（Lopes Genez等人， 2018）;（Shin等人，2008; Sinnen等人，2011年; Tang等人， 2010年）。复制调度试图通过在多个虚拟机上运行一些前导任务此外，集群调度器将一堆任务打包在一个集群中，并在同一处理器上执行如果所选簇的大小与给定DAG的大小相比相当高，则调度性能下降到顺序调度。表1描述了比较算法在时间复杂度方面的比较视图。在该表中，符号r（或p）指示所使用的资源，并且符号n（或v）指示所使用的资源的数量。工作流中任务的BER，其中符号c表示每个任务的所有祖先的平均数，而不仅仅是直接祖先。本文提出了一种新的基于链表调度算法，该算法在最大完工时间和其他相关调度评价参数方面优于PEFT、RHEFT、HSIP、HEFT-TD、Lookahead-TD的时间复杂度提出OCTd 和OCTu 是O=2×n=0.3. 应用和调度模型为了更好地理解所提出的算法，介绍了各种模型。4. 应用模型可并行化的应用程序被建模为DAG。一个DAG有不同的节点;每个节点都用于从整体上进行所需数量的计算。此外，DAG具有不同的弧，每个弧用于示出每对节点之间的现有依赖性，并且用于呈现两个依赖任务之间的数据通信成本的平均量，此外，每个DAG都有两个唯一的任务入口和出口;前者没有任何前任节点，而后者没有任何后继节点。请注意，在异构系统中，由于底层处理器速度不同，每个任务的执行时间也不同。本文的益处使用来自四个真实世界科学工作流应用的合成数据集进行评估，例如分子（Xu et al.，2014年）;LU-样（Hosseini Shirvani，2019年）; FFT（Hosseini Shirvani，2019年）和Mon- tage（Xu等人，2014年，在图中显示。1 .一、4.1. 调度模型本节解释任务图应用程序和任务分配到虚拟机的机制。所研究的系统配备了一组m个异构虚拟R. NoorianTalouki，M. Hosseini Shirvani和H. 莫塔梅尼沙特国王大学学报4904ð Þ图1.一、 两个真实世界的科学工作流程应用（a）分子（Xu等人， 2014）（b））LU样（Hosseini Shirvani，2019）（c）FFT（Hosseini Shirvani，2019）（d）蒙太奇（Xu等人， 2014年）。通过高速网络互连的机器虚拟机的异构性被认为是根据他们的速度和架构。列表调度器是分布式系统中因此，本文采用了列表调度策略，并对其进行了定制，提高了调度效率。异构最早完成时间（HEFT ）是著名的列表调度器之一它是由 Topcuoglu 等人首先（Topcuoglu等人， 2002年）。它用于在有限数量的异构并行机上进行处理系统. HEFT应用两个重要功能：表2使用的符号的名称。象征意义T应用程序中的任务集E用于任务之间的优先约束的边的集合ti给定DAG应用程序中的第i个任务关键前置任务TaskList任务列表和每个任务任务ti中的指令数最早结束时间（EFT）和最早开始时间（EST）。在副本我测试入口应用程序中第i个任务的新副本没有前置任务的入口第一步，它提供一个有序任务列表，第二步，它挑选高优先级任务并将其分配到快速可用的VM上。为了更好地跟踪论文，表2中列出了所用的术语。4.2. 该算法在本节中，我们将介绍问题公式化，根据乐观成本表向下（OCTd）和乐观成本表向上（OCTu）的新任务优先级策略，以及复制算法。4.3. 问题公式化函数ETti;vmkk由等式（1）计算（1）返回任务ti在异构虚拟机vmk中的任何一个上的执行时间。此外，tion的平均执行时间texit没有后继任务的退出eti;tj从子任务ti到tj的有向边vmList虚拟机vmkftg分配给vmk的任务集ETti;vmk任务ti在vmkES上的执行时间vmkVMk的执行速度平均执行时间EDRTti;vmk任务ti的最早数据接收时间（任务ti接收所有前置数据最早ESTti;vmk子任务t ionvmkEFTti;vmk子任务tionvmkAFTt i;v m k子任务tionv mk的最早开始时间ti on v m k A FTti;vmk子任务tionvmk的实际完成时间t ionSucctitip redtitit根据OCTd乐观成本表对分配给任务ti的值进行排名根据OCTu乐观成本表对分配给任务ti的值进行排名makespan总执行时间不R. NoorianTalouki，M. Hosseini Shirvani和H. 莫塔梅尼沙特国王大学学报4905ð Þ第一章ðÞnO>hv联系我们（。- 是的Σ我××K我K我K¼EDRT ti;vmk;其中k我公司简介>ESvml2vmList系统中的所有可用资源由等式中的ET ti计算。 （二）、4.4. 任务优先策略ETti;vmk尺寸tET t8k2vmListETti;vmkjvmListjð1Þð2Þ任务优先级排序阶段旨在提高任务的优先级根据他们的优先战略。一些论文，如（Topcuoglu et al.，2002）;（Lopes Genez等人，2018）使用向上和向下排序的任务优先级顺序来区分任务执行的优先级。乐观成本表向下（OCTd）和乐观成本表向上（OCTu）是两个重要的表，通过等式（1）计算的函数EDRT ti;vmk（3）返回在vmk上从其接收器接收到所有先决条件数据的最早时间。注意，在ti的前驱任务集中，任务tj是检查以指定ti的前导任务是原始的还是复制的，因为DAG中的每个任务都可以是复制的候选任务。此外，如果任务ti和它的前驱任务tj在同一虚拟机上执行，则数据传输时间E。tj;ti在等式中被认为是零。（三）、>8>EDRTti;vmk¼ 最大0B@Bmin.EF T.tj;vmle。tj;tiC1CAJpred优先任务。OCTd由等式向下创建（8）从入口任务开始向下到出口任务;为了计算OCTd，必须计算OCTd的前导、当前任务执行时间和通信成本等所有参数实际上，该函数返回任务执行时间的估计值。以同样的方式，OCTu是用Eq向上创建的（10）从退出任务开始;为了计算OCTu，必须计算所有参数，如后继者OCTu、后继者任务执行时间和通信成本此函数还返回每个任务的另一个估计执行时间此外，Eq.（9）Eq.（11）计算其估计的平均乐观成本值，8tj 2Pred tti t8t2不>预复制关于底层VM的数量这些方程是在算法1中使用。：set：. e.tj;ti<$$>0ifvmk<$vmlð3Þ8>OCTd.不进入; vmk 1/4ET。不进入; vmk在Eq.（3）在原稿和副本之间，选择返回最小值的一个，因为原稿和副本都是>OCTdti;vmktMaxPred2Pred 18Þ和复制任务具有相同的应用。因此，外部Max确定EDRT（.）'的值，因为必须确定已故前任的最后时间。为了计算最早开始时间，Esttti;vmkt i，等式（4）使用。在将ti调度到vmk上之前，minfOCT dtPre d;vmletPre d;tieti;vmkg：set：fetPred;ti<$0jvmk<$vmlg我们需要检查ti的复制是否已经被调度在排名第四 平均年龄10-18岁;平均年龄10-19岁vmk. 的EQ。（4）找到虚拟机上任务t i的最早开始时间，其是虚拟机的可用时间与EDRT t i之间的最大值;OCT d我8个十月I kvmk2vmList;vm=0（。Σ出口k>EST t条目;vmk1/4ti/4t输入ð4Þ>OCT最大值EST不确定;vmk不确定;最大值不确定;EDRT不确定;否则，vmk不确定为了计算最早完成时间EFTt i;vm k，等式（五）米ml2vmListtSucc2成功2成功fOCTutSucc;vmleti;tSuccetSucc;vml gi被利用。最早完成时间是通过将虚拟机上当前任务ti的执行时间vmk与虚拟机上当前任务ti的最早开始时间ESTti;vmk相加来计算的。请注意，>：set：feti;tSuccc0jvmkvmlgð10Þ一台机器由同一台机器上该入口OCTuti均值mk2vmList ðOCTuðti;vmkÞÞ ð11ÞEFT tentry;vmk ¼ET tentry;vmk 我不是 1/4吨进口EFTt;vmt;vmETt;vmotherwiseð5Þ算法1专用于提供有希望的有序任务列表。首先，算法1计算OCTd秩序表，对OCTd表进行排序，这是所提出的启发式表的基础当前任务的实际完成时间AFT=ti;vmk=当前任务ti可以完成的最小时间，vmk是返回最小完成时间的虚拟机。AFTti;vmkfEF Tti;vmkjk：vmk2vm列表，以便获得最小值，调度员。请记住，OCTd表是一个二维矩阵（m n），RankOCTd是一个（n1）列向量，其中参数m和n分别是任务和底层VM的数量。在算法1的每次迭代中，它找到OCTd表中具有最小值的行号Rj，而不管VM列如何;然后，它选择放置在ti，t的关键前置任务cp;i，是前置任务Ran kOCT d½Rj]. 然后，将此任务添加到下一个空位置中。从OCTdOrder_List的开头开始的（n×1）列它的数据比其他优先排序的任务更晚地传递到当前任务此时，我们可以根据公式7计算关键前置任务。8>set：fetPred;ti<$0;其中k<$Lg算法1，它返回OCTdOrder_List，保证任务之间的优先约束。ð7ÞR. NoorianTalouki，M. Hosseini Shirvani和H. 莫塔梅尼沙特国王大学学报4906g×××gðÞðÞð Þ ðÞ算法1. OCTd RankOrder输入：G：给定的任务DAGvmk：虚拟机; /*k-vmList中的第k个vm *//* 每个vmk都有一个数据结构数组，该数组具有startandend fields*/输出：7.列表←根据任务在RankOCTu列表中的值，按降序对Temp列表中的任务进行排序8.将Temp List添加到OCTuOrder List的开头OCTuOrderList Temp List;OCTuOrder List9.从OCTu表中删除相应的行10. end while11. 返回OCTuOrder列表12. 结束{OCTu RankOrder}OCTdOrder列表：根据OCTd RankOrder的任务顺序算法1. 开始2. 创建OCTd表，并根据等式对所有任务的OCTd列表进行（8）Eq. （9）分别3. 创建新的临时列表4. 将临时列表设置为空列表5. 当OCTd表不为空时，6. 在OCTd表中查找具有最小值的单元格，并在Temp List中设置等效任务7. 临时列表←根据任务在RankOCTd列表中的值，按升序对临时列表8. 添加临时列表到OCTdOrder List;OCTdOrder ListOCTdOrder List;Temp List的末尾9. 从OCTd表中删除相应的行10. end while11. 返回OCTdOrder列表12. 结束{OCTu RankOrder}此外，算法2专用于提供另一个有希望的有序任务列表。算法2首先计算OCTu排序表和RankOCTu列表，这是启发式列表调度器的基础。请记住，OCTu表是一个二维矩阵（m n），RankOCTu是一个（n 1）列向量，其中参数m和n分别是任务和底层VM的数量。在算法2的每次迭代中，它找到具有最小值的OCTu表的行号Rj，而不管VM列;然后，它选择被放置在Ran[kOCTu[1/2Rj]中的任务tj。然后，将此任务添加到OCTuOrder_List的从末尾到开头的下一个空位置，OCTuOrder_List是一个（n 1）列向量。如果多个任务在不同行中具有最小值，则从RankOCTu列表中选择相应的任 务 ， 并 根 据 RankOCTd 中 这 些 任 务 的 降 序 排 序 值 将 其 添 加 到OCTuOrder_List列表中;在这样做之后，算法从OCTu表中删除相应的行。在算法2结束时，它返回OCTuOrder_List，保证任务之间的优先约束。算法2. OCTu排名输入：G：给定的任务DAG;vmk：虚拟机; /*k-vmList中的第k个vm *//* 每个vmk都有一个数据结构数组，该数组具有startandend fields*/输出：OCTuOrder列表：根据OCTu RankOrder的任务顺序算法1. 开始2. 创建OCTu表，并根据等式对所有任务的OCTu进行排名（10）Eq. （11）分别3. 创建新的临时列表4. 将临时列表设置为空列表5. 当OCTu表不为空时，6. 在OCTu表中查找具有最小值的单元格，并在Temp List中设置等效任务5. 任务复制算法为了减少两个相关任务之间的通信开销，可以使用复制方法它源于这样一个想法，即在同一台机器上运行的相关任务具有零通信成本。为此，本文使用了前置任务的复制一些现有的研究集中在工作流调度上，使用任务复制技术通过减少任务间通信开销（数据传输）来最小化最大完工时间值（Lopes Genez等人，2018）;（Munir等人，2013）;使用任务复制来提高异构虚拟机上的任务调度性能的一些其他算法在（Wang等人，2016）;（Tang等人，2010年）。在HSIP方法中（Wang例如， 2016），为了避免开销问题，只有入口任务被复制，但是在我们的文章中，每个任务都可以是复制算法的候选者。在算法3中，变量STATE是逐渐创建的调度方案;这在开始时用空值初始化。如果前置任务的重复性得到改善，当前任务的最早完成时间t i在下一集，即它提高了EFT t i;vm k值;然后，算法更新STATE调度方案的这种变化与重复的前趋任务相结合。在该算法中，在复制当前任务的前导之前，必须检查复制是否提高了当前任务EFT是否会出现在下一集。事实上，它考虑了以前对未来的影响。首先，通过计算EDRT ti;vmk即在虚拟机vmk上执行当前任务ti所需的所有数据被传送的最早时间，确定该最早时间;然后，计算最早开始时间EFTti;vmk、最早结束时间EFT ti;vmk和实际结束时间AFT ti;vmk计算基本STATE 调度方案的最大完工时间。此调度长度保存在MaxLength变量中，必须通过合并前导任务的复制将MaxLength变量与新调度长度的最大完工时间在算法3的第2行中，它根据算法1中的OCTd RankOrder或算法2中的OCTu Rank-kOrder在TaskList变量中创建优先级任务列表第3行使用空值来调度STATE方案，在该方案中，STATE方案逐渐完成算法3的主循环在第4行和第23行之间;当TaskList中有一个未调度的任务时，它会迭代。选择有序表中的高优先级任务，并将其调度到以最小EFT值作为其AFT的STATE调度方案。如果当前任务至少有一个第8行检查的前导任务，则当前任务的AFT被认为是当前原始调度方案的完工时间值，保存在MaxLength变量中。然后，经由等式7确定与当前任务ti相关联的关键前驱任务tcp，i这个关键任务tcp;i通过基于插入的策略在与 最 近 分 配 了 任 务 ti 的 VM 相 关 联 的 时 隙 时 间 之 一 上 被 复 制（Hosseini Shirvani和Talouki，2021）。然后，将该重复任务用NewSTATE调度方案调度，并计算其AFT，然后将后继任务ti也用NewSTATE调度R. NoorianTalouki，M. Hosseini Shirvani和H. 莫塔梅尼沙特国王大学学报4907pred←←←ð ðÞÞ.EFTt;vm的最小值.K.14岁。根据方程计算AFT t ; vm。（6）kpred←predð ðÞÞ我K并计算其AFT值。这个量被认为是新状态调度方案的最大完工时间值，并保存在NewMaxLength变量中。如果这种变化的作品，当前的状态调度方案是由新的状态调度方案取代。换句话说，如果NewMaxLength小于MaxLength，这意味着复制技术有效。为了获得更好的效果，该算法对其他可用槽与Vmk相关联的时间，这在第11-20行之间完成。后确定最适合于托管关键任务的时隙时间，这隐含地减少了调度方案的最大完工时间，重复的任务t_copy和当前任务t_i被调度，然后，将当前任务ti从TaskList中移除。之后，算法3返回到第4行的while循环，以调查另一个未调度的高优先级任务最后，算法3返回有效的STATE调度方案。算法3：任务复制输入：G：给定的任务DAG;vmk：虚拟机; /*k-vmList中的第k个vm *//* 每个vmk都有一个数据结构数组，该数组具有startandend fields*/输出：STATE：一种高效的调度（解决方案）1. 开始2. 任务列表根据OCTd RankOrder算法1或OCTu RankOrder算法23. STATE空调度方案;此方案用于逐步进行调度4. 当TaskList上存在未计划的任务时，5.ti←从任务列表6.STATE在虚拟机上以最小最早完成时间调度任务t i，（六）7.根据公式计算AFTt;vmt。（六）表3每个任务的执行时间。图二. 应用程序DAG。8.ifPredti-9.MaxLength= Calculate min EFT t i;vm k这就是调度基本STATE方案的改进10.查找关键前置任务tcp;i2Predti基于关于等式711.而vmk中的每个时隙时间do12.t copy←在v m k的一个时隙上使用基于插入的策略复 制 任 务 t cp ; i （ Hosseini Shirvani 和 Talouki ，2021）。13.NEW STATE←在每个vmk上安排t副本，复制预览复制预览15.计划任务t i 新国家和计算基于Eq. （六）、16.NewMaxLength= 计算最小 EFT ti;vmk ，这是NEWSTATE方案的组成部分17.如果NewMaxLength18.新州州;19.end if20.end while21.end if22.从TaskList的开头删除任务ti23. end while24. 返回调度状态方案25. 结束{TaskDuplication}表4可用虚拟机、其执行时间和排名值。任务OCTu RankOCTu OCTd RankOCTdvm1vm2vm3vm1vm1vm1T164688672.6622213626.33T24239424144395445.66T32741433754487960.33T442395043.6629314033.33T52837283151486956T642394441.6648385246T71316221768739478.33T813163320.6672627971的t913162016.3366697770.66T100000858911295.335.1. 说明性示例为了评估所提出的模型的有效性，如图中所示使用样本DAG。2、逐步完善对原材料的管理，提出战略。该图由t1到t10的10个任务组成，弧。相关任务之间的数据传输时间由每个弧上方的数字显示。该说明性示例使用3个异构虚拟机，说明性示例的每个任务的执行时间值在表3中给出。最后一任务执行时间ETðtiÞvm1vm2vm3T122213626.33T222181819.33T332274334T471047T529273530.33T626172422.33T714253023T829233629.33的t91521814.67T1013163320.67R. NoorianTalouki，M. Hosseini Shirvani和H. 莫塔梅尼沙特国王大学学报4908]表3的列值表示该平台上每个任务的平均执行时间两 个 2 维 矩 阵 乐 观 成 本 表 向 上 （ OCTu ） 和 乐 观 成 本 表 向 下（OCTd）值以及两个列向量RankOCTu和RankOCTu列表经由等式（1）计算：（8），Eq. （9），Eq. （10），Eq. （11）分别。在表4中使用上述值来生成两个有希望的优先级排序的任务列表例如，为了产生OCTu有序列表，选择OCTu表中具有最小值的行一开始，选择第10行，因为它的值为零，表5任务优先级与不同的算法。文学中的启发法任务优先级排序完工时间RankU（Topcuoglu等人，（ 2002年）t1; t5; t6; t2; t4; t3; t8; t7; t9;t10133RankD（Topcuoglu等人，（ 2002年）t1; t6; t5; t2; t4; t3; t8; t7; t9;t10136PEFT（阿拉伯内贾德和巴博萨，t1; t4; t6; t2; t3; t5; t8; t7; t9;t10132Mar. 2014年度）RHEFT（塔曼和辛格，11月。t1; t4; t5; t6; t2; t3; t8; t7; t9;t10143（2017年）HSIP（Wang等人，（ 2016年）t1; t3; t6; t2; t5; t4; t8; t7; t9;t10125HEFT TD（Lopes Genez等人，t1; t5; t6; t2; t4; t3; t8; t7; t9;t101432018年）到VM。然后，将第10个任务添加到最终列表的末尾，该列表逐轮逐渐创建。此时，从OCTu表中删除第10行。在第二轮中，在第7、8和9行中找到最小值13。因为它们具有相同的值，所以它们基于它们在秩OCTu向量中的值按照降序进行排序;然后子列表[t8t7t9]被添加到最终列表的末尾，因为它们在秩OCTu中分别具有20.66、17和16.33。因此，任务t7、t8和t9从OCTu表中删除。在第三轮，值27是仅在与以下相关的第3行中找到的最小值：t3.在第四轮中，选择具有唯一最小值28的任务t5在第五轮中，在t2、t4和t6中找到最小值42，但是将子列表[t4t6t2]添加到因为任务t2、t4和t6分别有41、43.66和RankOCTu向量中的41.66个值。最后，将任务t1添加到最终列表的顶部。因此，最终的OCTu有序列表是[t1t4t6t2t5t3t8t7t9t10]。为了产生另一种有希望的表--OCTd有序表，在每一轮中选择OCTd表中具有最小值的行，但与OCTd方法相比，唯一的区别在于子表的排序和添加方式。排序是按照升序进行的，插入是从最终列表的末尾开始的因此，所有任务Lookahead-TD（Lopes Genez等人， 2018年）t1;t5; t6; t2; t4; t3; t8; t7; t9; t10 133被选中并添加到列表的前面。对于该说明性示例，最终OCTd有序列表是[t1t4t6t2t5t3t8t9t7t10]。建议的OCTu t1;t 4;t 6;t 2;t 5;t 3;t 8;t 7;t 9;t 10 122建议的OCTd t1;t 4;t 6;t 2;t 5;t 3;t 8;t 9;t 7;t 10 122对于这个说明性示例，表5显示了任务优先级顺序列表和最后完成时间与不同的以前的调度算法-图三. 输出说明性示例。aR. NoorianTalouki，M. Hosseini Shirvani和H. 莫塔梅尼沙特国王大学学报4909-Rithms正如该表所示，我们的算法在最大完工时间值方面优于其他算法。图3示出了我们的新启发式与文献中提出的几种算法之间的比较。如图3所示，我们提出的算法复制每个候选任务，这是有益的，而其他方法只复制输入任务。例如，所提出的OCTd和OCTu在适当的时隙时间内接近重复任务t1和t4 最后的结果证明了它的有效性。5.2. 实验数据分析本节介绍了数据分析，以更好地理解所建议的启发式算法相对于其他比较先进的算法在突出调度参数方面的性能我们的新启发式算法与几个提出的算法之间的比较是根据一些突出的调度参数，如完工时间，调度长度比（SLR），加速比，效能为了在不同情况下评估所提出的算法，使用通信计算比（CCR）参数来产生与众所周知的科学工作流相关的不同数据集，诸如分子、类LU、FFT和蒙太奇DAG。最终评估基于与不同DAG相关的不同CCR5.3. 完工时间makespan参数称为总执行时间。最大完工时间是最重要的调度准则之一，可以用方程计算。（十二）、最大完工时间最小完工时间最大完工时间最小完工时间最大完工时间图图4描述了在CCR值确定的不同条件下，根据最大完工时间的比较经济学的比较。在这一行中，表6说明了不同算法的完工时间比较精确值。表6的值证明了见图4。 比较经济学之间的最大限度的比较表6不同启发式算法的完工时间比较数据集CCR算法完工时间值RankU RankD PEFT RHEFT HSIP HEFT TD LOOKAHEAD TD OCTuOCTd分子0.5 74 70 57 67 64 59 57 53 511.0 81 66 64 79 71 68 64 645 87 74 69 90 75 67 69 67 6110 93 90 86 96 76 79 74 73 67陆如0.51351371341451271441351231.0 140 154 136 147 129 145 137 124 1245 141 151 138 149 131 146 139 125 12510 142 158 140 151 133 147 141 126 126FFT0.5 27 27 30 30 27 26 27 25 261.0 33 31 31 31 32 32 31 295 37 34 36 34 35 35 37 34 3110 41 38 40 37 37 40 36 36 37蒙太奇0.5 38 35 34 38 40 33 38 34 301.0 40 46 38 40 50 34 37 33 345 43 48 38 43 43 42 37 34 3610 46 50 39 46 45 37 38 37 36R. NoorianTalouki，M. Hosseini Shirvani和H. 莫塔梅尼沙特国王大学学报表49104910-ðÞ与启发式算法相关的相对偏差百分比（RPD）。数据集CCR相对百分比偏差（RPD）RankU RankD PEFT RHEFT HSIP HEFT-TD LOOKAHEAD-TD分子0.5 31% 27% 11% 24% 20% 14% 11%1.0 23% 6% 3% 22% 13% 9% 3%5 30% 18% 12% 32% 19% 9% 12%10 28% 26% 22% 30% 12% 15% 9%陆喜欢0.59%10%8%15%3%15%9%1.0 11% 19% 9% 16% 4% 14% 9%5 11% 17% 9% 16% 5% 14%10 11% 20% 10% 17% 5% 14% 11%FFT0.5 7% 7% 17% 17% 7% 4% 7%1.0 12% 6% 6% 6% 9% 9%5 16% 9% 14% 9% 11% 11%10 12% 5% 10% 3% 3% 1