Integer linear programming and heuristic techniques for system-level low power scheduling on multiprocessor architectures under throughput constraints

Krishnan Srinivasan, Karam S. Chatha

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


The increased complexity and performance requirements of embedded systems has led to the advent of programmable multiprocessor architectures. The paper presents system-level design techniques for minimizing the power consumption of throughput constrained periodic applications (such as multimedia and network processing) that are mapped to multiprocessor architectures. The paper discusses several design techniques that integrate dynamic voltage scaling (DVS) along with loop transformations (pipelining and unrolling), and apply dynamic power management (DPM) as the final design step. The paper presents an optimal mixed-integer linear programming (MILP) formulation along with three modifications that trade-off solution quality for reduced run times. The paper also presents a heuristic technique along with deterministic (LPPWUdet) and simulated annealing based (LPPWUsa) optimization strategies for solving the system-level low power design problem. The proposed techniques are evaluated by extensive experimentation with multimedia applications (MPEG-1 decoder, JPEG decoder, MP3 encoder), and synthetic taskgraphs (with 10-40 nodes). The proposed techniques are compared with two existing strategies that apply (i) loop pipelining (FP) with DPM but no DVS, and (ii) DVS and DPM but no loop transformations (LPS [Luo, Jha, Power conscious joint scheduling of periodic task graphs and aperiodic tasks in distributed real-time embedded systems, Proceedings of the International Conference on Computer Aided Design, November 2000]), respectively. The optimal MILP formulation, LPPWUdet and LPPWUsa give an average power reduction of 50.68 %, 48.57 % and 49.23 %, respectively, for multimedia applications when compared against FP. While all our techniques are able to satisfy the performance constraints for JPEG and MPEG-1 decoding applications, the LPS technique fails in many cases. Further, the results produced by our deterministic and simulated annealing based techniques for multimedia benchmarks are on an average within 8.04% and 2.75%, respectively, of the optimum solution produced by the MILP based approach. The experimentation with large synthetic taskgraphs demonstrate that the run times of the heuristic techniques scale very well.

Original languageEnglish (US)
Pages (from-to)326-354
Number of pages29
JournalIntegration, the VLSI Journal
Issue number3
StatePublished - Apr 2007


  • Dynamic power management
  • Dynamic voltage scaling
  • Lowpower design

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering


Dive into the research topics of 'Integer linear programming and heuristic techniques for system-level low power scheduling on multiprocessor architectures under throughput constraints'. Together they form a unique fingerprint.

Cite this