Combining Coarse-Grained Software Pipelining with DVS for Scheduling Real-Time Periodic Dependent Tasks on Multi-Core Embedded Systems

Hui Liu, Zili Shao, Meng Wang, Junzhao Du, Chun Jason Xue, Zhiping Jia

Abstract

In this paper, we combine coarse-grained software pipelining with DVS (Dynamic Voltage/Frequency Scaling) for optimizing energy consumption of stream-based multimedia applications on multi-core embedded systems. By exploiting the potential of multi-core architecture and the characteristic of streaming applications, we propose a two-phase approach to solve the energy minimization problem for periodic dependent tasks on multi-core processors with discrete voltage levels. With our approach, in the first phase, we propose a coarse-grained task-level software pipelining algorithm called RDAG to transform the periodic dependent tasks into a set of independent tasks based on the retiming technique (Leiserson and Saxe, Algorithmica 6:5–35, 1991). In the second phase, we propose two DVS scheduling algorithms for energy minimization. For single-core processors, we propose a pseudo-polynomial algorithm based on dynamic programming that can achieve optimal solution. For multi-core processors, we propose a novel scheduling algorithm called SpringS which works like a spring and can effectively reduce energy consumption by iteratively adjusting task scheduling and voltage selection. We conduct experiments with a set of benchmarks from E3S (Dick 2008) and TGFF (http://ziyang.ece.northwestern.edu/tgff/) based on the power model of the AMD Mobile Athlon4 DVS processor. The experimental results show that our technique can achieve 12.7% energy saving compared with the algorithms in Zhang et al. (2002) on average.
BibTeX
@article{liu2009combining,
  author = {Hui Liu and Zili Shao and Meng Wang and Junzhao Du and Chun Jason Xue and Zhiping Jia},
  title = {{Combining Coarse-Grained Software Pipelining with DVS for Scheduling Real-Time Periodic Dependent Tasks on Multi-Core Embedded Systems}},
  journal = {J. Signal Process. Syst.},
  year = {2009},
  doi = {10.1007/s11265-008-0315-2},
}

Loading related content...

Figure