Power-aware scheduling for makespan and flow

ABSTRACT

We consider offline scheduling algorithms that incorporate speed scaling to address the bicriteria problem of minimizing energy consumption and a scheduling metric. For makespan, we give linear-time algorithms to compute all non-dominated solutions for the general uniprocessor problem and for the multiprocessor problem when every job requires the same amount of work. We also show that the multiprocessor problem becomes NP-hard when jobs can require different amounts of work.For total flow, we show that the optimal flow corresponding to a particular energy budget cannot be exactly computed on a machine supporting arithmetic and the extraction of roots. This hardness result holds even when scheduling equal-work jobs on a uniprocessor. We do, however, extend previous work by Pruhs et al. to give an arbitrarilygood approximation for scheduling equal-work jobs on a multiprocessor.

REFERENCES

• 1: Advanced Micro Devices, Inc. AMD Athlon 64 processor power and thermal data sheet (ver. 3.43), Oct 2004. http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/30430.pdf.
• 2: S. Albers and H. Fujiwara Energy-efficient algorithms for flow time minimization. In Proc. 23rd Intern. Symp. on Theoretical Aspects of Computer Science, pages 621--633, 2006.
• 3: Noga Alon , Yossi Azar , Gerhard J. Woeginger , Tal Yadid, Approximation schemes for scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.493-500, January 05-07, 1997, New Orleans, Louisiana, United States
• 4: Chanderjit Bajaj, The algebraic degree of geometric optimization problems, Discrete & Computational Geometry, v.3 n.2, p.177-191, Jan, 1988 [doi>10.1007/BF02187906]
• 5: 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 (FOCS'04), p.520-529, October 17-19, 2004 [doi>10.1109/FOCS.2004.24]
• 6: N. Bansal and K. Pruhs. Speed scaling to manage temperature. In Proc. 22nd Intern. Symp. on Theoretical Aspects of Computer Science, pages 460--471, 2005.
• 7: 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]
• 8: Chandra Chekuri , Michael Bender, An efficient approximation algorithm for minimizing makespan on uniformly related machines, Journal of Algorithms, v.41 n.2, p.212-224, November 2001 [doi>10.1006/jagm.2001.1184]
• 9: J. J. Chen, T. W. Kuo, and H. I Lu. Power-saving scheduling for weakly dynamic voltage scaling devices. In Proc. 9th Workshop on Algorithms and Data Structures, number 3608 in LNCS, pages 338--349, 2005.
• 10: Fabián A. Chudak , David B. Shmoys, Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.581-590, January 05-07, 1997, New Orleans, Louisiana, United States
• 11: D.S. Dummit and R.M. Foote. Abstract Algebra. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1991.
• 12: A. El Gamal, C. Nair, B. Prabhakar, E. Uysal-Biyikoglu, and S. Zahedi. Energy-efficient scheduling of packet transmissions over wireless networks. In Proc. IEEE Infocom, pages 1773--1782, 2002.
• 13: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 14: Sandy Irani , Kirk R. Pruhs, Algorithmic problems in power management, ACM SIGACT News, v.36 n.2, June 2005 [doi>10.1145/1067309.1067324]
• 15: Trevor Mudge, Power: A First-Class Architectural Design Constraint, Computer, v.34 n.4, p.52-58, April 2001 [doi>10.1109/2.917539]
• 16: M.L. Pinedo. Planning and scheduling in manufacturing and services. Springer Series in Operations Research. Springer Science+Business Media, Inc., 2005.
• 17: K. Pruhs, P. Uthaisombut, and G. Woeginger. Getting the best response for your erg. In Proc. 9th Scandanavian Workshop on Algorithm Theory, volume 3111 of LNCS, pages 14--25, 2004.
• 18: K. Pruhs, R. van Stee, and P. Uthaisombut. Speed scaling of tasks with precedence constraints. In Proc. 3rd Workshop on Approximation and Online Algorithms, volume 3879 of LNCS, pages 307--319, 2005.
• 19: The GAP Group. Gap system for computational discrete algebra. http://turnbull.mcs.st-and.ac.uk/~gap/.
• 20: Vivek Tiwari , Deo Singh , Suresh Rajgopal , Gaurav Mehta , Rakesh Patel , Franklin Baez, Reducing power in high-performance microprocessors, Proceedings of the 35th annual conference on Design automation, p.732-737, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277227]
• 21: Elif Uysal-Biyikoglu , Balaji Prabhakar , Abbas El Gamal, Energy-efficient packet transmission over a wireless link, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.487-499, August 2002 [doi>10.1109/TNET.2002.801419]
• 22: M. Weiser, B. Welch, A. Demers, and S. Shenker. Scheduling for reduced cpu energy. In Proc. 1st Symp. on Operating Systems Design and Implementation, pages 13--23, 1994.
• 23: Fen Xie , Margaret Martonosi , Sharad Malik, Compile-time dynamic voltage scaling settings: opportunities and limits, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 24: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending; Network communication

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Theory

Keywords:
dynamic voltage scaling, low power, power-aware scheduling, speed scaling