David P. Bunde
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.
- 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.]]Google Scholar
- 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.]] Google ScholarDigital Library
- N. Alon, Y. Azar, G.J. Woeginger, and T. Yadid. Approximation schemes for scheduling. In Proc. 8th Annual ACM-SIAM Symp. Discrete Algorithms, pages 493--500, 1997.]] Google ScholarDigital Library
- C. Bajaj. The algebraic degree of geometric optimization problems. Discrete Comput. Geom., 3:177--191, 1988.]]Google ScholarDigital Library
- N. Bansal, T. Kimbrel, and K. Pruhs. Dynamic speed scaling to manage energy and temperature. In Proc. 45th Symp. Found. Computer Science, pages 520--529, 2004.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- C. Chekuri and M.A. Bender. An efficient approximation algorithm for minimizing makespan on uniformly related machines. Journal of Algorithms, 41:212--224, 2001.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- F.A. Chudak and D.B. Shmoys. Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. In Proc. 8th Annual ACM-SIAM Symp. Discrete Algorithms, pages 581--590, 1997.]] Google ScholarDigital Library
- D.S. Dummit and R.M. Foote. Abstract Algebra. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1991.]]Google Scholar
- 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.]]Google ScholarCross Ref
- M.R. Garey and D.S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Company, 1979.]] Google ScholarDigital Library
- S. Irani and K.R. Pruhs. Algorithmic problems in power management. SIGACT News, 32(2):63--76, 2005.]] Google ScholarDigital Library
- T. Mudge. Power: A first-class architectural design constraint. Computer, 34(4):52--58, 2001.]] Google ScholarDigital Library
- M.L. Pinedo. Planning and scheduling in manufacturing and services. Springer Series in Operations Research. Springer Science+Business Media, Inc., 2005.]]Google Scholar
- 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.]]Google ScholarCross Ref
- 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.]] Google ScholarDigital Library
- The GAP Group. Gap system for computational discrete algebra. http://turnbull.mcs.st-and.ac.uk/~gap/.]]Google Scholar
- V. Tiwari, D. Singh, S. Rajgopal, G. Mehta, R. Patel, and F. Baez. Reducing power in high-performance microprocessors. In Proc. 35th ACM/IEEE Design Automation Conference, pages 732--737, 1998.]] Google ScholarDigital Library
- E. Uysal-Biyikoglu, B. Prabhakar, and A. El Gamal. Energy-efficient packet transmission over a wireless link. IEEE/ACM Trans. Networking, 10(4):487--499, Aug. 2002.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- F. Xie, M. Martonosi, and S. Malik. Compile-time dynamic voltage scaling settings: Opportunities and limits. In Proc. 2005 ACM SIGPLAN Conf. on Programming Language Design and Implementation, pages 49--62, 2003.]] Google ScholarDigital Library
- F. Yao, A. Demers, and S. Shenker. A scheduling model for reduced CPU energy. In Proc. 36th Symp. Found. Computer Science, pages 374--382, 1995.]] Google ScholarDigital Library
Index Terms
- Power-aware scheduling for makespan and flow
Recommendations
Power-aware scheduling for makespan and flow
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 a linear-time algorithm to compute all non-dominated solutions for ...
Power-Aware Real-Time Scheduling upon Identical Multiprocessor Platforms
SUTC '08: Proceedings of the 2008 IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (sutc 2008)In this paper, we address the power-aware scheduling of sporadic constrained-deadline hard real-time tasks using dynamic voltage scaling upon multiprocessor platforms. We propose two distinct algorithms. Our first algorithm is an off-line speed ...
Variable voltage task scheduling algorithms for minimizing energy/power
In this paper, we propose variable voltage task scheduling algorithms that minimize energy or minimize peak power for the case when the task arrival times, deadline times, execution times, periods, and switching activities are given. We consider ...
Comments