On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems
On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems
复制标题
DOI：
10.1109/ipdps47924.2020.00112
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
A. Marchetti-Spaccamela;Nicole Megow;Jens Schlöter;M. Skutella;L. Stougie
中科院分区：
文献类型：
--
作者：
A. Marchetti-Spaccamela;Nicole Megow;Jens Schlöter;M. Skutella;L. Stougie
随着并行处理在现代计算系统中的广泛应用，人们提出了并行任务模型来描述并行应用的结构。工作流调度问题在过去的几年中得到了广泛的研究，主要集中在多处理器系统和分布式环境（如网格，集群）。在工作流调度中，应用程序被建模为有向无环图（DAG）。在实时调度社区中也引入了DAG来对多核架构上的多线程程序的执行进行建模。在大多数情况下，DAG模型假设一个固定的DAG结构，只捕获直线代码。直到最近，才提出了更一般的模型。特别地，条件DAG模型允许存在控制结构，例如条件（if-then-else）构造。虽然已经给出了条件达格模型的第一个算法结果，但可调度性分析的复杂性仍然悬而未决。我们对列表调度下条件DAG任务的最坏情况完工时间（最晚完成时间）进行了全面的分析。固定优先级调度）。我们展示了几个硬度的结果，关于多个处理器上的优化问题的复杂性，即使条件DAG具有良好的嵌套结构。对于一般的条件DAG任务，即使在单个处理器上，问题也是棘手的。补充这些负面的结果，我们表明，某些实践相关的DAG结构是非常好处理的。
As parallel processing became ubiquitous in modern computing systems, parallel task models have been proposed to describe the structure of parallel applications. The workflow scheduling problem has been studied extensively over past years, focusing on multiprocessor systems and distributed environments (e.g. grids, clusters). In workflow scheduling, applications are modeled as directed acyclic graphs (DAGs). DAGs have also been introduced in the real-time scheduling community to model the execution of multi-threaded programs on a multi-core architecture. The DAG model assumes, in most cases, a fixed DAG structure capturing only straight-line code. Only recently, more general models have been proposed. In particular, the conditional DAG model allows the presence of control structures such as conditional (if-then-else) constructs. While first algorithmic results have been presented for the conditional DAG model, the complexity of schedulability analysis remains wide open. We perform a thorough analysis on the worst-case makespan (latest completion time) of a conditional DAG task under list scheduling (a.k.a. fixed-priority scheduling). We show several hardness results concerning the complexity of the optimization problem on multiple processors, even if the conditional DAG has a well-nested structure. For general conditional DAG tasks, the problem is intractable even on a single processor. Complementing these negative results, we show that certain practice-relevant DAG structures are very well tractable.