Algorithms and analysis of scheduling for loops with minimum switching

Zili Shao, Qingfeng Zhuge, Meilin Liu, Chun Xue, Edwin H.M. Sha, Bin Xiao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

Switching activity and schedule length are the two of the most important factors in power dissipation. This paper studies the scheduling problem that minimises both schedule length and switching activities for applications with loops on multiple functional unit architectures. 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 constraint or only one functional unit (FU), the problem becomes NP-complete when switching activities are considered as the second constraint. An algorithm, Power Reduction Rotation Scheduling (PRRS), is proposed. The algorithm attempts to minimise both switching activities and schedule length while performing scheduling and allocation simultaneously. Compared with the list scheduling, PRRS shows an average of 20.1% reduction in schedule length and 52.2% reduction in bus switching activities. Our algorithm also shows better performance than the approach that considers scheduling and allocation in separate phases.
Original languageEnglish
Pages (from-to)88-97
Number of pages10
JournalInternational Journal of Computational Science and Engineering
Volume2
Issue number1-2
DOIs
Publication statusPublished - 1 Dec 2006

Keywords

  • Loop
  • Low power
  • Scheduling
  • Switching activity

ASJC Scopus subject areas

  • Software
  • Modelling and Simulation
  • Hardware and Architecture
  • Computational Mathematics
  • Computational Theory and Mathematics

Cite this