Skip to Main content Skip to Navigation
Reports

A Linear Algorithm for Real-Time Scheduling with Optimal Energy Use

Bruno Gaujal 1 Nicolas Navet 2 Cormac Walsh 1
2 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We present an algorithm for scheduling a set of non-recurrent tasks (or jobs) with real-time constraints so as to minimize the total energy consumption on a dynamically variable voltage processor. Our algorithm runs in linear time and is thus an improvement over the classical algorithm of Yao et al. It was made possible by considering the problem as a shortest path problem. We also propose an algorithm for the case where the processor possesses only a limited number of clock frequencies. We extend this algorithm to provide the minimum number of speed changes, which is important when the speed switching overhead cannot be neglected. All our algorithms are linear in the number of tasks if the arrivals and deadlines are sorted and need O(N logN) time otherwise and these complexities are shown optimal. We extend the results to fluid tasks and non-convex cost functions. An interesting by-product of this study is that it furnishes a linear time feasibility test for a set of non-recurrent tasks scheduled under EDF. This is an improvement over the classical one.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00071696
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:33:22 PM
Last modification on : Friday, June 25, 2021 - 3:40:05 PM

Identifiers

  • HAL Id : inria-00071696, version 1

Citation

Bruno Gaujal, Nicolas Navet, Cormac Walsh. A Linear Algorithm for Real-Time Scheduling with Optimal Energy Use. [Research Report] RR-4886, LIP RR-2003-38, INRIA,LIP. 2003. ⟨inria-00071696⟩

Share

Metrics

Record views

297

Files downloads

233