Systematic Searches for Global Multiprocessor Real-Time Scheduling

Olivier Buffet 1 Liliana Cucu-Grosjean 2
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper we address the problem of global real-time periodic scheduling on homogeneous multiprocessor platforms. A number of theoretical results have been obtained in the field of real-time systems, but mainly focusing on properties of specific algorithms in uniprocessor settings. The multiprocessor case has been considered only recently, with few resolution techniques proposed and experimented with up to now. In this paper we discuss several systematic search algorithms—exploring different search spaces—that exploit various features of the problem. These approaches are then evaluated experimentally on numerous randomly generated problems. This work shows (1) how two heuristic approaches can solve most (feasible and unfeasible) problems in no time, and (2) how to improve a state of the art algorithm by looking at jobs' laxities and by focusing the search on bottlenecks. We also discuss limitations of the proposed solvers and future work.
Type de document :
Rapport
[Research Report] RR-7386, INRIA. 2010, pp.17
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00519324
Contributeur : Olivier Buffet <>
Soumis le : dimanche 19 septembre 2010 - 22:40:28
Dernière modification le : jeudi 11 janvier 2018 - 06:20:05
Document(s) archivé(s) le : mardi 23 octobre 2012 - 16:21:00

Fichier

RR-7386.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00519324, version 1

Collections

Citation

Olivier Buffet, Liliana Cucu-Grosjean. Systematic Searches for Global Multiprocessor Real-Time Scheduling. [Research Report] RR-7386, INRIA. 2010, pp.17. 〈inria-00519324〉

Partager

Métriques

Consultations de la notice

283

Téléchargements de fichiers

145