Loop scheduling for real-time DSPs with minimum switching activities on multiple-functional-unit architectures

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)


This paper studies the scheduling problem that minimizes both schedule length and switching activities for applications with loops on multiple-functional-unit architectures. We formally prove that to find a schedule that has the minimal switching activities among all minimum-latency schedules with or without resource constraints is NP-complete. An algorithm, SAMLS (Switching-Activity Minimization Loop Scheduling), is proposed to minimize both schedule length and switching activities. In SAMLS, the best schedule is selected from the ones generated from a given initial schedule by repeatedly rescheduling the nodes with schedule length and switching activities minimization based on rotation scheduling and bipartite matching. The experimental results show our algorithm can greatly reduce both schedule length and switching activities compared with the previous work.
Original languageEnglish
Pages (from-to)53-63
Number of pages11
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publication statusPublished - 1 Dec 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this