Min-energy voltage allocation for tree-structured tasks

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

42 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)305-319
Journal / PublicationJournal of Combinatorial Optimization
Volume11
Issue number3
Publication statusPublished - May 2006

Abstract

We study job scheduling on processors capable of running at variable voltage/speed to minimize energy consumption. Each job in a problem instance is specified by its arrival time and deadline, together with required number of CPU cycles. It is known that the minimum energy schedule for n jobs can be computed in O(n3) time, assuming a convex energy function. We investigate more efficient algorithms for computing the optimal schedule when the job sets have certain special structures. When the time intervals are structured as trees, the minimum energy schedule is shown to have a succinct characterization and is computable in time O(P) where P is the tree's total path length. We also study an on-line average-rate heuristics AYR and prove that its energy consumption achieves a small constant competitive ratio for nested job sets and for job sets with limited overlap. Some simulation results are also given.

Research Area(s)

  • Energy efficiency, Scheduling, Variable voltage processor

Citation Format(s)

Min-energy voltage allocation for tree-structured tasks. / Li, Minming; Liu, Becky Jie; Yao, Frances F.

In: Journal of Combinatorial Optimization, Vol. 11, No. 3, 05.2006, p. 305-319.

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