An Approximation Algorithm for Energy-Efficient Scheduling on A Chip Multiprocessor

Chuan-Yue Yang; Jian-Jia Chen; Tei-Wei Kuo

doi:10.1109/DATE.2005.51

An Approximation Algorithm for Energy-Efficient Scheduling on A Chip Multiprocessor

Chuan-Yue Yang
, Jian-Jia Chen
, Tei-Wei Kuo

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

103 Citations (Scopus)

Abstract

In the recent decade, voltage scaling has become an attractive feature for many system component designs. In this paper, we consider energy-efficient real-time task scheduling over a chip multiprocessor architecture. The objective is to schedule a set of frame-based tasks with the minimum energy consumption, where all tasks are ready at time 0 and share a common deadline. We show that such a minimization problem is NP-hard and then propose a 2.371-approximation algorithm. The strength of the proposed algorithm was demonstrated by a series of simulations, for which near optimal results were obtained.

Original language	English
Title of host publication	Proceedings - Design, Automation and Test in Europe, DATE 05
Pages	468-473
Volume	I
DOIs	https://doi.org/10.1109/DATE.2005.51
Publication status	Published - Mar 2005
Externally published	Yes
Event	Design, Automation and Test in Europe (DATE '05) - Munich, Germany Duration: 7 Mar 2005 → 11 Mar 2005 https://ieeexplore.ieee.org/xpl/conhome/9609/proceeding

Publication series

Name	Proceedings -Design, Automation and Test in Europe, DATE
ISSN (Print)	1530-1591

Conference

Conference	Design, Automation and Test in Europe (DATE '05)
Abbreviated title	DATE’05
Place	Germany
City	Munich
Period	7/03/05 → 11/03/05
Internet address	https://ieeexplore.ieee.org/xpl/conhome/9609/proceeding

Access Output

10.1109/DATE.2005.51

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{4852658da8f842ec8293332a84023284,

title = "An Approximation Algorithm for Energy-Efficient Scheduling on A Chip Multiprocessor",

abstract = "In the recent decade, voltage scaling has become an attractive feature for many system component designs. In this paper, we consider energy-efficient real-time task scheduling over a chip multiprocessor architecture. The objective is to schedule a set of frame-based tasks with the minimum energy consumption, where all tasks are ready at time 0 and share a common deadline. We show that such a minimization problem is NP-hard and then propose a 2.371-approximation algorithm. The strength of the proposed algorithm was demonstrated by a series of simulations, for which near optimal results were obtained.",

author = "Chuan-Yue Yang and Jian-Jia Chen and Tei-Wei Kuo",

year = "2005",

month = mar,

doi = "10.1109/DATE.2005.51",

language = "English",

isbn = "0769522882",

volume = "I",

series = "Proceedings -Design, Automation and Test in Europe, DATE",

pages = "468--473",

booktitle = "Proceedings - Design, Automation and Test in Europe, DATE 05",

note = "Design, Automation and Test in Europe (DATE '05), DATE{\textquoteright}05 ; Conference date: 07-03-2005 Through 11-03-2005",

url = "https://ieeexplore.ieee.org/xpl/conhome/9609/proceeding",

}

Yang, C-Y, Chen, J-J & Kuo, T-W 2005, An Approximation Algorithm for Energy-Efficient Scheduling on A Chip Multiprocessor. in Proceedings - Design, Automation and Test in Europe, DATE 05. vol. I, 1395607, Proceedings -Design, Automation and Test in Europe, DATE, pp. 468-473, Design, Automation and Test in Europe (DATE '05), Munich, Germany, 7/03/05. https://doi.org/10.1109/DATE.2005.51

An Approximation Algorithm for Energy-Efficient Scheduling on A Chip Multiprocessor. / Yang, Chuan-Yue; Chen, Jian-Jia; Kuo, Tei-Wei.
Proceedings - Design, Automation and Test in Europe, DATE 05. Vol. I 2005. p. 468-473 1395607 (Proceedings -Design, Automation and Test in Europe, DATE).

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

TY - GEN

T1 - An Approximation Algorithm for Energy-Efficient Scheduling on A Chip Multiprocessor

AU - Yang, Chuan-Yue

AU - Chen, Jian-Jia

AU - Kuo, Tei-Wei

PY - 2005/3

Y1 - 2005/3

N2 - In the recent decade, voltage scaling has become an attractive feature for many system component designs. In this paper, we consider energy-efficient real-time task scheduling over a chip multiprocessor architecture. The objective is to schedule a set of frame-based tasks with the minimum energy consumption, where all tasks are ready at time 0 and share a common deadline. We show that such a minimization problem is NP-hard and then propose a 2.371-approximation algorithm. The strength of the proposed algorithm was demonstrated by a series of simulations, for which near optimal results were obtained.

AB - In the recent decade, voltage scaling has become an attractive feature for many system component designs. In this paper, we consider energy-efficient real-time task scheduling over a chip multiprocessor architecture. The objective is to schedule a set of frame-based tasks with the minimum energy consumption, where all tasks are ready at time 0 and share a common deadline. We show that such a minimization problem is NP-hard and then propose a 2.371-approximation algorithm. The strength of the proposed algorithm was demonstrated by a series of simulations, for which near optimal results were obtained.

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

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

U2 - 10.1109/DATE.2005.51

DO - 10.1109/DATE.2005.51

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

SN - 0769522882

SN - 9780769522883

VL - I

T3 - Proceedings -Design, Automation and Test in Europe, DATE

SP - 468

EP - 473

BT - Proceedings - Design, Automation and Test in Europe, DATE 05

T2 - Design, Automation and Test in Europe (DATE '05)

Y2 - 7 March 2005 through 11 March 2005

ER -

An Approximation Algorithm for Energy-Efficient Scheduling on A Chip Multiprocessor

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this