Optimal speed scaling under arbitrary power functions

Abstract

This paper investigates the performance of online dynamic speed scaling algorithms for the objective of minimizing a linear combination of energy and response time. We prove that (SRPT, P^--1 (n)), which uses Shortest Remaining Processing Time (SRPT) scheduling and processes at speed such that the power used is equal to the queue length, is 2-competitive for a very wide class of power-speed tradeoff functions. Further, we prove that there exist tradeoff functions such that no online algorithm can attain a competitive ratio less than 2.

References

1. S. Albers and H. Fujiwara. Energy-efficient algorithms for flow time minimization. In Lecture Notes in Computer Science (STACS), volume 3884, pages 621--633, 2006.
2. N. Bansal, H.-L. Chan, and K. Pruhs. Speed scaling with an arbitrary power function. In Proc. ACM-SIAM SODA, 2009.
3. N. Bansal, T. Kimbrel, and K. Pruhs. Speed scaling to manage energy and temperature. J. ACM, 54(1):1--39, Mar.2007.
4. N. Bansal, K. Pruhs, and C. Stein. Speed scaling for weighted flow times. In Proc. ACM-SIAM SODA, pages 805--813, 2007.
5. D.P. Bunde. Power-aware scheduling for makespan and flow. In Proc.ACM Symp. Parallel Alg. and Arch., 2006.
6. R. Chandra, R. Mahajan, T. Moscibroda, R. Raghavendra, and P. Bahl. A case for adapting channel width in wireless networks. In Proc. ACM SIGCOMM, pages 135--146, Seattle, WA, Aug. 2008.
7. S. Herbert and D. Marculescu. Analysis of dynamic voltage/frequency scaling in chip-multiprocessors. In Proc. ISLPED, page 6, 2007.
8. IBM PowerPC. http://www-03.ibm.com/technology/power/powerpc.html.
9. Intel Xscale.www.intel.com/design/intelxscale.
10. S. Irani and K.R. Pruhs. Algorithmic problems in power management. SIGACT News, 36(2):63--76, 2005.
11. S. Kaxiras and M. Martonosi. Computer Architecture Techniques for Power-Efficiency. Morgan and Claypool, 2008.
12. T.-W. Lam, L.-K. Lee, I.K.K. To, and P.W.H. Wong. Speed scaling functions for flow time scheduling based on active job count. In Proc. European Symposium on Algorithms, 2009.
13. L. Mastroleon, D. O'Neill, B. Yolken, and N. Bambos. Power aware management of packet switches. In Proc. High-Perf. Interconn., 2007.
14. S. Narendra et al. Ultra-low voltage circuits and processor in 180nm to 90nm technologies with a swapped-body biasing technique. In Proc. IEEE Int. Solid-State Circuits Conf, page 8.4, 2004.
15. K. Pruhs, P. Uthaisombut, and G. Woeginger. Getting the best response for your erg. In Scandinavian Worksh. Alg. Theory, 2004.
16. K. Pruhs, R. van Stee, and P. Uthaisombut. Speed scaling of tasks with precedence constraints. In Proc. Worksh Approx. Online Alg., 2005.
17. O.S. Unsal and I. Koren. System-level power-aware deisgn techniques in real-time systems. Proc. IEEE, 91(7):1055--1069, 2003.
18. A. Wierman, L.L.H. Andrew, and A. Tang. Power-aware speed scaling in processor sharing systems. In Proc. IEEE IN FOCOM, 2009.
19. F. Yao, A. Demers, and S. Shenker. A scheduling model for reduced CPU energy. In Proc. IEEE Symp. Foundations of Computer Science (FOCS), pages 374--382, 1995.
20. L. Yuan and G. Qu. Analysis of energy reduction on dynamic voltage scaling-enabled systems. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 24(12):1827--1837, Dec. 2005.
21. S. Zhang and K.S. Catha. Approximation algorithm for the temperature-aware scheduling problem. In Proc. IEEE Int. Conf. Comp. Aided Design, pages 281--288, Nov. 2007.
22. Y. Zhu and F. Mueller. Feedback EDF scheduling of real-time tasks exploiting dynamic voltage scaling. Real Time Systems, 31:33--63, Dec. 2005.

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Hardware

  • Communication hardware, interfaces and storage

• Networks

  • Network performance evaluation

  • Network services

    • Network management