Response Time Analysis and Optimization of DAG Tasks Exploiting Mutually Exclusive Execution

There is an increasing move towards implementing embedded real-time systems upon multiprocessors with parallel applications, which are usually modeled as Directed Acyclic Graphs (DAGs). Plentiful work has been presented to optimize the bound of Worst-Case Response Time (WCRT) since the cornerstone work proposed by Graham in 1969. However, all these works are developed on the basis of Graham’s bound and failed to tackle the root of pessimism in it. In this work, we present a novel method to optimize the WCRT bound of a DAG task by designing mutually exclusive groups so that a sequential execution is enforced for some nodes, under which the problem of bounding WCRT becomes a problem of identifying a mutually exclusive path and thus does not suffer the pessimism in Graham’s bound. Experiments are conducted to evaluate the performance of our method against other WCRT optimization approaches in the state-of-the-art.