文丨五年宝

编辑丨五年宝

前言

云计算采用“按使用付费”系统，客户无需完全了解分发策略和托管细节即可访问云服务，而这提供了对共享资产池，比如说存储空间、计算服务器和Web设施的全局按需访问。

从而减少了企业采购和确定逻辑结果的时间，客户可以毫无压力地稳定地访问这些资产，并且无需与设施提供商沟通，云基础设施的目标是为动态应用程序提供易于使用的工作区。

当各种计算机硬件与软件包服务集成时可以获得工作空间，这些设施允许客户通过其执行、可访问性和服务质量（QoS）需求的指示来在网络空间中传输他们的提交内容。

由于此类提交的配置、部署和安排要求不同，资产管理和任务调度的方法成为云框架效率和有效性发展的基础，在一些分布式框架中，所有作业都可以想象为执行其中的各种任务。

这些任务分为依赖任务和独立任务，尽管独立任务可以由多个虚拟机(VM)同时执行，但相关任务必须通过实现其优先级关系来进行规划。

这也可以表示为有向无环图(DAG)，其中图顶点或节点表示任务，边表示任务之间的链接，必须按照计划顺序执行具有优先级限制的任务，从而缩短计划完工时间。

任务调研

任务调度问题可以分为两大类：确定性调度和非确定性调度，确定性调度又分为基于启发式的和基于引导随机搜索（GRSB）的。

为了确定性任务调度也称为静态调度，GRSB算法比基于启发式的调度算法成本更高，因为该算法需要更多迭代来生成增强的调度。

除此之外，基于启发式的算法可以在创纪录的时间内提供近似解决方案，它们可以归类为与重复相关的、基于聚类和基于列表等。

基于重复的启发式方法具有较高的时间复杂度，而这类聚类的启发式方法适用于同构框架比较简单，这也是研究人员考虑了基于列表的启发式方法后发现的结论。

发现它们在缩短完工时间方面缩短了持续时间和效率，而它们在任务调度的两个主要阶段工作，在第一阶段，对各个任务进行排名计算，然后按降序排列。

在第二阶段，他们在可用机器上安排具有最高排名值的任务，而异构则是最早完成时间（HEFT），过程由于其高性能权衡和低成本而在异构计算的同行中最受欢迎。

研究人员还设计并提出了HEFT算法的三个修改版本，用于排名计算和处理器选择，并减少任务调度的持续时间。

最后他们提出了异构机器上任务调度的挑战以及云框架相关的功能，以便通过包含任务之间的依赖关系来有效管理可用虚拟机上的指定任务。

针对所提出的算法与基本HEFT算法，以及在实际应用中任意创建DAG上的AVCT（平均计算成本）算法进行了分析和比较。

该方法的新颖性在于HEFT算法的两个阶段采用不同的方法，在第一阶段（排名生成），他们需要执行几种方法来计算排名。

在第二阶段，他们需要改变如何选择空槽进行任务调度，而这些更改不会给主要HEFT算法增加任何成本，并且会缩短虚拟机工作流提交的完成时间。

从研究人员进行的计算分析和实验中，可以观察到基本HEFT算法（AVCT方法）和他们提出的修改版本MXCT、MNCT和AVBS（平均计算成本和最佳空位）。

关于生成的进度计划完工时间的研究得到突破，这也意味着所使用的方案会影响时间表的长度，他们还观察到，使用平均值方案进行排名计算和选择第一个空槽并不总是最佳选择。

研究人员的研究结果表明，在缩短虚拟机上运行的工作流问题的调度长度方面，这根他们提出的改进版本比基本HEFT算法表现的更好。

多处理器任务调度

在这之前，不同的研究人员提出了几种列表调度程序来解决任务调度问题，而HEFT算法使用平均通信和计算成本来估计任务的上升排名值。

基于标准差的任务调度（SDBATS），使用传输和计算费用的标准差来近似上升的排名值，处理器上的关键路径(CPOP)添加后代和上升排名值以创建重要的跟踪和优先列。

在DAG的每个阶段，性能有效任务调度(PETS)包括平均计算成本、数据传输和接收成本以固定任务的排名值。

基于复制的异构最早完成时间（HEFD），使用任务方差作为异构性的特征来近似任务之间的传输和计算成本。

预测最早完成时间（PEFT）是基于前瞻技术创建的，并通过乐观成本值表（OCT）的计算来近似后代任务，而OCT是一个二维数组，其列和行分别表示处理器和任务的数量。

OCT中的每个元素，最短路径的最优值t后代任务到离开节点，一部分机器被提名执行任务，所有这些算法计算都依赖于标准偏差或可访问机器上任务权重的平均值。

但它们不包括框架异质性，因为最近的工作展示了标准偏差，包括现有机器上的任务和异构性，从研究结果中分析了各种任务调度算法及其局限性、工具和参数。

研究人员相信，通过使用基本HEFT算法的三个版本可以提高HEFT算法的效率，而研究结果提出了第一阶段（排名计算）的两种方案，以及一种不同的空时隙选择方法。

