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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)


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. ) 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.
Original languageEnglish
Pages (from-to)249-262
Number of pages14
JournalJournal of Signal Processing Systems
Issue number2
Publication statusPublished - 1 Nov 2009


  • Dynamic voltage scaling (DVS)
  • Multi-core
  • Multimedia
  • Periodic dependent tasks
  • Real-time
  • Retiming
  • Scheduling
  • Software pipelining

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Modelling and Simulation
  • Hardware and Architecture


Dive into the research topics of 'Combining coarse-grained software pipelining with dvs for scheduling real-time periodic dependent tasks on multi-core embedded systems'. Together they form a unique fingerprint.

Cite this