Discrete and continuous min-energy schedules for variable voltage processors

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

55 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)3983-3987
Journal / PublicationProceedings of the National Academy of Sciences of the United States of America
Issue number11
Publication statusPublished - 14 Mar 2006


Current dynamic voltage scaling techniques allow the speed of processors to be set dynamically to save energy consumption, which is a major concern in microprocessor design. A theoretical model for min-energy job scheduling was first proposed a decade ago, and it was shown that for any convex energy function, the min-energy schedule for a set of n jobs has a unique characterization and is computable in O(n3) time. This algorithm has remained as the most efficient known despite many investigations of this model. In this work, we give an algorithm with running time O(n2 log n) for finding the min-energy schedule. In contrast to the previous algorithm, which outputs optimal speed levels from high to low iteratively, our algorithm is based on finding successive approximations to the optimal schedule. At the core of the approximation is an efficient partitioning of the job set into high and low speed subsets by any speed threshold, without computing the exact speed function. © 2006 by The National Academy of Sciences of the USA.

Research Area(s)

  • Dynamic voltage scaling, Energy efficiency, Optimization, Scheduling