Séminaire - Real-time scheduling of periodic constrained deadlines parallel DAGs

Le prochain séminaire conjoint A3SI-LRT du LIGM (unité mixte de recherche de l'Université Paris Est) aura lieu le jeudi 30 juin de 14h00 à 15h00 à ESIEE PARIS (salle 260).

Real-time scheduling of periodic constrained deadlines parallel DAGs
Laurent George

Abstract: Parallelism is becoming more important nowadays due to the increasing use of multiprocessor systems. A Directed Acyclic Graph (DAG) is a general model of parallel tasks with inter-subtask parallelism. It consists of a collection of dependent subtasks under precedence constraints. In this talk, we study the problem of scheduling periodic parallel real-time DAG tasks on homogeneous multiprocessor systems. The dependencies between subtasks make scheduling process more challenging. We study two scheduling approaches: the DAG transformation approach and the Direct scheduling approche. The first approach is based on a stretching algorithm to be applied on each DAG task prior to scheduling process. Thus, DAGs are transformed into a set of independent sequential threads with intermediate offsets and deadlines. We consider the Global Earliest Deadline First (GEDF) from the fixed job level priority family. We prove that GEDF scheduling of stretched threads has a resource augmentation bound equal to (3+sqrt{5})/2.