Loop scheduling for minimizing schedule length and switching activities

Zili Shao, Qingfeng Zhuge, Edwin H.M. Sha, Chantana Chantrapornchai

Research output: Journal article publicationConference articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

Switching activity is one of the most important factors in power dissipation. This paper studies the scheduling problem that minimizes both schedule length and switching activities for applications with loops. We show that to find a schedule that has the minimal switching activities among all minimum-latency schedules with or without resource constraints is NP-complete. Although the minimum latency scheduling problem is polynomial-time solvable if there is no resource constraints or only one function unit, the problem becomes NP-complete when considering switching activities as the second constraint. An algorithm, Power Reduction Rotation Scheduling (PRRS), is proposed. The algorithm attempts to minimize both switching activities and schedule length while performing scheduling and allocation simultaneously. The experimental results show that our algorithm produces effective schedules that give the switching activities 58.5% less compared to the traditional rotation scheduling on average. Our algorithm also shows better performance than the approach that considers scheduling and allocation at the separate phases.
Original languageEnglish
JournalProceedings - IEEE International Symposium on Circuits and Systems
Volume5
Publication statusPublished - 14 Jul 2003
Externally publishedYes
EventProceedings of the 2003 IEEE International Symposium on Circuits and Systems - Bangkok, Thailand
Duration: 25 May 200328 May 2003

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this