SPEED SCALING FOR WEIGHTED FLOW TIME

被引：35

作者：

Bansal, Nikhil ^{[1
]}

Pruhs, Kirk ^{[2
]}

Stein, Cliff ^{[3
]}

机构：

[1] IBM TJ Watson Res, Yorktown Hts, NY 10598 USA

[2] Univ Pittsburgh, Dept Comp Sci, Pittsburgh, PA 15260 USA

[3] Columbia Univ, Dept IEOR, New York, NY 10027 USA

来源：

SIAM JOURNAL ON COMPUTING | 2009年 / 39卷 / 04期

基金：

美国国家科学基金会;

关键词：

speed scaling; flow time; energy minimization; online algorithms; DESIGN; POWER;

D O I：

10.1137/08072125X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. We give an online speed scaling algorithm that is O(1)-competitive for the objective of weighted flow time plus energy. This algorithm also allows us to efficiently construct an O(1)-approximate schedule for minimizing weighted flow time subject to an energy constraint.

引用

页码：1294 / 1308

页数：15

共 16 条

[1] Energy-Efficient Algorithms for Flow Time Minimization [J].

Albers, Susanne ;

Fujiwara, Hiroshi .

ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (04)

[2]

BANSAL N, 2007, SPEED SCALING MANAGE, V54

[3] Average Rate Speed Scaling [J].

Bansal, Nikhil ;

Bunde, David P. ;

Chan, Ho-Leung ;

Pruhs, Kirk .

ALGORITHMICA, 2011, 60 (04) :877-889

[4]

Bansal N, 2009, PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P693

[5]

Bansal N, 2009, LECT NOTES COMPUT SC, V5555, P144, DOI 10.1007/978-3-642-02927-1_14

[6] Online weighted flow time and deadline scheduling [J].

Becchetti, Luca ;

Leonardi, Stefano ;

Marchetti-Spaccamela, Alberto ;

Pruhs, Kirk .

JOURNAL OF DISCRETE ALGORITHMS, 2006, 4 (03) :339-352

[7] Power-aware microarchitecture:: Design and modeling challenges for next-generation microprocessors [J].

Brooks, DM ;

Bose, P ;

Schuster, SE ;

Jacobson, H ;

Kudva, PN ;

Buyuktosunoglu, A ;

Wellman, JD ;

Zyuban, V ;

Gupta, M ;

Cook, PW .

IEEE MICRO, 2000, 20 (06) :26-44

[8]

Bunde D.P., 2006, Proc. ACM Symp. Parallel Alg. and Arch, P190, DOI DOI 10.1145/1148109.1148140

[9]

Chan HL, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P795

[10]

Hardy G., 1952, INEQUALITIES

← 1 2 →