skip to main content
10.5555/1283383.1283468acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Energy efficient online deadline scheduling

Published: 07 January 2007 Publication History

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]
N. Bansal, T. Kimbrel, and K. Pruhs. Dynamic speed scaling to manage energy and temperature. In Proc. FOCS, pages 520--529, 2004.
[3]
N. Bansal and K. Pruhs. Speed scaling to manage temperature. In Proc. STACS, pages 460--471, 2005.
[4]
S. Baruah, G. Keren, B. Mishra, A. Raghunathan, L. Rosier, and D. Shasha. On-line scheduling in the presence of overload. In Proc. FOCS, pages 100--110, 1991.
[5]
D. M. Brooks, P. Bose, S. E. Schuster, H. Jacobson, P. N. Kudva, A. Buyuktosunoglu, J. D. Wellman, V. Zyuban, M. Gupta, and P. W. Cook. Power-aware microarchitecture: Design and modeling challenges for next-generation microprocessors. IEEE Micro, 20(6):26--44, 2000.
[6]
D. P. Bunde. Power-aware scheduling for makespan and flow. In Proc. SPAA, 2006, to appear.
[7]
M. L. Dertouzos. Control robotics: the procedural control of physical processes. In Proc. IFIP Congress, pages 807--813, 1974.
[8]
D. Grunwald, P. Levis, K. I. Farkas, C. B. Morrey, and M. Neufeld. Policies for dynamic clock scheduling. In Proc. OSDI, pages 73--86, 2000.
[9]
S. Irani, R. K. Gupta, and S. Shukla. Algorithms for power savings. In Proc. SODA, pages 37--46, 2003.
[10]
S. Irani and K. Pruhs. Algorithmic problems in power management. SIGACT News, 2005.
[11]
W. C. Kwon and T. Kim. Optimal voltage allocation techniques for dynamically variable voltage processors. ACM Transactions on Embedded Computing Systems, 4(1):221--230, 2005.
[12]
G. Keren and D. Shasha. Dover: An optimal on-line scheduling algorithm for overloaded uniprocessor realtime systems. SIAM J. Comput., 24(2):318--339, 1995.
[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]
M. Li and F. Yao. An efficient algorithm for computing optimal discrete voltage schedules. SIAM J. Comput, 35(3):658--671, 2005.
[15]
P. Pillai and K. G. Shin. Real-time dynamic voltage scaling for low-power embedded operating systems. In Proc. SOSP, pages 89--102, 2001.
[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]
H. S. Yun and J. Kim On energy-optimal voltage scheduling for fixed-priority hard real-time systems. ACM Transactions on Embedded Computing Systems, 2(3): 393--430, 2003.
[19]
M. Weiser, B. Welch, A. Demers, and S. Shenker. Scheduling for reduced CPU energy. In Proc. OSDI, pages 13--23, 1994.
[20]
F. Yao, A. Demers, and S. Shenker. A scheduling model for reduced CPU energy. In Proc. FOCS, pages 374--382, 1995.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
January 2007
1322 pages
ISBN:9780898716245
  • Conference Chair:
  • Harold Gabow

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

  • Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;
Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)1
Reflects downloads up to 28 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2018)A new rule-based power-aware job scheduler for supercomputersThe Journal of Supercomputing10.1007/s11227-018-2281-174:6(2508-2527)Online publication date: 1-Jun-2018
  • (2016)Throughput maximization in multiprocessor speed-scalingTheoretical Computer Science10.1016/j.tcs.2016.03.020630:C(1-12)Online publication date: 30-May-2016
  • (2015)Rate-adaptive scheduling policies for network stability and energy efficiencyIEEE/ACM Transactions on Networking10.1109/TNET.2014.234650723:6(1755-1764)Online publication date: 1-Dec-2015
  • (2015)From preemptive to non-preemptive speed-scaling schedulingDiscrete Applied Mathematics10.1016/j.dam.2014.10.007181:C(11-20)Online publication date: 30-Jan-2015
  • (2013)Energy efficient scheduling of parallelizable jobsProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627885(948-957)Online publication date: 6-Jan-2013
  • (2013)Online Speed Scaling Based on Active Job Count to Minimize Flow Plus EnergyAlgorithmica10.1007/s00453-012-9613-y65:3(605-633)Online publication date: 1-Mar-2013
  • (2012)Slow down and sleep for profit in online deadline schedulingProceedings of the First Mediterranean conference on Design and Analysis of Algorithms10.1007/978-3-642-34862-4_17(234-247)Online publication date: 3-Dec-2012
  • (2011)A tutorial on amortized local competitiveness in online schedulingACM SIGACT News10.1145/1998037.199805842:2(83-97)Online publication date: 10-Jun-2011
  • (2011)On multi-processor speed scaling with migrationProceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures10.1145/1989493.1989539(279-288)Online publication date: 4-Jun-2011
  • (2011)Approximation algorithms for variable voltage processorsTheoretical Computer Science10.1016/j.tcs.2010.10.011412:32(4074-4080)Online publication date: 1-Jul-2011
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media