An O(n2) algorithm for computing optimal continuous voltage schedules

Minming Li; Frances F. Yao; Hao Yuan

doi:10.1007/978-3-319-55911-7_28

An O(n²) algorithm for computing optimal continuous voltage schedules

Minming Li^*
, Frances F. Yao
, Hao Yuan

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

12 Citations (Scopus)

Abstract

Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. In the continuous model, the processor can run at any speed, while in the dis-crete model, the processor can only run at finite number of speeds given as input. The current best algorithm for computing the optimal sched-ules for the continuous model runs at O(n² log n) time for scheduling n jobs. In this paper, we improve the running time to O(n²) by speeding up the calculation of s-schedules using a more refined data structure. For the discrete model, we improve the computation of the optimal schedule from the current best O(dn log n) to O(n log max{d, n}) where d is the number of allowed speeds.

Original language	English
Title of host publication	Lecture Notes in Computer Science
Publisher	Springer Verlag
Pages	389-400
Volume	10185 LNCS
ISBN (Print)	9783319559100
DOIs	https://doi.org/10.1007/978-3-319-55911-7_28
Publication status	Published - Apr 2017
Event	14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 - Bern, Switzerland Duration: 20 Apr 2017 → 22 Apr 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10185 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
Place	Switzerland
City	Bern
Period	20/04/17 → 22/04/17

Access Output

10.1007/978-3-319-55911-7_28

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Li, M., Yao, F. F., & Yuan, H. (2017). An O(n²) algorithm for computing optimal continuous voltage schedules. In Lecture Notes in Computer Science (Vol. 10185 LNCS, pp. 389-400). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10185 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-55911-7_28

@inproceedings{b9a4d8c646464cbbbaf308d51820aab6,

title = "An O(n2) algorithm for computing optimal continuous voltage schedules",

abstract = "Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. In the continuous model, the processor can run at any speed, while in the dis-crete model, the processor can only run at finite number of speeds given as input. The current best algorithm for computing the optimal sched-ules for the continuous model runs at O(n2 log n) time for scheduling n jobs. In this paper, we improve the running time to O(n2) by speeding up the calculation of s-schedules using a more refined data structure. For the discrete model, we improve the computation of the optimal schedule from the current best O(dn log n) to O(n log max\{d, n\}) where d is the number of allowed speeds.",

author = "Minming Li and Yao, \{Frances F.\} and Hao Yuan",

year = "2017",

month = apr,

doi = "10.1007/978-3-319-55911-7\_28",

language = "English",

isbn = "9783319559100",

volume = "10185 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "389--400",

booktitle = "Lecture Notes in Computer Science",

address = "Germany",

note = "14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 ; Conference date: 20-04-2017 Through 22-04-2017",

}

Li, M, Yao, FF & Yuan, H 2017, An O(n²) algorithm for computing optimal continuous voltage schedules. in Lecture Notes in Computer Science . vol. 10185 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10185 LNCS, Springer Verlag, pp. 389-400, 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017, Bern, Switzerland, 20/04/17. https://doi.org/10.1007/978-3-319-55911-7_28

An O(n²) algorithm for computing optimal continuous voltage schedules. / Li, Minming; Yao, Frances F.; Yuan, Hao.
Lecture Notes in Computer Science . Vol. 10185 LNCS Springer Verlag, 2017. p. 389-400 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10185 LNCS).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - An O(n2) algorithm for computing optimal continuous voltage schedules

AU - Li, Minming

AU - Yao, Frances F.

AU - Yuan, Hao

PY - 2017/4

Y1 - 2017/4

N2 - Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. In the continuous model, the processor can run at any speed, while in the dis-crete model, the processor can only run at finite number of speeds given as input. The current best algorithm for computing the optimal sched-ules for the continuous model runs at O(n2 log n) time for scheduling n jobs. In this paper, we improve the running time to O(n2) by speeding up the calculation of s-schedules using a more refined data structure. For the discrete model, we improve the computation of the optimal schedule from the current best O(dn log n) to O(n log max{d, n}) where d is the number of allowed speeds.

AB - Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. In the continuous model, the processor can run at any speed, while in the dis-crete model, the processor can only run at finite number of speeds given as input. The current best algorithm for computing the optimal sched-ules for the continuous model runs at O(n2 log n) time for scheduling n jobs. In this paper, we improve the running time to O(n2) by speeding up the calculation of s-schedules using a more refined data structure. For the discrete model, we improve the computation of the optimal schedule from the current best O(dn log n) to O(n log max{d, n}) where d is the number of allowed speeds.

UR - https://www.scopus.com/pages/publications/85018436628

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85018436628&origin=recordpage

U2 - 10.1007/978-3-319-55911-7_28

DO - 10.1007/978-3-319-55911-7_28

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783319559100

VL - 10185 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 389

EP - 400

BT - Lecture Notes in Computer Science

PB - Springer Verlag

T2 - 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017

Y2 - 20 April 2017 through 22 April 2017

ER -