A Rapid Heuristic for Scheduling Non-Preemptive Dependent Periodic Tasks onto Multiprocessor - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

A Rapid Heuristic for Scheduling Non-Preemptive Dependent Periodic Tasks onto Multiprocessor

Résumé

We address distributed real-time applications represented by systems of non-preemptive dependent periodic tasks. This system is described by an acyclic directed graph. Because the distribution and the scheduling of these tasks onto a multiprocessor is an NP-hard problem we propose a greedy heuristic to solve it. Our heuristic sequences three algorithms: assignment, unrolling, and scheduling. The tasks of the same, or multiple, periods are assigned to the same processor according to a mixed sort. Then, the initial graph of tasks is unrolled, i.e. each task is repeated according to the ratio between its period and the least common multiple of all periods of tasks. Finally, the tasks of the unrolled graph are distributed and scheduled onto the processors where they have been assigned. Then, we give the complexity of this heuristic, and we illustrate it with an example. A performance analysis comparing our heuristic with an optimal Branch and Cut algorithm concludes that our heuristic is effective in terms of scheduling success ratio and speed.
Fichier principal
Vignette du fichier
pdcs07.pdf (282.02 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00413486 , version 1 (04-09-2009)

Identifiants

  • HAL Id : inria-00413486 , version 1

Citer

Omar Kermia, Yves Sorel. A Rapid Heuristic for Scheduling Non-Preemptive Dependent Periodic Tasks onto Multiprocessor. Proceedings of ISCA 20th International Conference on Parallel and Distributed Computing Systems, PDCS'07, 2007, Las Vegas, Nevada, United States. ⟨inria-00413486⟩
536 Consultations
269 Téléchargements

Partager

Gmail Facebook X LinkedIn More