Title: Algorithms and analysis of scheduling for loops with minimum switching

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

Addresses: Department of Computing, Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong. ' Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75083, USA. ' Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75083, USA. ' Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75083, USA. ' Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75083, USA. ' Department of Computing, Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

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.

Keywords: switching activity; loops; scheduling algorithms; low power; power reduction; rotation scheduling.

DOI: 10.1504/IJCSE.2006.009939

International Journal of Computational Science and Engineering, 2006 Vol.2 No.1/2, pp.88 - 97

Published online: 03 Jun 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article