Energy efficient online deadline scheduling

ABSTRACT

This paper extends the study of online algorithms for energy-efficient deadline scheduling to the overloaded setting. Specifically, we consider a processor that can vary its speed between 0 and a maximum speed T to minimize its energy usage (of which the rate is roughly a cubic function of the speed). As the speed is upper bounded, the system may be overloaded with jobs and no scheduling algorithms can meet the deadlines of all jobs. An optimal schedule is expected to maximize the throughput, and furthermore, its energy usage should be the smallest among all schedules that achieve the maximum throughput. In designing a scheduling algorithm, one has to face the dilemma of selecting more jobs and being conservative in energy usage. Even if we ignore energy usage, the best possible online algorithm is 4-competitive on throughput [12]. On the other hand, existing work on energy-efficient scheduling focuses on minimizing the energy to complete all jobs on a processor with unbounded speed, giving several O(1)-competitive algorithms with respect to the energy usage [2, 20]. This paper presents the first online algorithm for the more realistic setting where processor speed is bounded and the system may be overloaded; the algorithm is O(1)-competitive on both throughput and energy usage. If the maximum speed of the online scheduler is relaxed slightly to (1 + ε)T for some ε > 0, we can improve the competitive ratio on throughput to arbitrarily close to one, while maintaining O(1)-competitive on energy usage.

REFERENCES

• 1: S. Albers and H. Fujiwara. Energy-efficient algorithms for flow time minimization. In Proc. STACS, 621--633, 2006.
• 2: Nikhil Bansal , Tracy Kimbrel , Kirk Pruhs, Dynamic Speed Scaling to Manage Energy and Temperature, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.520-529, October 17-19, 2004 [doi>10.1109/FOCS.2004.24]
• 3: N. Bansal and K. Pruhs. Speed scaling to manage temperature. In Proc. STACS, pages 460--471, 2005.
• 4: S. Baruah , G. Koren , B. Mishra , A. Raghunathan , L. Rosier , D. Shasha, On-line scheduling in the presence of overload, Proceedings of the 32nd annual symposium on Foundations of computer science, p.100-110, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185354]
• 5: David M. Brooks , Pradip Bose , Stanley E. Schuster , Hans Jacobson , Prabhakar N. Kudva , Alper Buyuktosunoglu , John-David Wellman , Victor Zyuban , Manish Gupta , Peter W. Cook, Power-Aware Microarchitecture: Design and Modeling Challenges for Next-Generation Microprocessors, IEEE Micro, v.20 n.6, p.26-44, November 2000 [doi>10.1109/40.888701]
• 6: David P. Bunde, Power-aware scheduling for makespan and flow, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148140]
• 7: M. L. Dertouzos. Control robotics: the procedural control of physical processes. In Proc. IFIP Congress, pages 807--813, 1974.
• 8: Dirk Grunwald , Charles B. Morrey, III , Philip Levis , Michael Neufeld , Keith I. Farkas, Policies for dynamic clock scheduling, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.6-6, October 22-25, 2000, San Diego, California
• 9: Sandy Irani , Sandeep Shukla , Rajesh Gupta, Algorithms for power savings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 10: Sandy Irani , Kirk R. Pruhs, Algorithmic problems in power management, ACM SIGACT News, v.36 n.2, June 2005 [doi>10.1145/1067309.1067324]
• 11: Woo-Cheol Kwon , Taewhan Kim, Optimal voltage allocation techniques for dynamically variable voltage processors, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.1, p.211-230, February 2005 [doi>10.1145/1053271.1053280]
• 12: Gilad Koren , Dennis Shasha, D^over: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems, SIAM Journal on Computing, v.24 n.2, p.318-339, April 1995 [doi>10.1137/S0097539792236882]
• 13: M. Li, B. J. Liu, and F. F. Yao. Min-energy voltage allocations for tree-structured tasks. In Proc. COCOON, pages 283--296, 2005.
• 14: Minming Li , Frances F. Yao, An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules, SIAM Journal on Computing, v.35 n.3, p.658-671, 2005 [doi>10.1137/050629434]
• 15: Padmanabhan Pillai , Kang G. Shin, Real-time dynamic voltage scaling for low-power embedded operating systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 16: K. Pruhs, P. Uthaisombut, and G. Woeginger. Getting the best response for your erg. In Proc. SWAT, pages 14--25, 2004.
• 17: K. Pruhs, R. van Stee, and P. Uthaisombut. Speed scaling of tasks with precedence constraints. In Proc. WAOA, pages 307--319, 2005.
• 18: Han-Saem Yun , Jihong Kim, On energy-optimal voltage scheduling for fixed-priority hard real-time systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.3, p.393-430, August 2003 [doi>10.1145/860176.860183]
• 19: Mark Weiser , Brent Welch , Alan Demers , Scott Shenker, Scheduling for reduced CPU energy, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.2-es, November 14-17, 1994, Monterey, California
• 20: F. Yao , A. Demers , S. Shenker, A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.374, October 23-25, 1995