Speed scaling with an arbitrary power function

ABSTRACT

All of the theoretical speed scaling research to date has assumed that the power function, which expresses the power consumption P as a function of the processor speed s, is of the form P = s^α, where α > 1 is some constant. Motivated in part by technological advances, we initiate a study of speed scaling with arbitrary power functions. We consider the problem of minimizing the total flow plus energy. Our main result is a (3+ε)-competitive algorithm for this problem, that holds for essentially any power function. We also give a (2+ε)-competitive algorithm for the objective of fractional weighted flow plus energy. Even for power functions of the form s^α, it was not previously known how to obtain competitiveness independent of α for these problems. We also introduce a model of allowable speeds that generalizes all known models in the literature.

REFERENCES

• 1: Susanne Albers and Hiroshi Fujiwara. Energy-efficient algorithms for flow time minimization. In Lecture Notes in Computer Science (STACS), volume 3884, pages 621--633, 2006.
• 2: Nikhil Bansal , Ho-Leung Chan , Tak-Wah Lam , Lap-Kei Lee, Scheduling for Speed Bounded Processors, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_34]
• 3: Nikhil Bansal , Ho-Leung Chan, Weighted flow time does not admit O(1)-competitive algorithms, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1238-1244, January 04-06, 2009, New York, New York
• 4: Nikhil Bansal , Kirk Pruhs , Cliff Stein, Speed scaling for weighted flow time, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.805-813, January 07-09, 2007, New Orleans, Louisiana
• 5: 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
• 6: Fred Bower, Daniel Sorin, and Landon Cox. The impact of dynamically heterogeneous multicore processors on thread scheduling. Unpublished.
• 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: J. Adam Butts , Gurindar S. Sohi, A static power model for architects, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.191-201, December 2000, Monterey, California, United States [doi>10.1145/360128.360148]
• 9: Xiaobo Fan , Wolf-Dietrich Weber , Luiz Andre Barroso, Power provisioning for a warehouse-sized computer, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 10: G. H. Hardy, J. E. Littlewood, and G. Polya. Inequalities. Cambridge University Press, 1952.
• 11: Tak-Wah Lam , Lap-Kei Lee , Isaac K. To , Prudence W. Wong, Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_54]
• 12: John Markoff and Steve Lohr. Intel's huge bet turns iffy. New York Times, September 29 2002.
• 13: Ke Meng , Russ Joseph, Process variation aware cache leakage management, Proceedings of the 2006 international symposium on Low power electronics and design, October 04-06, 2006, Tegernsee, Bavaria, Germany [doi>10.1145/1165573.1165636]
• 14: Kirk Pruhs, Competitive online scheduling for server systems, ACM SIGMETRICS Performance Evaluation Review, v.34 n.4, March 2007 [doi>10.1145/1243401.1243411]
• 15: Kirk Pruhs, Patchrawat Uthaisombut, and Gerhard Woeginger. Getting the best response for your erg. In Scandanavian Workshop on Algorithms and Theory, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.0 General