A Stretching Algorithm for Parallel Real-time DAG Tasks on Multiprocessor Systems

Manar Qamhieh (1) , Laurent George (2) , Serge Midonnet (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 LISSI - Laboratoire Images, Signaux et Systèmes Intelligents

Parallelism is becoming more important nowadays due to the increasing use of multiprocessor systems. In this paper, we study the problem of scheduling periodic parallel real-time Directed Acyclic graph (DAG) tasks on m homogeneous multiprocessor systems. A DAG task is an example of inter-subtask parallelism. It consists of a collection of dependent subtasks under precedence constraints. The dependencies between subtasks make scheduling process more challenging. We propose a stretching algorithm applied on each DAG tasks to transform them into a set of independent sequential threads with intermediate offsets and deadlines. The threads obtained with the transformation are two types, (i) fully-stretched master threads with utilization equal to 1 and (ii) constrained-deadline independent threads. The fully-stretched master threads are assigned to dedicated processors and the remaining processors m' ≤ m, are scheduled using global EDF scheduling algorithm. Then, we prove that preemptive global EDF scheduling of stretched threads has a resource augmentation bound equal to (3+ √ 5)/2 for all tasksets with n < ϕ * m , where n is the number of tasks in the taskset and ϕ is the golden ratio 1 .

Mots clés: Real-time scheduling; parallel tasks; Directed Acyclic Graphs; global EDF scheduling; speedup factor

Domaines: Informatique [cs]; Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]

Manar Qamhieh, Laurent George, Serge Midonnet. A Stretching Algorithm for Parallel Real-time DAG Tasks on Multiprocessor Systems. The 22nd International Conference on Real-Time Networks and Systems, Oct 2014, Versaille, France. pp.13-22, ⟨10.1145/2659787.2659818⟩. ⟨hal-01090627⟩