Skip to Main content Skip to Navigation
New interface
Journal articles

Dynamic voltage scaling under EDF revisited

Bruno Gaujal 1, 2, 3 Nicolas Navet 4 
3 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
4 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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.
Complete list of metadata
Contributor : Nicolas Navet Connect in order to contact the contributor
Submitted on : Tuesday, August 28, 2007 - 1:33:17 PM
Last modification on : Tuesday, October 25, 2022 - 4:24:45 PM
Long-term archiving on: : Thursday, April 8, 2010 - 9:30:16 PM


Files produced by the author(s)



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



Record views


Files downloads