【论文】略读笔记63-前沿-全局虚拟存储下虚机复用的工作流资源调度

📖《Cost-Efficient Workflow Scheduling Algorithm for Applications With Deadline Constraint on Heterogeneous Clouds》

2022 年发表于 CCF-A 类期刊 TPDS。

🎯需求

• 近年来，越来越多的大规模数据处理和计算工作流应用在异构云上运行。

  • 如今，越来越多的大规模数据处理和计算应用，如数据挖掘、基因组测序和大数据分析，都是以工作流的形式进行组装和建模的，工作流由许多受优先级限制的相互依存的任务组成。这些应用通常在集群和网格等高性能计算平台上处理。
  • 然而，这些平台不仅建设和维护成本高昂，而且不方便按需付费。因此，许多工作流应用，如 CyberShake、Epigenomics、LIGO、Montage 和 SIPHT，已经部署或逐步迁移到商业云。
  • 云计算被定义为以 “即用即付 ”模式提供 IT 基础设施和应用服务。在这样一个平台上，有多种类型的异构虚拟机（VM），它们具有不同的计算特性（内核、内存、存储和 I/O 带宽），可满足各种应用的相应需求。这种云按需服务模式为租用虚拟机类型提供了便利和灵活的计费方式，有利于云终端用户。成功的商业云系统包括 Amazon EC2、Google App Engine等。

• 这类具有优先级限制任务的云应用通常都有截止日期限制，其调度是云提供商面临的一个基本问题。此外，基于云计费期的工作流执行成本最小化也是云面临的一个复杂而具有挑战性的问题。

  • 一般来说，云用户根据其应用程序的需求租用或发布虚拟机（VM）。商业云提供商根据提供的时间段（如分钟或小时）收费，价格基于其处理能力（如内核）、存储量和其他因素，这被称为按使用付费模式。
    • 在这种计费模式下，分配给大容量虚拟机类型的任务通常需要较短的执行时间和较高的费用。
  • 此外，任务执行成本不是根据其实际执行时间计算的，而是根据云用户租用的时间段计算的。
  • 因此，对于云用户来说，任务或工作流租用成本最小化是一个关键问题，而不是优化工作流性能这一传统目标。解决这一问题的有效方法是将工作流的任务调度到异构云，同时考虑它们的租用期。

  🚧现状

• 云工作流调度策略将受优先级限制的任务分配到虚拟机（VM）上，以获得最佳执行成本或最小调度长度（makespan）。由于工作流应用受到截止日期的限制，这个问题变得更加复杂。

  • 然而，工作流计划任务租用计费期的一部分可被同一应用的任务重复使用，而且不同的任务开始时间点会导致不同的租用计费期。例如，假设用户的任务实际执行时间为 1.1 个计费周期，但却租用了 2 个计费周期。剩余的 0.9 个计费周期可被同一用户的另一个只需 0.75 个计费周期的任务重复使用，用户可节省一个计费周期的费用。
  • 因此，分配和租用适当的计费时段以节省执行成本是可取的。

• 此外，许多工作流应用程序都是数据密集型的，其数据文件大小从 2 GB（SIPHT）到超过 200 TB（CyberShake）不等。大多数云系统都有一个全局虚拟存储系统，如亚马逊 S3。因此，工作流任务和 I/O 之间的数据通信也是全局虚拟存储系统面临的一个挑战。

• 此外，云用户通常希望他们的应用能在截止日期前完成，这也是各种云应用中普遍考虑的重要问题。

🛩创新

• 在本研究中，受工作流任务数据 I/O、截止日期限制调度和共享云计费期等挑战的启发，我们重点研究了有效调度截止日期限制的云工作流任务以实现最优财务成本和系统性能的问题。

  • 为实现这一目标，我们首先根据具有全局存储系统的云，将工作流应用建模为 I/O 数据感知有向无环图（DDAG）。
  • 然后，我们以最小执行财务成本为目标，用数学方法阐述了这个有截止日期限制的工作流调度问题。我们还从多维多选包问题中推导出该问题的时间复杂度为 NP-hard。
  • 第三，我们提出了一种启发式低成本任务调度策略，称为 CETSS，它包括工作流 DDAG 模型构建、任务子截止日期初始化、贪婪工作流调度算法和任务调整方法。贪婪工作流调度算法主要包括动态任务租用计费期共享方法和非计划任务子期限放松技术。

• 我们的创新点总结如下：

  • 1）首先，我们考虑了云系统的文件数据 I/O（具有全局虚拟存储系统），并将经典工作流应用 DAG 扩展为 I/O 数据感知有向无环图（DDAG）模型。
  • 2）其次，我们从数学上阐述了具有成本效益、截止日期和优先级限制的工作流任务调度问题。通过对多维多选包问题的推导，证明了该问题的 NP-硬时间复杂性。
  • 3）第三，我们利用扩展的 SKOPE 代码骨架框架分析并构建了工作流应用 DDAG 模型。我们还引入了云异构因子来实现标准虚拟机，用于初始化每个任务的子死线。
  • 4）第四，我们提出了一种启发式低成本高效任务调度策略（CETSS），它由云应用 DDAG 模型、任务子截止日期初始化、贪婪工作流调度算法和任务调整方法四部分组成。贪婪调度算法主要包括动态任务租用计费期共享方法和非计划任务子期限放松技术。
  • 5）第五，我们在随机生成和实际应用中进行了大量仿真实验。实验结果清楚地表明，就工作流执行的总财务成本而言，我们提出的工作流调度策略（CETSS）优于现有的可共享计费期感知算法 LHCM 和不可共享计费期感知算法 PCP。

📊效果

• 我们在一些合成随机生成的应用和实际应用（如表观基因组学、CyberShake 和 LIGO）上进行了严格的仿真。实验结果清楚地表明，我们提出的启发式 CETSS 优于现有算法，能有效节省工作流的总执行成本。特别是，CETSS 非常适合大型工作流应用。

⛳️未来机会

• 实验结果也证明，我们提出的算法 CETSS 非常适合大规模工作流应用。主要原因有两个：
  • 1）一是 CETSS 有更多机会与其他任务共享租用计费时段。
  • 2）另一个原因是，我们的动态子截止日期计算策略为将任务调度到更便宜的资源提供了宽松的条件。

🧠疑问

1. 所定义的“大规模”有多大？依据是什么？
2. 具体效率能达到多少？

---

---

• 希望这篇博客对你有帮助！如果你有任何问题或需要进一步的帮助，请随时提问。
• 如果你喜欢这篇文章，欢迎动动小手 给我一个follow或star。

🗺参考文献

[1] X. Tang et al., “Cost-Efficient Workflow Scheduling Algorithm for Applications With Deadline Constraint on Heterogeneous Clouds,” in IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 9, pp. 2079-2092, 1 Sept. 2022, doi: 10.1109/TPDS.2021.3134247.