CSTEP Priority Function

The CSTEP control step scheduler uses list scheduling on a block-by-block basis, with timing constraint evaluation as the priority function. Operations are scheduled into control steps one basic block at a time, with the blocks scheduled in executidepth-first traversal of the control flow graph. For each basic block, data ready operator are considered for placement into the current control step, using a priority function that reflects whether or not that placement will violate timing constraints. Resource limits may be applied to limit the number of operators of a particular type in any one control step. 

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. 

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... 

If the secondary function determines that placement of the current operator would violate the maximum hardware specifications, one of two actions will take place. If the user has chosen to run in "hard mode, the maxlist values are accepted as hard limits that cannot be violated by the scheduler, so a negative value is returned by the priority function so that placement is delayed. If, however, the user has chosen "soft mode," wherein the initial maxlist values imply a lower limit on hardware and CSTEP may choose higher limits according to utilization, the tertiary priority function is invoked. 

---