Seminar - Real-time scheduling of periodic constrained deadlines parallel DAGs

The next Joint A3SI-LRT Seminar of the LIGM (Joint Research Unit of the University of Paris-Est) will take place on Thursday June 30 from 14:00 to 15:00 at ESIEE PARIS (Room 260).

Real-time scheduling of periodic constrained deadlines parallel DAGs
Laurent George
Equipe LRT, LIGM, ESIEE

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.