Response time analysis for G-EDF and G-DM scheduling of sporadic DAG-tasks with arbitrary deadline

New programming models have been proposed to exploit the parallelism of modern computing architectures. Also in the real-time domain more detailed task models are under evaluation to provide a tighter analysis of parallel application with precedence and timing constraints. This paper presents two schedulability tests based on Response Time Analysis for determining whether a set of sporadic DAG-tasks with arbitrary deadlines can be scheduled by G-EDF or G-DM on a platform consisting of m identical processor. The first test is a simple polynomial time test, while the second one is a pseudo-polynomial time test. Our tests exploit the combinatorial properties of the DAGs by considering the interference experienced by each vertex. We describe a set of simulations showing that our tests outperform the tests described in [7] in terms of schedulability ratio and running time. We also provide resource augmentation bounds for our polynomial time test when considering single-DAG systems.