Getting the best response for your erg

ABSTRACT

We consider the speed scaling problem of minimizing the average response time of a collection of dynamically released jobs subject to a constraint A on energy used. We propose an algorithmic approach in which an energy optimal schedule is computed for a huge A, and then the energy optimal schedule is maintained as A decreases. We show that this approach yields an efficient algorithm for equi-work jobs. We note that the energy optimal schedule has the surprising feature that the job speeds are not monotone functions of the available energy. We then explain why this algorithmic approach is problematic for arbitrary work jobs. Finally, we explain how to use the algorithm for equi-work jobs to obtain an algorithm for arbitrary work jobs that is O(1)-approximate with respect to average response time, given an additional factor of (1 + ε) energy.

REFERENCES

• 1: Albers, S., and Fujiwara, H. 2006. Energy efficient algorithms for flow time minimization. In Proceedings of the Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science. Springer-Verlag, New York, 621--633.
• 2: John Augustine , Sandy Irani , Chaitanya Swamy, Optimal Power-Down Strategies, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 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, p.520-529, October 17-19, 2004 [doi>10.1109/FOCS.2004.24]
• 4: Bansal, N., and Pruhs, K. 2005. Speed scaling to manage temperature. In Symposium on Theoretical Aspects of Computer Science. 460--471.
• 5: Bazaraa, M., Sherali, H., and Shetty, C. 1979. Nonlinear Programming: Theory and Algorithms. Wiley, New York.
• 6: Luca Becchetti , Stefano Leonardi , Alberto Marchetti-Spaccamela , Kirk Pruhs, Online Weighted Flow Time and Deadline Scheduling, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, p.36-47, August 18-20, 2001
• 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: Chen, J.-J., Kuo, T.-W., and Lu, H.-I. 2005. Power-saving scheduling for weakly dynamic voltage scaling devices. In Proceedings of the Workshop on Algorithms and Data Structures. 338--349.
• 9: Jian-Jia Chen , Tei-Wei Kuo , Chia-Lin Yang, Profit-driven uniprocessor scheduling with energy and timing constraints, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968072]
• 10: 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
• 11: Woo-Cheol Kwon , Taewhan Kim, Optimal voltage allocation techniques for dynamically variable voltage processors, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775867]
• 12: Li, M., Liu, B. J., and Yao, F. F. 2005. Min-energy voltage allocation for tree-structured tasks. In Proceedings of the International Computing and Combinatorics Conference. 283--296.
• 13: Trevor Mudge, Power: A First-Class Architectural Design Constraint, Computer, v.34 n.4, p.52-58, April 2001 [doi>10.1109/2.917539]
• 14: Nesterov, I., and Nemirovski. 1994. Interior Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics, Philadelphia, PA.
• 15: Pruhs, K., van Stee, R., and Uthaisombut, P. P. 2005. Speed scaling of tasks with precedence constraints. In Proceedings of the WAOA. 307--319.
• 16: 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
• 17: Han-Saem Yun , Jihong Kim, On energy-optimal voltage scheduling for fixed-priority hard real-time systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.3, p.393-430, August 2003 [doi>10.1145/860176.860183]

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

Keywords:
Speed scaling, frequency scaling, power management, scheduling, voltage scaling