【论文】略读笔记67-前沿-大规模跨地域任务云边协作调度

📖《Efficient Flow-Based Scheduling for Geo-Distributed Simulation Tasks in Collaborative Edge and Cloud Environments》

2022 年国防科大团队发表于 CCF-A 类期刊 TPDS。

🎯需求

• 实验是科学的基础。当实验不能或不应该在真实系统中进行时，可以利用动态模型来完成特定目的的实验，这就是模拟。
  • 例如，飞机模拟器可以以更低的成本加快飞行员的培训，利用流行病模拟可以获得正确的公共卫生政策。
• 为了缓解因实体数量和高精密模型不断增加而导致的大规模模拟成本增加的问题，一些从业者选择在云环境中部署模拟应用程序。边缘计算是云计算的良好补充，可用于部署大规模地理分布式模拟应用，这些应用对不同模拟组件（本文中也称为任务）和用户之间的通信延迟非常敏感。
  • 与提交给集群的普通任务不同，模拟应用程序通常是紧密耦合的，各组件之间通过发送许多小消息频繁通信，以进行数据交换或维持模拟事件的正确随机顺序。
    • 对于分析模拟而言，大部分数据交换发生在模拟组件之间，消息捆绑等技术可以有效缓解云平台在传输小消息方面的限制。
    • 然而，在训练模拟等大规模地理分布模拟中，组件除了与其他模拟组件通信外，还需要与用户频繁地实时交换数据。将所有组件和模型部署在远程云数据中心很容易增加用户之间的通信延迟，造成数据中心的带宽瓶颈。
      • 例如，佩戴许多动作传感器的用户需要上传大量数据，以更新虚拟模拟环境中相应数字模型的状态。
  • 边缘计算是缓解这一问题的一个不错选择，它将计算资源置于用户附近，受到了工业界和学术界的广泛关注。
    • 虽然与远程云数据中心相比，边缘计算节点更接近用户，但其计算资源也不充足。事实上，当模拟组件部署在云端或边缘时，会出现性能权衡问题。对于一个给定的组件，如果它与相应用户之间的交换数据量较大，而与其他组件的通信频率相对较低，那么它最好部署在靠近相应用户的近边缘节点。否则，应将其部署在云数据中心。
• 我们主要关注云边协作环境中模拟组件的高效调度，以便在考虑主机容量限制的情况下最大限度地降低总体通信成本。此外，计算节点（云数据中心和边缘）之间的网络拓扑结构、用户和任务之间的交换数据量以及任务之间的通信强度都在考虑之列。
  • 由于模拟中的任务通常是紧密耦合的，因此应该对它们进行联合调度，这实际上是一个 NP-complete（NP-complete）多维组合优化问题。
  • 考虑到大规模地理分布模拟应用中的任务数量可能非常大，所选的调度策略应具有良好的扩展性。
  • 此外，由于资源状态（可用性和容量）的动态变化以及模拟任务的动态加入和退出，尽快获得所有任务的部署决策非常重要，要求调度算法具有较低的决策延迟。

🚧现状

• 有关这一问题的方法大致可分为三类，即元启发式算法、启发式算法和精确算法。
  • 1）元启发式算法主要针对通用问题设计，通常受自然现象启发，如遗传算法（GA）和粒子群优化（PSO）。
    • 优点：这些算法可以为许多具有复杂约束条件的优化问题获得近似最优解。
    • 缺点：然而，当问题空间较大时，这些算法会耗费大量时间，而且即使所有参数保持不变，结果也不是确定的。
  • 2）启发式算法是一组约束条件，旨在为特定问题找到好的解决方案。启发式算法是一类近似算法，倾向于按照某些预定义的规则（如主导资源公平性或最短作业优先）依次部署任务。
    • 优点：事实上，这些算法可以看作是算法运行时间与生成解决方案质量之间的权衡，其假设是，当每个任务都以最优方式安排时，最终的部署决定是可以接受的。
    • 缺点：然而，这些算法很难模拟任务之间复杂的相互作用。而且，这些启发式算法很容易陷入局部最优状态。
  • 3）精确算法试图通过复杂的分析和计算找到理论上的最优解。特别是，一些学者将任务调度问题建模为整数线性问题（ILP），并利用现成的求解器（如 CPLEX）来获得最优解。
    • 优点：基于现成求解器，算法求解非常方便。
    • 缺点：但这些算法所耗费的时间可能并不合理，尤其是在任务和主机数量非常大的情况下。主要原因可能是 ILP 的典型算法（如分支与边界法或切割面法）都是指数算法。
