Article

Speed scaling for weighted flow time

Authors:

Nikhil Bansal,

Kirk Pruhs,

Cliff SteinAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 805 - 813

Published: 07 January 2007 Publication History

Get Access

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.

Digital Library

Google Scholar

[2]

{BBS+00} David M. Brooks, Pradip Bose, Stanley E. Schuster, Hans Jacobson, Prabhakar N. Kudva, Alper Buyuktosunoglu, John-David Wellman, Victor Zyuban, Manish Gupta, and Peter W. Cook. Power-aware microarchitecture: Design and modeling challenges for next-generation microprocessors. IEEE Micro, 20(6):26--44, 2000.

Digital Library

Google Scholar

[3]

{BKP04} Nikhil Bansal, Tracy Kimbrel, and Kirk Pruhs. Dynamic speed scaling to manage energy and temperature. In IEEE Syposium on Foundations of Computer Science, pages 520--529, 2004.

Digital Library

Google Scholar

[4]

{BLMSP01} Luca Becchetti, Stefano Leonard!, Alberto Marchetti-Spaccamela, and Kirk R. Pruhs. Online weighted flow time and deadline scheduling. In Workshop on Approximation Algorithms for Combinatorial Optimization, pages 36--47, 2001.

Digital Library

Google Scholar

[5]

{Bun06} David Bunde. Power-aware scheduling for makespan and flow. In Proceedings of the 2006 ACM Symposium on Parallel Algorithms and Architectures, 2006. To appear.

Digital Library

Google Scholar

[6]

{HLP52} G. H. Hardy, J. E. Littlewood, and G. Polya. Inequalities. Cambridge University Press, 1952.

Google Scholar

[7]

{IPO5} Sandy Irani and Kirk R. Pruhs. Algorithmic problems in power management. SIGACT News, 36(2):63--76, 2005.

Digital Library

Google Scholar

[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.

Google Scholar

[9]

{Mud01} Trevor Mudge. Power: A first-class architectural design constraint. Computer, 34(4):52--58, 2001.

Digital Library

Google Scholar

[10]

{PUW04} Kirk Pruhs, Patchrawat Uthaisombut, and Gerhard Woeginger. Getting the best response for your erg. In Scandanavian Workshop on Algorithms and Theory, 2004.

Google Scholar

[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.

Google Scholar

[12]

{YDS95} F. Yao, A. Demers, and S. Shenker. A scheduling model for reduced cpu energy. In IEEE Syposium on Foundations of Computer Science, page 374, 1995.

Digital Library

Google Scholar

Cited By

View all

Mukherjee DDhara SBorst Svan Leeuwaarden J(2017)Optimal Service Elasticity in Large-Scale Distributed SystemsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/30844631:1(1-28)Online publication date: 13-Jun-2017
https://dl.acm.org/doi/10.1145/3084463
Gebrehiwot MAalto SLassila P(2014)Optimal sleep-state control of energy-aware M/G/1 queuesProceedings of the 8th International Conference on Performance Evaluation Methodologies and Tools10.4108/icst.Valuetools.2014.258149(82-89)Online publication date: 9-Dec-2014
https://dl.acm.org/doi/10.4108/icst.Valuetools.2014.258149
Tian YLin CLi K(2014)Managing performance and power consumption tradeoff for multiple heterogeneous servers in cloud computingCluster Computing10.1007/s10586-013-0326-z17:3(943-955)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.1007/s10586-013-0326-z
Show More Cited By

Speed scaling for weighted flow time
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Non-clairvoyant speed scaling for weighted flow time
ESA'10: Proceedings of the 18th annual European conference on Algorithms: Part I

We study online job scheduling on a processor that can vary its speed dynamically to manage its power. We attempt to extend the recent success in analyzing total unweighted flow time plus energy to total weighted flow time plus energy. We first consider ...
Speed Scaling for Weighted Flow Time

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 ...
Throughput maximization in multiprocessor speed-scaling

In the classical energy minimization problem, introduced in 24, we are given a set of n jobs each one characterized by its release date, its deadline, its processing volume and we aim to find a feasible schedule of the jobs on a single speed-scalable ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
416
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)4

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mukherjee DDhara SBorst Svan Leeuwaarden J(2017)Optimal Service Elasticity in Large-Scale Distributed SystemsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/30844631:1(1-28)Online publication date: 13-Jun-2017
https://dl.acm.org/doi/10.1145/3084463
Gebrehiwot MAalto SLassila P(2014)Optimal sleep-state control of energy-aware M/G/1 queuesProceedings of the 8th International Conference on Performance Evaluation Methodologies and Tools10.4108/icst.Valuetools.2014.258149(82-89)Online publication date: 9-Dec-2014
https://dl.acm.org/doi/10.4108/icst.Valuetools.2014.258149
Tian YLin CLi K(2014)Managing performance and power consumption tradeoff for multiple heterogeneous servers in cloud computingCluster Computing10.1007/s10586-013-0326-z17:3(943-955)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.1007/s10586-013-0326-z
Bansal NChan HPruhs K(2013)Speed Scaling with an Arbitrary Power FunctionACM Transactions on Algorithms10.1145/2438645.24386509:2(1-14)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1145/2438645.2438650
Lam TLee LTo IWong P(2013)Online Speed Scaling Based on Active Job Count to Minimize Flow Plus EnergyAlgorithmica10.1007/s00453-012-9613-y65:3(605-633)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1007/s00453-012-9613-y
Bell PWong P(2011)Multiprocessor speed scaling for jobs with arbitrary sizes and deadlinesProceedings of the 8th annual conference on Theory and applications of models of computation10.5555/2008967.2008973(27-36)Online publication date: 23-May-2011
https://dl.acm.org/doi/10.5555/2008967.2008973
Xu DLiu XFan BLin BSinha PXu J(2011)Minimizing energy cost for internet-scale datacenters with dynamic trafficProceedings of the Nineteenth International Workshop on Quality of Service10.5555/1996039.1996054(1-2)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.5555/1996039.1996054
Sun HHe YHsu W(2011)Speed scaling for energy and performance with instantaneous parallelismProceedings of the First international ICST conference on Theory and practice of algorithms in (computer) systems10.5555/1987334.1987358(240-251)Online publication date: 18-Apr-2011
https://dl.acm.org/doi/10.5555/1987334.1987358
Chan HLam TLi R(2011)Energy-efficient due date schedulingProceedings of the First international ICST conference on Theory and practice of algorithms in (computer) systems10.5555/1987334.1987343(69-80)Online publication date: 18-Apr-2011
https://dl.acm.org/doi/10.5555/1987334.1987343
Pruhs KStein C(2010)How to schedule when you have to buy your energyProceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques10.5555/1886521.1886549(352-365)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.5555/1886521.1886549
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Non-clairvoyant speed scaling for weighted flow time

Speed Scaling for Weighted Flow Time

Throughput maximization in multiprocessor speed-scaling