Speed scaling on parallel processors

ABSTRACT

In this paper we investigate algorithmic instruments leading to low powerconsumption in computing devices. While previous work on energy-efficient algorithms has mostly focused on single processor environments, in this paper we investigate multi-processor settings. We study the basic problem of scheduling a set of jobs, each specified by a release time, a deadline and a processing volume, on variable speed processors so as to minimize the total energy consumption. We first settle the complexity of speed scaling with unit size jobs. More specifically, we devise a polynomial time algorithm for agreeable deadlines and prove NP-hardness results for arbitrary release dates and deadlines. For the latter setting we also develop a polynomial time algorithm achieving a constant factor approximation guarantee that is independent of the number of processors. Additionally, we study speed scaling of jobs with arbitrary processing requirements and, again, develop constant factor approximation algorithms. We finally transform our offline algorithms into constant competitive online strategies.

REFERENCES

• 1: S. Albers and H. Fujiwara. Energy-efficient algorithms for flow time minimization. Proc. 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), Springer LNCS 3884, 621--633, 2006.
• 2: John Augustine , Sandy Irani , Chaitanya Swamy, Optimal Power-Down Strategies, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.530-539, October 17-19, 2004 [doi>10.1109/FOCS.2004.50]
• 3: 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]
• 4: Philippe Baptiste, Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.364-367, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109598]
• 5: Luiz André Barroso, The price of performance, Queue, v.3 n.7, September 2005 [doi>10.1145/1095408.1095420]
• 6: N. Bansal and K. Pruhs. Speed scaling to manage temperature. Proc. 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), Springer LNCS 3404, 460--471, 2005.
• 7: Jian-Jia Chen , Heng-Ruey Hsu , Kai-Hsiang Chuang , Chia-Lin Yang , Ai-Chun Pang , Tei-Wei Kuo, Multiprocessor Energy-Efficient Scheduling with Task Migration Considerations, Proceedings of the 16th Euromicro Conference on Real-Time Systems (ECRTS'04), p.101-108, June 30-July 02, 2004 [doi>10.1109/ECRTS.2004.20]
• 8: J.-J. Chen, T.-W. Kuo, H.-I. Lu. Power-saving scheduling for weakly dynamic voltage scaling devices. Proc. 9th International Workshop on Algorithms and Data Structures, Springer LNCS 3608, 338--349, 2005.
• 9: Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987 [doi>10.1145/7531.7535]
• 10: Intel pressroom. http://www.intel.com/pressroom/kits/teraflops/ or http://download.intel.com/pressroom/kits/Teraflops/Teraflops Research Chip Overview.pdf
• 11: 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
• 12: K. Pruhs, R. van Stee, P. Uthaisombut. Speed scaling of tasks with precedence constraints. Proc. 3rd International Workshop on Approximation and Online Algorithms (WAOA), Springer LNCS 3879, 307--319, 2005.
• 13: K. Pruhs, P. Uthaisombut and G. Woeginger. Getting the best response for your erg. Proc. 9th Scandinavian Workshop on Algorithm Theory (SWAT), Springer LNCS 3111, 15--25, 2004.
• 14: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 15: 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:
  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:
NP-completeness, approximation algorithms, energy efficiency, multiprocessor scheduling, online algorithms