Online Scheduling of Moldable Task Graphs under Common Speedup Models
Online Scheduling of Moldable Task Graphs under Common Speedup Models
复制标题
DOI：
10.1145/3545008.3545049
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
A. Benoit;L. Perotin;Y. Robert;Hongyang Sun
中科院分区：
文献类型：
--
作者：
A. Benoit;L. Perotin;Y. Robert;Hongyang Sun
以最小化总完成时间（或完工时间）为目标在多处理器系统上调度可模制任务的问题已经被广泛研究，特别是当任务具有依赖性（即，任务图），或者当任务被即时释放时（即，在线）。然而，很少有研究集中在这两个方面（即，可模制任务图的在线调度）。在本文中，我们设计了一个新的在线算法，并得出了几个常见的但现实的加速模型（即，车顶线、通信、Amdahl和一般组合）。我们还证明，对于每个模型，我们的算法，这是非常接近的常数竞争比的竞争力的下限。最后，我们提供了第一个下界的竞争比的任何确定性的在线算法的任意加速模型，这不是常数，但取决于任务的数量在最长路径的图。
The problem of scheduling moldable tasks on multiprocessor systems with the objective of minimizing the overall completion time (or makespan) has been widely studied, in particular when tasks have dependencies (i.e., task graphs), or when tasks are released on-the-fly (i.e., online). However, few studies have focused on both (i.e., online scheduling of moldable task graphs). In this paper, we design a new online algorithm and derive constant competitive ratios for this problem under several common yet realistic speedup models (i.e., roofline, communication, Amdahl, and a general combination). We also prove, for each model, a lower bound on the competitiveness of our algorithm, which is very close to the constant competitive ratio. Finally, we provide the first lower bound on the competitive ratio of any deterministic online algorithm for the arbitrary speedup model, which is not constant but depends on the number of tasks in the longest path of the graph.