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

Omar Kermia 1 Yves Sorel 1
1 AOSTE - Models and methods of analysis and optimization for systems with real-time and embedding constraints
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Paris-Rocquencourt, COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Type de document :
Communication dans un congrès
Proceedings of ISCA 20th International Conference on Parallel and Distributed Computing Systems, PDCS'07, 2007, Las Vegas, Nevada, United States. 2007
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00413486
Contributeur : Kumar Guha <>
Soumis le : vendredi 4 septembre 2009 - 11:54:44
Dernière modification le : vendredi 25 mai 2018 - 12:02:04
Document(s) archivé(s) le : mardi 15 juin 2010 - 20:31:27

Fichier

pdcs07.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00413486, version 1

Collections

Citation

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. 2007. 〈inria-00413486〉

Partager

Métriques

Consultations de la notice

533

Téléchargements de fichiers

271