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.
|Number of pages||11|
|Journal||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Publication status||Published - 1 Dec 2004|
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)