Energy-efficient contention-aware application mapping and scheduling on NoC-based MPSoCs

Dawei Li, Jie Wu

Research output: Contribution to journalArticle

13 Citations (Scopus)

Abstract

We consider the problem of energy-efficient contention-aware application mapping and scheduling on Network-on-Chip (NoC) based multiprocessors. For an application represented by a directed acyclic graph, we present a model where voltage scaling techniques for processors can be combined with frequency tuning techniques for NoC links to save overall system energy consumption. We employ a two-step approach to solve the overall mapping and scheduling problem. First, the application mapping problem is formulated as a quadratic binary programming problem, which aims to minimize the communication energy; we apply a relaxation-based iterative rounding algorithm to solve it. With the mapping achieved, we further consider the application scheduling problem, which aims to find the optimal voltage level for each task of the application and optimal frequency level for each communication of the application to minimize the overall system energy consumption, given the application deadline. To attack the second problem, we first design an algorithm based on the earliest time first scheduling to determine the application's finish time if a voltage and frequency assignment is given; then, we develop a genetic algorithm to search the solution space for the voltage and frequency assignment that minimizes the overall system energy consumption and meets the application's deadline. Through these two steps, we produce a mapping and scheduling that meets the application's deadline, and significantly reduces the overall system energy consumption. Experiments are conducted for a number of randomly generated application graphs, as well as several real application graphs to verify the energy reduction and applicability of the proposed model and algorithms.

Original languageEnglish
Pages (from-to)1-11
Number of pages11
JournalJournal of Parallel and Distributed Computing
Volume96
DOIs
StatePublished - 1 Oct 2016

Fingerprint

MPSoC
Contention
Energy Efficient
Scheduling
Energy Consumption
Energy utilization
Deadline
Voltage
Frequency Assignment
Minimise
Network on chip
Network-on-chip
Scheduling Problem
Electric potential
Directed Acyclic Graph
Communication
Rounding
Graph in graph theory
Multiprocessor
Energy

Keywords

  • Application mapping
  • Dynamic link frequency tuning
  • Dynamic voltage scaling
  • Energy-efficient scheduling
  • Network-on-chip (NoC)

Cite this

@article{3ef540c43b384854a7e08c32d44ecf45,
title = "Energy-efficient contention-aware application mapping and scheduling on NoC-based MPSoCs",
abstract = "We consider the problem of energy-efficient contention-aware application mapping and scheduling on Network-on-Chip (NoC) based multiprocessors. For an application represented by a directed acyclic graph, we present a model where voltage scaling techniques for processors can be combined with frequency tuning techniques for NoC links to save overall system energy consumption. We employ a two-step approach to solve the overall mapping and scheduling problem. First, the application mapping problem is formulated as a quadratic binary programming problem, which aims to minimize the communication energy; we apply a relaxation-based iterative rounding algorithm to solve it. With the mapping achieved, we further consider the application scheduling problem, which aims to find the optimal voltage level for each task of the application and optimal frequency level for each communication of the application to minimize the overall system energy consumption, given the application deadline. To attack the second problem, we first design an algorithm based on the earliest time first scheduling to determine the application's finish time if a voltage and frequency assignment is given; then, we develop a genetic algorithm to search the solution space for the voltage and frequency assignment that minimizes the overall system energy consumption and meets the application's deadline. Through these two steps, we produce a mapping and scheduling that meets the application's deadline, and significantly reduces the overall system energy consumption. Experiments are conducted for a number of randomly generated application graphs, as well as several real application graphs to verify the energy reduction and applicability of the proposed model and algorithms.",
keywords = "Application mapping, Dynamic link frequency tuning, Dynamic voltage scaling, Energy-efficient scheduling, Network-on-chip (NoC)",
author = "Dawei Li and Jie Wu",
year = "2016",
month = "10",
day = "1",
doi = "10.1016/j.jpdc.2016.04.006",
language = "English",
volume = "96",
pages = "1--11",
journal = "Journal of Parallel and Distributed Computing",
issn = "0743-7315",
publisher = "Academic Press Inc.",

}

Energy-efficient contention-aware application mapping and scheduling on NoC-based MPSoCs. / Li, Dawei; Wu, Jie.

In: Journal of Parallel and Distributed Computing, Vol. 96, 01.10.2016, p. 1-11.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Energy-efficient contention-aware application mapping and scheduling on NoC-based MPSoCs

AU - Li, Dawei

AU - Wu, Jie

PY - 2016/10/1

Y1 - 2016/10/1

N2 - We consider the problem of energy-efficient contention-aware application mapping and scheduling on Network-on-Chip (NoC) based multiprocessors. For an application represented by a directed acyclic graph, we present a model where voltage scaling techniques for processors can be combined with frequency tuning techniques for NoC links to save overall system energy consumption. We employ a two-step approach to solve the overall mapping and scheduling problem. First, the application mapping problem is formulated as a quadratic binary programming problem, which aims to minimize the communication energy; we apply a relaxation-based iterative rounding algorithm to solve it. With the mapping achieved, we further consider the application scheduling problem, which aims to find the optimal voltage level for each task of the application and optimal frequency level for each communication of the application to minimize the overall system energy consumption, given the application deadline. To attack the second problem, we first design an algorithm based on the earliest time first scheduling to determine the application's finish time if a voltage and frequency assignment is given; then, we develop a genetic algorithm to search the solution space for the voltage and frequency assignment that minimizes the overall system energy consumption and meets the application's deadline. Through these two steps, we produce a mapping and scheduling that meets the application's deadline, and significantly reduces the overall system energy consumption. Experiments are conducted for a number of randomly generated application graphs, as well as several real application graphs to verify the energy reduction and applicability of the proposed model and algorithms.

AB - We consider the problem of energy-efficient contention-aware application mapping and scheduling on Network-on-Chip (NoC) based multiprocessors. For an application represented by a directed acyclic graph, we present a model where voltage scaling techniques for processors can be combined with frequency tuning techniques for NoC links to save overall system energy consumption. We employ a two-step approach to solve the overall mapping and scheduling problem. First, the application mapping problem is formulated as a quadratic binary programming problem, which aims to minimize the communication energy; we apply a relaxation-based iterative rounding algorithm to solve it. With the mapping achieved, we further consider the application scheduling problem, which aims to find the optimal voltage level for each task of the application and optimal frequency level for each communication of the application to minimize the overall system energy consumption, given the application deadline. To attack the second problem, we first design an algorithm based on the earliest time first scheduling to determine the application's finish time if a voltage and frequency assignment is given; then, we develop a genetic algorithm to search the solution space for the voltage and frequency assignment that minimizes the overall system energy consumption and meets the application's deadline. Through these two steps, we produce a mapping and scheduling that meets the application's deadline, and significantly reduces the overall system energy consumption. Experiments are conducted for a number of randomly generated application graphs, as well as several real application graphs to verify the energy reduction and applicability of the proposed model and algorithms.

KW - Application mapping

KW - Dynamic link frequency tuning

KW - Dynamic voltage scaling

KW - Energy-efficient scheduling

KW - Network-on-chip (NoC)

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

U2 - 10.1016/j.jpdc.2016.04.006

DO - 10.1016/j.jpdc.2016.04.006

M3 - Article

AN - SCOPUS:84971300807

VL - 96

SP - 1

EP - 11

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

SN - 0743-7315

ER -