Scheduling on power-heterogeneous processors

Susanne Albers; Evripidis Bampis; Dimitrios Letsios; Giorgio Lucarelli; Richard Stotz

doi:10.1007/978-3-662-49529-2_4

Scheduling on power-heterogeneous processors

Susanne Albers, Evripidis Bampis, Dimitrios Letsios, Giorgio Lucarelli, Richard Stotz

Informatik 14 - Lehrstuhl für Algorithmen und Komplexität

Publikation: Beitrag in Buch/Bericht/Konferenzband › Konferenzbeitrag › Begutachtung

8 Zitate (Scopus)

Abstract

We consider the problem of scheduling a set of jobs, each one specified by its release date, its deadline and its processing volume, on a set of heterogeneous speed-scalable processors, where the energyconsumption rate is processor-dependent. Our objective is to minimize the total energy consumption when both the preemption and the migration of jobs are allowed. We propose a new algorithm based on a compact linear programming formulation. Our method approaches the value of the optimal solution within any desired accuracy for a large set of continuous power functions. Furthermore, we develop a faster combinatorial algorithm based on flows for standard power functions and jobs whose density is lower bounded by a small constant. Finally, we extend and analyze the A Verage Rate (AVR) online algorithm in the heterogeneous setting.

Originalsprache	Englisch
Titel	LATIN 2016
Untertitel	Theoretical Informatics - 12th Latin American Symposium, Proceedings
Redakteure/-innen	Gonzalo Navarro, Evangelos Kranakis, Edgar Chávez
Herausgeber (Verlag)	Springer Verlag
Seiten	41-54
Seitenumfang	14
ISBN (Print)	9783662495285
DOIs	https://doi.org/10.1007/978-3-662-49529-2_4
Publikationsstatus	Veröffentlicht - 2016
Veranstaltung	12th Latin American Symposium on Theoretical Informatics, LATIN 2016 - Ensenada, Mexiko Dauer: 11 Apr. 2016 → 15 Apr. 2016

Publikationsreihe

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band	9644
ISSN (Print)	0302-9743
ISSN (elektronisch)	1611-3349

Konferenz

Konferenz	12th Latin American Symposium on Theoretical Informatics, LATIN 2016
Land/Gebiet	Mexiko
Ort	Ensenada
Zeitraum	11/04/16 → 15/04/16

UN SDGs

Dieser Output leistet einen Beitrag zu folgendem(n) Ziel(en) für nachhaltige Entwicklung

Zugriff auf Dokument

10.1007/978-3-662-49529-2_4

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Dieses zitieren

Albers, S., Bampis, E., Letsios, D., Lucarelli, G., & Stotz, R. (2016). Scheduling on power-heterogeneous processors. in G. Navarro, E. Kranakis, & E. Chávez (Hrsg.), LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings (S. 41-54). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 9644). Springer Verlag. https://doi.org/10.1007/978-3-662-49529-2_4

Albers, Susanne ; Bampis, Evripidis ; Letsios, Dimitrios et al. / Scheduling on power-heterogeneous processors. LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings. Hrsg. / Gonzalo Navarro ; Evangelos Kranakis ; Edgar Chávez. Springer Verlag, 2016. S. 41-54 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{317641f5db9747ea8ab1ecef197813c4,

title = "Scheduling on power-heterogeneous processors",

abstract = "We consider the problem of scheduling a set of jobs, each one specified by its release date, its deadline and its processing volume, on a set of heterogeneous speed-scalable processors, where the energyconsumption rate is processor-dependent. Our objective is to minimize the total energy consumption when both the preemption and the migration of jobs are allowed. We propose a new algorithm based on a compact linear programming formulation. Our method approaches the value of the optimal solution within any desired accuracy for a large set of continuous power functions. Furthermore, we develop a faster combinatorial algorithm based on flows for standard power functions and jobs whose density is lower bounded by a small constant. Finally, we extend and analyze the A Verage Rate (AVR) online algorithm in the heterogeneous setting.",

author = "Susanne Albers and Evripidis Bampis and Dimitrios Letsios and Giorgio Lucarelli and Richard Stotz",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 12th Latin American Symposium on Theoretical Informatics, LATIN 2016 ; Conference date: 11-04-2016 Through 15-04-2016",

year = "2016",

doi = "10.1007/978-3-662-49529-2_4",

language = "English",

isbn = "9783662495285",

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

publisher = "Springer Verlag",

pages = "41--54",

editor = "Gonzalo Navarro and Evangelos Kranakis and Edgar Ch{\'a}vez",

booktitle = "LATIN 2016",

}

