Longer Is Shorter: Making Long Paths to Improve the Worst-Case Response Time of DAG Tasks

DAG (directed acyclic graph) tasks are widely used to model parallel real-time workload. The real-time performance of a DAG task not only depends on its total workload, but also its graph structure. Intuitively, with the same total workload, a DAG task with looser precedence constraints tends to have better real-time performance in terms of worst-case response time. However, this paper shows that actually we can shorten the worst-case response time of a DAG task by carefully adding new edges and constructing longer paths. We develop techniques based on the state-of-the-art DAG response time analysis methods to properly add new edges so that the worst-case response time bound guaranteed by formal analysis can be significantly reduced. An approach built upon the proposed techniques is also presented to handle the scheduling of multiple DAG tasks. Experiments under different parameter settings demonstrate the effectiveness of the proposed method.