Energy-aware scheduling for acyclic synchronous data flows on multiprocessors

Dawei Li, Jie Wu

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

Abstract

Synchronous Data Flow (SDF) is a useful computational model in image processing, computer vision, and DSP. Previously, throughput and buffer requirement analyses have been studied for SDFs. In this paper, we address energy-aware scheduling for acyclic SDFs on multiprocessors. The multiprocessor considered here has the capability of Dynamic Voltage and Frequency Scaling (DVFS), which allows processors to operate at different power/energy levels to reduce the energy consumption. An acyclic SDF graph can first be transformed to an equivalent homogeneous SDF graph and then to a Directed Acyclic Graph (DAG) for one iteration of it. We propose pipeline scheduling to address two closely related problems. The first problem is minimizing energy consumption per iteration of the acyclic SDF given a throughput constraint; the second problem is maximizing throughput given an energy consumption constraint per iteration of the acyclic SDF. Since the space of valid total orders of the transformed DAG is exponential, and finding the optimal order is no easy task, we first derive a valid total order, which can be achieved via various strategies, based on the DAG. Given the derived order, we design two dynamic programming algorithms, which produce optimal pipeline scheduling (including pipeline stage partitioning and the frequency setting for each stage), for the two problems, respectively. We also compare the performances of using various strategies to derive a valid total order. Analyses, experiments, and simulations demonstrate the strength of our proposed pipeline scheduling and dynamic programming algorithms.

Original languageEnglish
Article number1350011
JournalJournal of Interconnection Networks
Volume14
Issue number3
DOIs
StatePublished - 1 Jan 2013

Fingerprint

Pipelines
Scheduling
Data flow graphs
Energy utilization
Throughput
Dynamic programming
Electron energy levels
Computer vision
Image processing
Experiments

Keywords

  • Directed acyclic graph (DAG)
  • Dynamic programming
  • Dynamic voltage and frequency scaling (DVFS)
  • Pipeline scheduling
  • Synchronous data flow (SDF)

Cite this

@article{45da4e1e9b3141fc8ec6e154c0b5c090,
title = "Energy-aware scheduling for acyclic synchronous data flows on multiprocessors",
abstract = "Synchronous Data Flow (SDF) is a useful computational model in image processing, computer vision, and DSP. Previously, throughput and buffer requirement analyses have been studied for SDFs. In this paper, we address energy-aware scheduling for acyclic SDFs on multiprocessors. The multiprocessor considered here has the capability of Dynamic Voltage and Frequency Scaling (DVFS), which allows processors to operate at different power/energy levels to reduce the energy consumption. An acyclic SDF graph can first be transformed to an equivalent homogeneous SDF graph and then to a Directed Acyclic Graph (DAG) for one iteration of it. We propose pipeline scheduling to address two closely related problems. The first problem is minimizing energy consumption per iteration of the acyclic SDF given a throughput constraint; the second problem is maximizing throughput given an energy consumption constraint per iteration of the acyclic SDF. Since the space of valid total orders of the transformed DAG is exponential, and finding the optimal order is no easy task, we first derive a valid total order, which can be achieved via various strategies, based on the DAG. Given the derived order, we design two dynamic programming algorithms, which produce optimal pipeline scheduling (including pipeline stage partitioning and the frequency setting for each stage), for the two problems, respectively. We also compare the performances of using various strategies to derive a valid total order. Analyses, experiments, and simulations demonstrate the strength of our proposed pipeline scheduling and dynamic programming algorithms.",
keywords = "Directed acyclic graph (DAG), Dynamic programming, Dynamic voltage and frequency scaling (DVFS), Pipeline scheduling, Synchronous data flow (SDF)",
author = "Dawei Li and Jie Wu",
year = "2013",
month = "1",
day = "1",
doi = "10.1142/S0219265913500114",
language = "English",
volume = "14",
journal = "Journal of Interconnection Networks",
issn = "0219-2659",
publisher = "World Scientific Publishing Co. Pte Ltd",
number = "3",

}

Energy-aware scheduling for acyclic synchronous data flows on multiprocessors. / Li, Dawei; Wu, Jie.

In: Journal of Interconnection Networks, Vol. 14, No. 3, 1350011, 01.01.2013.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Energy-aware scheduling for acyclic synchronous data flows on multiprocessors

AU - Li, Dawei

AU - Wu, Jie

PY - 2013/1/1

Y1 - 2013/1/1

N2 - Synchronous Data Flow (SDF) is a useful computational model in image processing, computer vision, and DSP. Previously, throughput and buffer requirement analyses have been studied for SDFs. In this paper, we address energy-aware scheduling for acyclic SDFs on multiprocessors. The multiprocessor considered here has the capability of Dynamic Voltage and Frequency Scaling (DVFS), which allows processors to operate at different power/energy levels to reduce the energy consumption. An acyclic SDF graph can first be transformed to an equivalent homogeneous SDF graph and then to a Directed Acyclic Graph (DAG) for one iteration of it. We propose pipeline scheduling to address two closely related problems. The first problem is minimizing energy consumption per iteration of the acyclic SDF given a throughput constraint; the second problem is maximizing throughput given an energy consumption constraint per iteration of the acyclic SDF. Since the space of valid total orders of the transformed DAG is exponential, and finding the optimal order is no easy task, we first derive a valid total order, which can be achieved via various strategies, based on the DAG. Given the derived order, we design two dynamic programming algorithms, which produce optimal pipeline scheduling (including pipeline stage partitioning and the frequency setting for each stage), for the two problems, respectively. We also compare the performances of using various strategies to derive a valid total order. Analyses, experiments, and simulations demonstrate the strength of our proposed pipeline scheduling and dynamic programming algorithms.

AB - Synchronous Data Flow (SDF) is a useful computational model in image processing, computer vision, and DSP. Previously, throughput and buffer requirement analyses have been studied for SDFs. In this paper, we address energy-aware scheduling for acyclic SDFs on multiprocessors. The multiprocessor considered here has the capability of Dynamic Voltage and Frequency Scaling (DVFS), which allows processors to operate at different power/energy levels to reduce the energy consumption. An acyclic SDF graph can first be transformed to an equivalent homogeneous SDF graph and then to a Directed Acyclic Graph (DAG) for one iteration of it. We propose pipeline scheduling to address two closely related problems. The first problem is minimizing energy consumption per iteration of the acyclic SDF given a throughput constraint; the second problem is maximizing throughput given an energy consumption constraint per iteration of the acyclic SDF. Since the space of valid total orders of the transformed DAG is exponential, and finding the optimal order is no easy task, we first derive a valid total order, which can be achieved via various strategies, based on the DAG. Given the derived order, we design two dynamic programming algorithms, which produce optimal pipeline scheduling (including pipeline stage partitioning and the frequency setting for each stage), for the two problems, respectively. We also compare the performances of using various strategies to derive a valid total order. Analyses, experiments, and simulations demonstrate the strength of our proposed pipeline scheduling and dynamic programming algorithms.

KW - Directed acyclic graph (DAG)

KW - Dynamic programming

KW - Dynamic voltage and frequency scaling (DVFS)

KW - Pipeline scheduling

KW - Synchronous data flow (SDF)

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

U2 - 10.1142/S0219265913500114

DO - 10.1142/S0219265913500114

M3 - Article

VL - 14

JO - Journal of Interconnection Networks

JF - Journal of Interconnection Networks

SN - 0219-2659

IS - 3

M1 - 1350011

ER -