Energy-aware scheduling for acyclic synchronous data flows on multiprocessors

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.