An enhanced Co-scheduling method using reduced MS-state diagrams

Abstract

Instruction scheduling methods based on the construction of state diagrams (or automata) have been used for architectures involving deeply pipelined function units. However, the size of the state diagram is prohibitively large, resulting in high execution time and space requirement. We present a simple method for reducing the size of the state diagram by recognizing unique paths of a state diagram. Our experiments show that the number of paths in the reduced state diagram is significantly lower - by 1 to 3 orders of magnitude - compared to the number of paths in the original state diagram. Using the reduced MS-state diagrams, we develop an efficient software pipelining method. The proposed software pipelining algorithm produced efficient schedules and performed better than R.A. Huff's (1993) Slack Scheduling method, and the original Co-scheduling method, in terms of both the initiation interval (II) and the time taken to construct the schedule.