• 遗憾的是，现有的现代集群调度器大多基于队列（启发式算法），任务是按顺序调度的，因此缺乏联合处理紧密耦合任务的能力。
• 其他基于批处理的调度算法（元启发式算法、精确算法）通常也很耗时。
• 流网络是描述这一问题的一个很有前途的工具，它将任务调度问题表述为图上的最小成本最大流（MCMF）优化，在这种情况下，每个顶点代表一个任务节点或计算节点，从任务节点到计算节点的路径表示一个可能的布局决策。
  • 缺点：然而，现有的基于流量的调度器很少模拟任务或用户之间的交互，而且只考虑一维资源。

🛩创新

• 根据上述观察结果，我们设计了用于分布式模拟的新型基于流量的调度器 Pond。

  • 1）任务与其对应用户或其他任务之间的数据传输成本被模拟为每个弧的成本。
  • 2）此外，通过放宽一些约束条件，这个 NP 难的组合优化问题被简化为 MCMF 问题，这是一个 P 问题，并且已经开发出一些多项式时间算法。
  • 3）需要注意的是，网络流优化理论只支持一维流向量。由于本文同时考虑了 CPU 和内存资源，因此必须在 Pond 中做一些额外的工作。

• 总结而言，本文介绍的 Pond 是一种新型基于流的调度器，它能感知任务与用户以及异构多维资源之间的交互。

  • 首先，我们提出了边缘和云协作环境中大规模地理分布模拟的任务调度问题，分析了分布式模拟任务的特点，并通过将任务和用户之间的通信开销映射到网络中弧线的成本，将调度问题表述为流量网络上的最小成本最大流量（MCMF）问题。
  • 考虑到现有基于流量的调度器在处理多维资源时存在的固有缺陷，我们提出了一种基于主导资源概念的方法来处理具有多维资源需求的异构任务。
  • 我们设计了一些针对具体问题的启发式方法来消除不可行的放置决策。由流量碎片和容量违规引起的失败任务可通过在资源树中贪婪搜索来重新安排。

📊效果

• 基于阿里巴巴生产轨迹和一些随机合成参数进行了广泛的模拟实验。结果表明，与一些基线方法相比，Pond 可以在相当低的部署延迟内显著降低每个任务的平均通信成本。

⛳️未来机会

• 结果表明，当负载不是很高时，Pond_Domi 在部署质量和延迟方面表现良好。但是，在高负载情况下，Pond_Domi 的资源效率并不令人满意，这可以看作是性能和资源效率之间的权衡。在未来的工作中，我们将设计一些额外的机制来缓解上述缺点。

🧠疑问

1. 核心逻辑：传统模拟应用可以部署在云上，但大规模跨地域模拟需要与用户频繁交互，不适合在云上 -> 适合使用云边协作，根据任务特点决定在云还是在边 -> 问题是NP难的，算法应当能够处理动态变化的环境并快速求解 -> 现有算法大多没考虑模拟任务和用户之间的交互、动态变化的环境，或效率不够高 -> 提出Pond解决三大难点：刻画复杂交互、动态变化环境；将NP难问题转化为P问题，提高效率；提出算法，解决传统算法无法应对的多维资源、重调度问题。
2. 和边缘的关系不大？和跨地域数据中心的关系更大？边缘的特点体现在哪里？

---

---

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

🗺参考文献

[1] Z. Miao, P. Yong, Z. Jiancheng and Y. Quanjun, “Efficient Flow-Based Scheduling for Geo-Distributed Simulation Tasks in Collaborative Edge and Cloud Environments,” in IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 12, pp. 3442-3459, 1 Dec. 2022, doi: 10.1109/TPDS.2022.3155713.