CSTEP Algorithm

During the execution of the CSTEP algorithm, the primary priority function evaluates data-ready operators for scheduling into the current control step csjj. It first considers the impact of this placement on minimum-time constraints. If scheduling an operator into the current control step violates any minimum-time constraints, this placement is considered too early and must be delayed to a later control step. This is... 

Constraint Interactions. List scheduling operates by placing operators into successive control steps. Data-flow constraints, control-flow constraints, and minimum-time constraints can all have the effect of delaying the scheduling of an operator until these constraints are satisfied. If the delayed operator is also subject to a maximum-time constraint, then a possible conflict exists between the two constraints that may not be resolved by the CSTEP algorithm alone. 

This chapter describes CSTEP, a scheduling algorithm that uses techniques drawn from microcode compaction. Unlike other approaches, CSTEP has a primary goal of dealing with interface timing constraints as well as performance and area constraints. 

Fisher [FisherSl] describes the list scheduling algorithm as it is used in microcode compaction. CSTEP uses list scheduling with a number of modifications that support scheduling for synthesis. First, it supports primitive estimation of combinational delay. Second, it uses this estimation to support multiple cycle operators and cascaded operators. Third, it uses a modified priority function in which negative priority values force placement of operators to be delayed. 

CSTEP schedules behavioral operations into control states using a list scheduling algorithm. A propagation delay time is specified in a separate data file for each of the behavioral operators. In addition, a clock period is specified for the design. 

---