Online dynamic power management with hard real-time guarantees

被引：8

作者：

Chen, Jian-Jia ^{[1
]}

Kao, Mong-Jen ^{[2
]}

Lee, D. T. ^{[2
,3
]}

Rutter, Ignaz ^{[1
]}

Wagner, Dorothea ^{[1
]}

机构：

[1] Karlsruhe Inst Technol, Fac Informat, D-76021 Karlsruhe, Germany

[2] Acad Sinica, Inst Informat Sci, Taipei, Taiwan

[3] Natl Chung Hsing Univ, Dept Comp Sci & Informat Engn, Taichung 40227, Taiwan

来源：

THEORETICAL COMPUTER SCIENCE | 2015年 / 595卷

关键词：

Online energy-efficient scheduling; Dynamic power management; ALGORITHMS; ENERGY; TASKS;

D O I：

10.1016/j.tcs.2015.06.014

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the problem of online dynamic power management that provides hard real-time guarantees for multi-processor systems. In this problem, a set of jobs, each associated with an arrival time, a deadline, and an execution time, arrives to the system in an online fashion. The objective is to compute a non-migrative preemptive schedule of the jobs and a sequence of power on/off operations of the processors so as to minimize the total energy consumption while ensuring that all the deadlines of the jobs are met. We assume that we can use as many processors as necessary. In this paper we examine the complexity of this problem and provide online strategies that lead to practical energy-efficient solutions for real-time multi-processor systems. First, we consider the case for which we know in advance that the set of jobs can be scheduled feasibly on a single processor. We show that, even in this case, the competitive ratio of any online algorithm is at least 2.06. On the other hand, we give a 4-competitive online algorithm that uses at most two processors. For jobs with unit execution times, the competitive ratio of this algorithm improves to 3.59. Second, we relax our assumption by considering as input multiple streams of jobs, each of which can be scheduled feasibly on a single processor. We present a trade-off between the energy-efficiency of the schedule and the number of processors to be used. More specifically, for k given job streams and h processors with h > k, we give a scheduling strategy such that the energy usage is at most 4. inverted right perpendicular k/h-k inverted left perpendicular times that used by any schedule which schedules each of the k streams on a separate processor. Finally, we drop the assumptions on the input set of jobs. We show that the competitive ratio of any online algorithm is at least 2.28, even for the case of unit job execution times for which we further derive an O(1)-competitive algorithm. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：46 / 64

页数：19

共 32 条

[1] Race to Idle: New Algorithms for Speed Scaling with a Sleep State [J].

Albers, Susanne ;

Antoniadis, Antonios .

ACM TRANSACTIONS ON ALGORITHMS, 2014, 10 (02)

[2]

Albers S, 2011, SPAA 11: PROCEEDINGS OF THE TWENTY-THIRD ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, P279

[3]

Anand S, 2011, LECT NOTES COMPUT SC, V6755, P232, DOI 10.1007/978-3-642-22006-7_20

[4]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[5]

[Anonymous], 1983, THESIS MIT CAMBRIDGE

[6]

Antoniadis A., 2015, Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, P1102

[7] Optimal power-down strategies [J].

Augustine, John ;

Irani, Sandy ;

Swamy, Chaitanya .

SIAM JOURNAL ON COMPUTING, 2008, 37 (05) :1499-1516

[8] Speed scaling to manage energy and temperature [J].

Bansal, Nikhil ;

Kimbrel, Tracy ;

Pruhs, Kirk .

JOURNAL OF THE ACM, 2007, 54 (01)

[9] Scheduling Unit Tasks to Minimize the Number of Idle Periods: A Polynomial Time Algorithm for Offline Dynamic Power Management [J].

Baptiste, Philippe .

PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, :364-367

[10]

Baptiste P, 2007, LECT NOTES COMPUT SC, V4698, P136

← 1 2 3 4 →