研究人员又检查了每个版本生成的时间表完工时间，并将最小长度完工时间作为结果，尽管它稍微增加了算法的成本，但它是时间复杂度和性能之间的权衡。

最后通过研究人员的评估表明，所提出的版本在提高效率和缩短进度长度方面产生了高价值的进度表。

HEFT算法

HEFT算法旨在将DAG任务调度到异构处理器中，而HEFT过程有两个基本阶段：排名生成和处理器选择阶段。

在第一阶段，HEFT对所有任务进行排名计算，并根据排名值的降序排列它们的优先级，它首先根据平均通信和计算成本为每个DAG节点和边分配权重以进行排名计算。

在第二阶段，HEFT根据任务的优先级值选择任务，并将每个指定的任务调度到最合适的处理器上，这可以减少任务的调度长度。

如果遵守优先级约束，HEFT还会将任务安排在处理器上两个先前计划的任务之间的空槽中，HEFT算法也会在处理器上寻找空槽，直到找到可以承担所选任务的计算成本的空槽。

而HEFT过程利用平均通信和计算成本，作为DAG权重来计算排名和选择处理器，任务调度始终考虑第一个空槽。

在某些特定的情况下，计算和选择第一个空槽的平均成本可能不是一个好的解决方案，直到研究的示例DAG 后。

研究结果显示了三个不同VM上每个任务的可能执行成本，这也意味着样本DAG的边缘标有平均通信成本。

在这些实验中，如果使用所有三个VM的平均计算成本（如基本HEFT中所示）来确定任务的优先级，则调度顺序将为{T}S_{1}，调度长度将为98。

研究人员的成果充分说明了这一点，假设优先级的分配是使用可以执行任务的三个VM上的计算成本的最优值来完成的。

相比之下，小于基本HEFT算法获得的调度长度，而类似地结果，通过使用任务可以在其上运行的三个VM上的计算成本的最小值来分配优先级。

最后会发现任务调度长度和顺序将与基本HEFT算法中发现的相同，这和VM的计算成本类似，基本上都属于按照最优分配优先级。

相反，如果处理器选择阶段改变，则获得的调度长度可能改变，在这里，排名的计算是使用平均计算成本值来完成的。

在上文提到的示例中，如果研究人员选择一个任务完成时间最短的空槽而不是初始槽，则调度长度将下降到89，因为现在已调度任务{T}_{5} 在VM 2上，而不是VM 1。

最后研究人员发现，排名计算的计算值的平均成本和选择第一个空槽来调度任务并不是最佳选择，这也意味着获得的时间表长度可能会改变。

云环境提出的方法

很快研究人员又提出了基本HEFT算法的修改版本，以获得云环境中任务安排挑战的改进结果。

有充分的实验可以证明，在第一阶段中，他们会执行不同的方法，而在第二阶段中，他们又会改变任务调度的空槽选择模式。

与基本HEFT算法相比，这些修改不会产生任何额外成本，这也让研究在每个阶段提出的改变解释十分明确。

在这个阶段，研究人员又提出了一种新颖的方法来确定所选任务的空槽，当任务的所有组先将所需的输入数据传输到该资源时，就会开始在资源上为任务搜索适当的空槽。

而实验的的计算成本，没有超过其中任何一个所选任务完成的时间，当完成后研究人员又 给出了HEFT的完整算法。

结果

在这次的研究中，研究人员创建了一个补充基本HEFT算法的系统，并改进了任务进程的处理器选择和优先级排序。

输入系统的输入包括通信成本、可能的执行成本矩阵、显示依赖关系的DAG以及虚拟机和任务的数量。

为了评估我们算法的性能，他们生成了各种调度问题，并尝试使用HEFT算法的修改版本以及基本HEFT算法来解决它们。

当研究人员设计了一个自动化系统来处理不同规模的调度问题，就会发现这样做是为了防止在提供不同参数的值时出现偏颇，最后的系统将参数分配给适当范围内的随机值。

同样的是，其余67%的问题，与AVCT方法相比，MNCT方法在27%的情况下提供了相等的进度长度，在40%的情况下提供了更好的进度长度。

在云计算中，可扩展的资源通过互联网作为服务提供给客户端，这也意味着云服务提供商在云计算架构中需要处理更多的客户。

所以任务调度是建立功能高效的云计算环境的最大挑战之一，在上述文中提到的研究方案，他们还提出了不同版本的基于启发式算法的异构最早完成时间。

这些算法在云计算环境中，进行任务调度和资源分配，最后通过将科研人员提出的方法与其他框架在计划长度方面进行比较。

实验结束后，可以明显发现新提出的方法表现更好，根据观察，通过从每种方法的时间表中选择最佳结果，可以提高原始HEFT算法的效率。

虽然这可能导致算法成本较高，但这是成本和性能之间的权衡，在这样的情况下，可以进一步考虑基于自然启发的优化算法的调度，以在云环境中更有效地进行任务调度。