Conditionally Optimal Parallelization of Real-Time DAG Tasks for Global EDF

Real-time applications with high computational demand, e.g., autonomous driving, are emerging and their complex nature conforms to a DAG(directed acyclic graph) structure. We propose a conditionally optimal parallelization for real-time DAG tasks for global EDF, ensuring complete execution of all tasks within the deadline. To achieve this, we formalize a monotonic increasing property of both tolerance and interference to the parallelization option. Using such properties, we develop a unidirectional search algorithm that can assign parallelization options in polynomial time, which we formally prove the optimality. We observe significant improvement of schedulability through simulation experiment, and then in the following implementation experiment, we demonstrate that the algorithm is practically applicable for real-world use-cases.