Enhanced co-scheduling: A software pipelining method using module-scheduled pipeline theory

Instruction scheduling methods which use the concepts developed by the clas sical pipeline theory have been proposed for architectures involving deeply pipelined function units. These methods rely on the construction of state diagrams (or automatons) to iii efficiently represent the complex resource usage pattern; and (ii) analyze legal initiation sequences, i.e.. those whi ch do not cause a structural hazard. In this paper, we propose a state-diag ram based approach for module scheduling or software pipelining, an instruc tion scheduling method for loops. Our approach adapts the classical pipelin e theory for modulo scheduling, and, hence, the resulting theory is called Modulo-Scheduled pipeline (MS-pipeline) theory. The state diagram, called t he Modulo-Scheduled (MS) state diagram is helpful in identifying legal init iation or latency sequences, that improve the number of instructions initia ted in a pipeline. An efficient method, called Co-scheduling; which uses th e legal initiation sequences as guidelines for constructing software pipeli ned schedules has bren proposed in this paper. However, the complexity of t he constructed MS-stair diagram limits the usefulness of our Co scheduling method. Further analysis of the MS-pipeline theory. reveals that the space complexity of the MS-state diagram can be significantly reduced by identify ing primary paths. We develop the underlying theory to establish that the r educed MS-stale diagram consisting only of primary paths is complete; i.e., it retains ail the useful information represented by the original state di agram as far as scheduling of operations is concerned. Our experiments show that the number of paths in the reduced state diagram is significantly low er-by 1 to 3 orders of magnitude-compared to the number of paths in the ori ginal state diagram. The reduction in the state diagram Facilitate the Co-s cheduling method to consider multiple initiations sequences, and hence obta in more efficient schedules. We call the resulting method, enhanced Co-sche duling. The enhanced Co-scheduling method produced efficient schedules when tested on a set of 1153 benchmark loops, Further the schedules produced by this method are significantly better than those produced by Huff's Slack S cheduling method, a competitive software pipelining method, in terms of bot h the initiation interval of the schedules and the time taken to construct them.