Speed scaling for weighted flow time

ABSTRACT

In addition to the traditional goal of efficiently managing time and space, many computers now need to efficiently manage power usage. For example, Intel's SpeedStep and AMD's PowerNOW technologies allow the Windows XP operating system to dynamically change the speed of the processor to prolong battery life. In this setting, the operating system must not only have a job selection policy to determine which job to run, but also a speed scaling policy to determine the speed at which the job will be run. These policies must be online since the operating system does not in general have knowledge of the future. In current CMOS based processors, the speed satisfies the well known cube-root-rule, that the speed is approximately the cube root of the power [Mud01, BBS+00]. Thus, in this work, we make the standard generalization that the power is equal to speed to some power α ≥ 1, where one should think of α as being approximately 3 [YDS95, BKP04]. Energy is power integrated over time. The operating system is faced with a dual objective optimization problem as it both wants to conserve energy, and optimize some Quality of Service (QoS) measure of the resulting schedule.

REFERENCES

• 1: {AF06} 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: 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]
• 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: 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
• 5: David P. Bunde, Power-aware scheduling for makespan and flow, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148140]
• 6: {HLP52} G. H. Hardy, J. E. Littlewood, and G. Polya. Inequalities. Cambridge University Press, 1952.
• 7: Sandy Irani , Kirk R. Pruhs, Algorithmic problems in power management, ACM SIGACT News, v.36 n.2, June 2005 [doi>10.1145/1067309.1067324]
• 8: {LLLK84} J. Labetoulle, E. Lawler, J. K. Lenstra, and A. Rinnooy Kan. Preemptive scheduling of uniform machines subject to release dates. Progress in Combinatorial Optimization, pages 245--261, 1984.
• 9: Trevor Mudge, Power: A First-Class Architectural Design Constraint, Computer, v.34 n.4, p.52-58, April 2001 [doi>10.1109/2.917539]
• 10: {PUW04} Kirk Pruhs, Patchrawat Uthaisombut, and Gerhard Woeginger. Getting the best response for your erg. In Scandanavian Workshop on Algorithms and Theory, 2004.
• 11: {PvSU05} Kirk Pruhs, Rob van Stee, and Patchrawat Uthaisombut. Speed scaling of tasks with precedence constraints. In Workshop on Approximation and Online Algorithms, 2005.
• 12: 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