An ILP formulation for task scheduling on heterogeneous chip multiprocessors

Suleyman Tosun; Nazanin Mansouri; Mahmut Kandemir; Ozcan Ozturk

doi:10.1007/11902140_30

An ILP formulation for task scheduling on heterogeneous chip multiprocessors

Suleyman Tosun
, Nazanin Mansouri
, Mahmut Kandemir
, Ozcan Ozturk

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

9 Scopus citations

Abstract

One of the main difficuties to map an embedded application onto a multiprocessor architecture is that there are multiple ways of this mapping due to several constraints. In this paper, we present an Integer Linear Programming based framework that maps a given application (represented as a task graph) onto a Heterogeneous Chip Multiprocessor architecture. Our framework can be used with several objective functions such as energy, performance, and fallibility (opposite of reliability). We use Dynamic Voltage Scaling (DVS) for reducing energy consumption while we employ task duplication to minimize fallibility. Our experimental results show that over 50% improvements on energy consumption are possible by using DVS, and the fully task duplicated schedules can be achieved under tight performance and energy bounds.

Original language	English (US)
Title of host publication	Computer and Information Sciences - ISCIS 2006
Subtitle of host publication	21th International Symposium, Proceedings
Publisher	Springer Verlag
Pages	267-276
Number of pages	10
ISBN (Print)	3540472428, 9783540472421
DOIs	https://doi.org/10.1007/11902140_30
State	Published - 2006
Event	ISCIS 2006: 21th International Symposium on Computer and Information Sciences - Istanbul, Turkey Duration: Nov 1 2006 → Nov 3 2006

Publication series

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

Other

Other	ISCIS 2006: 21th International Symposium on Computer and Information Sciences
Country/Territory	Turkey
City	Istanbul
Period	11/1/06 → 11/3/06

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/11902140_30

Cite this

Tosun, S., Mansouri, N., Kandemir, M., & Ozturk, O. (2006). An ILP formulation for task scheduling on heterogeneous chip multiprocessors. In Computer and Information Sciences - ISCIS 2006: 21th International Symposium, Proceedings (pp. 267-276). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4263 LNCS). Springer Verlag. https://doi.org/10.1007/11902140_30

Tosun, Suleyman ; Mansouri, Nazanin ; Kandemir, Mahmut et al. / An ILP formulation for task scheduling on heterogeneous chip multiprocessors. Computer and Information Sciences - ISCIS 2006: 21th International Symposium, Proceedings. Springer Verlag, 2006. pp. 267-276 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{309866c4fe554a0185033e40b7e92d6e,

title = "An ILP formulation for task scheduling on heterogeneous chip multiprocessors",

abstract = "One of the main difficuties to map an embedded application onto a multiprocessor architecture is that there are multiple ways of this mapping due to several constraints. In this paper, we present an Integer Linear Programming based framework that maps a given application (represented as a task graph) onto a Heterogeneous Chip Multiprocessor architecture. Our framework can be used with several objective functions such as energy, performance, and fallibility (opposite of reliability). We use Dynamic Voltage Scaling (DVS) for reducing energy consumption while we employ task duplication to minimize fallibility. Our experimental results show that over 50\% improvements on energy consumption are possible by using DVS, and the fully task duplicated schedules can be achieved under tight performance and energy bounds.",

author = "Suleyman Tosun and Nazanin Mansouri and Mahmut Kandemir and Ozcan Ozturk",

year = "2006",

doi = "10.1007/11902140\_30",

language = "English (US)",

isbn = "3540472428",

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

publisher = "Springer Verlag",

pages = "267--276",

booktitle = "Computer and Information Sciences - ISCIS 2006",

address = "Germany",

note = "ISCIS 2006: 21th International Symposium on Computer and Information Sciences ; Conference date: 01-11-2006 Through 03-11-2006",

}

Tosun, S, Mansouri, N, Kandemir, M & Ozturk, O 2006, An ILP formulation for task scheduling on heterogeneous chip multiprocessors. in Computer and Information Sciences - ISCIS 2006: 21th International Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4263 LNCS, Springer Verlag, pp. 267-276, ISCIS 2006: 21th International Symposium on Computer and Information Sciences, Istanbul, Turkey, 11/1/06. https://doi.org/10.1007/11902140_30

An ILP formulation for task scheduling on heterogeneous chip multiprocessors. / Tosun, Suleyman; Mansouri, Nazanin; Kandemir, Mahmut et al.
Computer and Information Sciences - ISCIS 2006: 21th International Symposium, Proceedings. Springer Verlag, 2006. p. 267-276 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4263 LNCS).

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

TY - GEN

T1 - An ILP formulation for task scheduling on heterogeneous chip multiprocessors

AU - Tosun, Suleyman

AU - Mansouri, Nazanin

AU - Kandemir, Mahmut

AU - Ozturk, Ozcan

PY - 2006

Y1 - 2006

N2 - One of the main difficuties to map an embedded application onto a multiprocessor architecture is that there are multiple ways of this mapping due to several constraints. In this paper, we present an Integer Linear Programming based framework that maps a given application (represented as a task graph) onto a Heterogeneous Chip Multiprocessor architecture. Our framework can be used with several objective functions such as energy, performance, and fallibility (opposite of reliability). We use Dynamic Voltage Scaling (DVS) for reducing energy consumption while we employ task duplication to minimize fallibility. Our experimental results show that over 50% improvements on energy consumption are possible by using DVS, and the fully task duplicated schedules can be achieved under tight performance and energy bounds.

AB - One of the main difficuties to map an embedded application onto a multiprocessor architecture is that there are multiple ways of this mapping due to several constraints. In this paper, we present an Integer Linear Programming based framework that maps a given application (represented as a task graph) onto a Heterogeneous Chip Multiprocessor architecture. Our framework can be used with several objective functions such as energy, performance, and fallibility (opposite of reliability). We use Dynamic Voltage Scaling (DVS) for reducing energy consumption while we employ task duplication to minimize fallibility. Our experimental results show that over 50% improvements on energy consumption are possible by using DVS, and the fully task duplicated schedules can be achieved under tight performance and energy bounds.

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

UR - https://www.scopus.com/pages/publications/33845241669#tab=citedBy

U2 - 10.1007/11902140_30

DO - 10.1007/11902140_30

M3 - Conference contribution

AN - SCOPUS:33845241669

SN - 3540472428

SN - 9783540472421

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

SP - 267

EP - 276

BT - Computer and Information Sciences - ISCIS 2006

PB - Springer Verlag

T2 - ISCIS 2006: 21th International Symposium on Computer and Information Sciences

Y2 - 1 November 2006 through 3 November 2006

ER -

Tosun S, Mansouri N, Kandemir M, Ozturk O. An ILP formulation for task scheduling on heterogeneous chip multiprocessors. In Computer and Information Sciences - ISCIS 2006: 21th International Symposium, Proceedings. Springer Verlag. 2006. p. 267-276. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11902140_30

An ILP formulation for task scheduling on heterogeneous chip multiprocessors

Abstract

Publication series

Other

UN SDGs

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this