论文标题
使用长路径来界定DAG任务的响应时间
Bounding the Response Time of DAG Tasks Using Long Paths
论文作者
论文摘要
1969年，格雷厄姆（Graham）使用总工作负载和最长的DAG路径开发了一个众所周知的响应时间，该响应时间已被广泛应用于解决基于DAG的任务系统的许多调度和分析问题。本文使用总工作负载和DAG多个长路径的长度为DAG任务提供了一个新的响应时间，而不是Graham绑定中最长的路径。我们的新界限在理论上主导着，并在经验上优于格雷厄姆的界限。我们进一步将提出的方法扩展到多DAG任务系统。我们的计划性测试理论上主导了联合计划，并以相当大的利润优于最先进的。
In 1969, Graham developed a well-known response time bound for a DAG task using the total workload and the longest path of the DAG, which has been widely applied to solve many scheduling and analysis problems of DAG-based task systems. This paper presents a new response time bound for a DAG task using the total workload and the lengths of multiple long paths of the DAG, instead of the longest path in Graham's bound. Our new bound theoretically dominates and empirically outperforms Graham's bound. We further extend the proposed approach to multi-DAG task systems. Our schedulability test theoretically dominates federated scheduling and outperforms the state-of-the-art by a considerable margin.
