Step Scheduling CSTEP

Scheduling has strong interactions with other parts of the synthesis process because it affects two important factors in the design  

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. 

---

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. 

Control Step Scheduling and Data Path Allocation. Control step scheduling (CSTEP) and data path allocation (EMUCS) are the last of the major phases of the Workbench shown in Figure 9-1. The control step sequencing and data path allocation tools synthesize modules to perform the operations and transfer and store the values it finds in the VT. They assign all the operators in the VT to control steps and bind individual values and operators in the VT to specific modules in the synthesized structure. Only the EMUCS data path allocation tool has been integrated into the CORAL system. 

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. 

Analyzing the Results and Iterating. After the basic pipelined data flow is created, the user should schedule the control steps and simulate a representative set of instructions to estimate the performance of the design. Once control steps have been scheduled using CSTEP, the Workbench s Simulate Instruction command can be used to trace the execution of an instruction and determine the amount of time spent executing the instruction in each stage. However, since the CSTEP control step scheduler does not understand pipelined SELECTs, the results of the simulation must be processed slightly by hand to reflect this. 

In the case of the Workbench, three tools are involved in the synthesis process CSTEP is used to create a control step schedule, EMUCS allocates hardware and binds the data flow objects to that hardware according to the schedule produced by CSTEP, and Busser is used to choose busses for the data path produced by EMUCS. The specific use of partitioning information by these three tools is described in the CSTEP and EMUCS chapters. 

As the scheduler for the Workbench, it is appropriate for CSTEP to use a fixed hardware approach to scheduling rather than a fixed schedule length because it can use the high level structural information provided by the partitioner to help determine an appropriate number of functional units. Chapter 8 describes the synthesis of the Elliptical Filter. The partitioner suggests a 2 partition design which implies a minimum of 2 adders and 2 multipliers, producing a 19 control step schedule, as listed in Table 5-1. This schedule will be used by EMUCS and is used in Chapter 8 to determine a data path for the elliptical filter. 

The performance of a design can be evaluated by considering the control step schedule. The number of csteps is the most basic measure of performance, and it can be applied to any design. One specific performance measure used for the microprocessor designs is the average execution time. The average execution time is the average number of control states executed for each instruction and is computed on the assumption that all execution paths in a routine are equally likely. 

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

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. 

The second design is the flattened description, which was produced by 2 flattening transformation steps. With inline expansion, the CSTEP control schedule shows that the number of cycles required to execute the ORA immediate instruction drops from 16 to 7, a 56% improvement. The SELECT transformations reduce the execution time for the ORA immediate instruction down to 6 cycles. 

CSTEP writes the control step each VT operator is scheduled for in the data structure representing the operator. When EMUCS binds an operator to a specific functional unit, it adds a reference to that module in the operator s data structure. The routine used to record VT to Register-Transfer Level linking information needs only to traverse... 

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

---