Min-energy voltage allocation for tree-structured tasks |
| |
Authors: | Minming Li Becky Jie Liu Frances F Yao |
| |
Institution: | (1) Department of Computer Science, Tsinghua University, Beijing, China;(2) Department of Computer Science, City University of Hong Kong, Hong Kong |
| |
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 AVR 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.
This work is supported in part by Research Grants Council of Hong Kong under grant No. CityU 1165/04E, National Natural Science
Foundation of China under Grant No. 60135010, 60321002 and the Chinese National Key Foundation Research & Development Plan
(2004CB318108). |
| |
Keywords: | Scheduling Variable voltage processor Energy efficiency |
本文献已被 SpringerLink 等数据库收录! |
|