Dynamic voltage scaling under EDF revisited

Bruno Gaujal 1, 2, 3, 4 Nicolas Navet 1
1 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 SLOOP - Simulation, Object Oriented Languages and Parallelism
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Basic algorithms have been proposed in the field of low-power (Yao, F., et al. in Proceedings of lEEE annual foundations of computer science, pp. 374–382, 1995) which compute the minimum energy-schedule for a set of non-recurrent tasks (or jobs) scheduled under EDF on a dynamically variable voltage processor. In this study, we propose improvements upon existing algorithms with lower average and worst-case complexities. They are based on a new EDF feasibility test that helps to identify the “critical intervals”. The complexity of this feasibility test depends on structural characteristics of the set of jobs. More precisely, it depends on how tasks are included one in the other. The first step of the algorithm is to construct the Hasse diagram of the set of tasks where the partial order is defined by the inclusion relation on the tasks. Then, the algorithm constructs the shortest path in a geometrical representation at each level of the Hasse diagram. The optimal processor speed is chosen according to the maximal slope of each path.
Type de document :
Article dans une revue
Real-Time Systems / Real Time Systems; The Journal of Real-Time Systems, 2007, 37 (1), pp.77-97. <10.1007/s11241-007-9029-y>
Liste complète des métadonnées

Contributeur : Nicolas Navet <>
Soumis le : mardi 28 août 2007 - 13:33:17
Dernière modification le : mardi 25 octobre 2016 - 16:57:26
Document(s) archivé(s) le : jeudi 8 avril 2010 - 21:30:16


Fichiers produits par l'(les) auteur(s)




Bruno Gaujal, Nicolas Navet. Dynamic voltage scaling under EDF revisited. Real-Time Systems / Real Time Systems; The Journal of Real-Time Systems, 2007, 37 (1), pp.77-97. <10.1007/s11241-007-9029-y>. <inria-00168449>



Consultations de
la notice


Téléchargements du document