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 language | English |
|---|---|
| Article number | 1350011 |
| Journal | Journal of Interconnection Networks |
| Volume | 14 |
| Issue number | 3 |
| DOIs | |
| State | Published - 1 Jan 2013 |
Fingerprint
Keywords
- Directed acyclic graph (DAG)
- Dynamic programming
- Dynamic voltage and frequency scaling (DVFS)
- Pipeline scheduling
- Synchronous data flow (SDF)
Cite this
}
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 journal › Article › Research › peer-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 -