Albers, S, Bampis, E, Letsios, D, Lucarelli, G & Stotz, R 2016, Scheduling on power-heterogeneous processors. in G Navarro, E Kranakis & E Chávez (Hrsg.), LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bd. 9644, Springer Verlag, S. 41-54, 12th Latin American Symposium on Theoretical Informatics, LATIN 2016, Ensenada, Mexiko, 11/04/16. https://doi.org/10.1007/978-3-662-49529-2_4

Scheduling on power-heterogeneous processors. / Albers, Susanne; Bampis, Evripidis; Letsios, Dimitrios et al.
LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings. Hrsg. / Gonzalo Navarro; Evangelos Kranakis; Edgar Chávez. Springer Verlag, 2016. S. 41-54 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 9644).

Publikation: Beitrag in Buch/Bericht/Konferenzband › Konferenzbeitrag › Begutachtung

TY - GEN

T1 - Scheduling on power-heterogeneous processors

AU - Albers, Susanne

AU - Bampis, Evripidis

AU - Letsios, Dimitrios

AU - Lucarelli, Giorgio

AU - Stotz, Richard

PY - 2016

Y1 - 2016

N2 - We consider the problem of scheduling a set of jobs, each one specified by its release date, its deadline and its processing volume, on a set of heterogeneous speed-scalable processors, where the energyconsumption rate is processor-dependent. Our objective is to minimize the total energy consumption when both the preemption and the migration of jobs are allowed. We propose a new algorithm based on a compact linear programming formulation. Our method approaches the value of the optimal solution within any desired accuracy for a large set of continuous power functions. Furthermore, we develop a faster combinatorial algorithm based on flows for standard power functions and jobs whose density is lower bounded by a small constant. Finally, we extend and analyze the A Verage Rate (AVR) online algorithm in the heterogeneous setting.

AB - We consider the problem of scheduling a set of jobs, each one specified by its release date, its deadline and its processing volume, on a set of heterogeneous speed-scalable processors, where the energyconsumption rate is processor-dependent. Our objective is to minimize the total energy consumption when both the preemption and the migration of jobs are allowed. We propose a new algorithm based on a compact linear programming formulation. Our method approaches the value of the optimal solution within any desired accuracy for a large set of continuous power functions. Furthermore, we develop a faster combinatorial algorithm based on flows for standard power functions and jobs whose density is lower bounded by a small constant. Finally, we extend and analyze the A Verage Rate (AVR) online algorithm in the heterogeneous setting.

UR - http://www.scopus.com/inward/record.url?scp=84961711497&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-49529-2_4

DO - 10.1007/978-3-662-49529-2_4

M3 - Conference contribution

AN - SCOPUS:84961711497

SN - 9783662495285

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

SP - 41

EP - 54

BT - LATIN 2016

A2 - Navarro, Gonzalo

A2 - Kranakis, Evangelos

A2 - Chávez, Edgar

PB - Springer Verlag

T2 - 12th Latin American Symposium on Theoretical Informatics, LATIN 2016

Y2 - 11 April 2016 through 15 April 2016

ER -

Albers S, Bampis E, Letsios D, Lucarelli G, Stotz R. Scheduling on power-heterogeneous processors. in Navarro G, Kranakis E, Chávez E, Hrsg., LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings. Springer Verlag. 2016. S. 41-54. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-49529-2_4

Scheduling on power-heterogeneous processors

Abstract

Publikationsreihe

Konferenz

UN SDGs

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Dieses zitieren