CSTEP Timing Constraints

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. 

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. 

CSTEP supports interface timing constraints which specify minimum and maximum times between operations. Constraint declarations in CSTEP describe a constraint name, a time interval between operators, and an inequality with a constant that is expressed in either nanoseconds or clock periods. For example, the following maximum-time constraint specifies that operator xl must execute at least 80ns before operator x2 ... 

Constraints on equality and inequality are accepted by CSTEP and treated as combinations of minimum and maximum timing constraints. 

CSTEP schedules operators into control steps one basic block at a time. Basic blocks are scheduled in execution order using an execution-order traversal of the control flow graph. This guarantees that when a timing constraint is expressed on two operators that are in separate basic blocks, the first operator in the constraint is scheduled before the second operator is scheduled. This leaves the second operator to be evaluated for placement in terms of how placement affects the constraint. The ordered scheduling of basic blocks also ensures that inter-basic block data dependencies will be satisfied. 

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

Timing constraints and control flow. Timing constraints may be placed on any pair of operators in a behavioral specification. Evaluation of timing constraints must consider the possibility that two operations may be separated by conditionals and loops. In the case of conditionals, there may be more than one path of execution between the two operators. For example. Figure 5-4 shows two operations separated by a single IF-THEN-ELSE conditional construct. Since the two parts of the conditional may take different amounts of time to execute, any timing constraint on the two operators must be satisfied when either of the two paths is executed. When conditionals are nested, additional paths of execution are possible. CSTEP deals with this possibility in a preprocessing step that enumerates the paths between operators and creates a separate constraint for each path. 

Dealing with loops is a more complicated problem, because in general the number of iterations that a loop executes is not known. Currently, CSTEP evaluates the worst case for minimum-time constraints by assuming that the loop executes a minimum of one iteration. If lower and upper bounds can be supplied by the user, it is straightforward to evaluate both minimum and maximum-time constraints using this worst-case information. 

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 has described the design and implementation of CSTEP, the Workbench scheduling tool. CSTEP was designed for speed and flexibility and supports scheduling with resource constraints and interface timing constraints. 

The Control Step Scheduler (CSTEP) schedules the behavioral operations into control steps, determining the parallelism of the design. It considers the structural partitions suggested by the Architectural Partitioning tool as well as timing and resource constraints specified by the designer. 

The objective function states that we are going to minimize the total number of control steps. Constraint (4) states that no schedule should invoke more than function units of type t. Note that is a constant. Constraints (5) and (6) are the same as those in the time-constrained scheduling. IMo operations should be scheduled after Cstep, as described in constraint (7). 

---