Algorithms and analysis of scheduling for loops with minimum switching. (5th June 2006)

• Record Type: Journal Article
• Authors: Shao, Zili; Zhuge, Qingfeng; Liu, Meilin; Xue, Chun; Sha, Edwin; Xiao, Bin
• Is Part Of: International journal of computational science and engineering. Volume 2:Number 1/2(2006)
• Page Start: 88
• Page End: 97
• Publication Date: 2006-06-05
• Subjects: switching activity -- loops -- scheduling algorithms -- low power -- power reduction -- rotation scheduling; Computer science -- Mathematics -- Periodicals; Computer simulation -- Mathematical aspects -- Periodicals; Computational intelligence -- Periodicals; 004.015105
• Languages: English
• ISSNs: 1742-7185

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.