Power-aware scheduling of conditional task graphs in real-time multiprocessor systems

Dongkun Shin; Jihong Kim

doi:10.1109/LPE.2003.1231938

Power-aware scheduling of conditional task graphs in real-time multiprocessor systems

Dongkun Shin
, Jihong Kim

Seoul National University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

48 Scopus citations

Abstract

We propose a novel power-aware task scheduling algorithm for DVS-enabled real-time multiprocessor systems. Unlike the existing algorithms, the proposed DVS algorithm can handle conditional task graphs (CTGs) which model more complex precedence constraints. We first propose a condition-unaware task scheduling algorithm integrating the task ordering algorithm for CTGs and the task stretching algorithm for unconditional task graphs. We then describe a condition-aware task scheduling algorithm which assigns to each task the start time and the clock speed, taking account of the condition matching and task execution profiles. Experimental results show that the proposed condition-aware task scheduling algorithm can reduce the energy consumption by 50% on average over the non-DVS task scheduling algorithm.

Original language	English
Title of host publication	ISLPED 2003 - Proceedings of the 2003 International Symposium on Low Power Electronics and Design
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	408-413
Number of pages	6
ISBN (Electronic)	158113682X
DOIs	https://doi.org/10.1109/LPE.2003.1231938
State	Published - 2003
Externally published	Yes
Event	2003 International Symposium on Low Power Electronics and Design, ISLPED 2003 - Seoul, Korea, Republic of Duration: 25 Aug 2003 → 27 Aug 2003

Publication series

Name	Proceedings of the International Symposium on Low Power Electronics and Design
Volume	2003-January
ISSN (Print)	1533-4678

Conference

Conference	2003 International Symposium on Low Power Electronics and Design, ISLPED 2003
Country/Territory	Korea, Republic of
City	Seoul
Period	25/08/03 → 27/08/03

Keywords

Algorithm design and analysis
Clocks
Computer science
Dynamic voltage scaling
Energy consumption
Multiprocessing systems
Power engineering and energy
Real time systems
Scheduling algorithm
Voltage control

Access to Document

10.1109/LPE.2003.1231938

Cite this

Shin, D., & Kim, J. (2003). Power-aware scheduling of conditional task graphs in real-time multiprocessor systems. In ISLPED 2003 - Proceedings of the 2003 International Symposium on Low Power Electronics and Design (pp. 408-413). Article 1231938 (Proceedings of the International Symposium on Low Power Electronics and Design; Vol. 2003-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/LPE.2003.1231938

Shin, Dongkun ; Kim, Jihong. / Power-aware scheduling of conditional task graphs in real-time multiprocessor systems. ISLPED 2003 - Proceedings of the 2003 International Symposium on Low Power Electronics and Design. Institute of Electrical and Electronics Engineers Inc., 2003. pp. 408-413 (Proceedings of the International Symposium on Low Power Electronics and Design).

@inproceedings{7be9c38138924b73946df854e512f735,

title = "Power-aware scheduling of conditional task graphs in real-time multiprocessor systems",

abstract = "We propose a novel power-aware task scheduling algorithm for DVS-enabled real-time multiprocessor systems. Unlike the existing algorithms, the proposed DVS algorithm can handle conditional task graphs (CTGs) which model more complex precedence constraints. We first propose a condition-unaware task scheduling algorithm integrating the task ordering algorithm for CTGs and the task stretching algorithm for unconditional task graphs. We then describe a condition-aware task scheduling algorithm which assigns to each task the start time and the clock speed, taking account of the condition matching and task execution profiles. Experimental results show that the proposed condition-aware task scheduling algorithm can reduce the energy consumption by 50\% on average over the non-DVS task scheduling algorithm.",

keywords = "Algorithm design and analysis, Clocks, Computer science, Dynamic voltage scaling, Energy consumption, Multiprocessing systems, Power engineering and energy, Real time systems, Scheduling algorithm, Voltage control",

author = "Dongkun Shin and Jihong Kim",

note = "Publisher Copyright: {\textcopyright} 2003 ACM.; 2003 International Symposium on Low Power Electronics and Design, ISLPED 2003 ; Conference date: 25-08-2003 Through 27-08-2003",

year = "2003",

doi = "10.1109/LPE.2003.1231938",

language = "English",

series = "Proceedings of the International Symposium on Low Power Electronics and Design",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "408--413",

booktitle = "ISLPED 2003 - Proceedings of the 2003 International Symposium on Low Power Electronics and Design",

}

Shin, D & Kim, J 2003, Power-aware scheduling of conditional task graphs in real-time multiprocessor systems. in ISLPED 2003 - Proceedings of the 2003 International Symposium on Low Power Electronics and Design., 1231938, Proceedings of the International Symposium on Low Power Electronics and Design, vol. 2003-January, Institute of Electrical and Electronics Engineers Inc., pp. 408-413, 2003 International Symposium on Low Power Electronics and Design, ISLPED 2003, Seoul, Korea, Republic of, 25/08/03. https://doi.org/10.1109/LPE.2003.1231938

Power-aware scheduling of conditional task graphs in real-time multiprocessor systems. / Shin, Dongkun; Kim, Jihong.
ISLPED 2003 - Proceedings of the 2003 International Symposium on Low Power Electronics and Design. Institute of Electrical and Electronics Engineers Inc., 2003. p. 408-413 1231938 (Proceedings of the International Symposium on Low Power Electronics and Design; Vol. 2003-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Power-aware scheduling of conditional task graphs in real-time multiprocessor systems

AU - Shin, Dongkun

AU - Kim, Jihong

PY - 2003

Y1 - 2003

N2 - We propose a novel power-aware task scheduling algorithm for DVS-enabled real-time multiprocessor systems. Unlike the existing algorithms, the proposed DVS algorithm can handle conditional task graphs (CTGs) which model more complex precedence constraints. We first propose a condition-unaware task scheduling algorithm integrating the task ordering algorithm for CTGs and the task stretching algorithm for unconditional task graphs. We then describe a condition-aware task scheduling algorithm which assigns to each task the start time and the clock speed, taking account of the condition matching and task execution profiles. Experimental results show that the proposed condition-aware task scheduling algorithm can reduce the energy consumption by 50% on average over the non-DVS task scheduling algorithm.

AB - We propose a novel power-aware task scheduling algorithm for DVS-enabled real-time multiprocessor systems. Unlike the existing algorithms, the proposed DVS algorithm can handle conditional task graphs (CTGs) which model more complex precedence constraints. We first propose a condition-unaware task scheduling algorithm integrating the task ordering algorithm for CTGs and the task stretching algorithm for unconditional task graphs. We then describe a condition-aware task scheduling algorithm which assigns to each task the start time and the clock speed, taking account of the condition matching and task execution profiles. Experimental results show that the proposed condition-aware task scheduling algorithm can reduce the energy consumption by 50% on average over the non-DVS task scheduling algorithm.

KW - Algorithm design and analysis

KW - Clocks

KW - Computer science

KW - Dynamic voltage scaling

KW - Energy consumption

KW - Multiprocessing systems

KW - Power engineering and energy

KW - Real time systems

KW - Scheduling algorithm

KW - Voltage control

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

U2 - 10.1109/LPE.2003.1231938

DO - 10.1109/LPE.2003.1231938

M3 - Conference contribution

AN - SCOPUS:1542329196

T3 - Proceedings of the International Symposium on Low Power Electronics and Design

SP - 408

EP - 413

BT - ISLPED 2003 - Proceedings of the 2003 International Symposium on Low Power Electronics and Design

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2003 International Symposium on Low Power Electronics and Design, ISLPED 2003

Y2 - 25 August 2003 through 27 August 2003

ER -

Shin D, Kim J. Power-aware scheduling of conditional task graphs in real-time multiprocessor systems. In ISLPED 2003 - Proceedings of the 2003 International Symposium on Low Power Electronics and Design. Institute of Electrical and Electronics Engineers Inc. 2003. p. 408-413. 1231938. (Proceedings of the International Symposium on Low Power Electronics and Design). doi: 10.1109/LPE.2003.1231938

Power-aware scheduling of conditional task graphs in real-time multiprocessor systems

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this