Scheduling CSTEP

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. 

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. 

Numerous approaches to scheduling have been reported in the literature ranging from simple local scheduling heuristics to sophisticated global approaches which try to balance performance against resource usage. This section discusses these approaches and compares them to the CSTEP scheduler. 

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. 

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

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. 

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. 

Utilization should be measured across the whole schedule. However, since CSTEP does not know the length of the schedule during the scheduling process, it cannot get an exact measure of utilization for any functional unit. It can consider the utilization of a functional unit over a small window of the schedule, and it uses this window to make decisions about how much hardware to use. 

Partitioning Information and Resource Considerations. It is easy to take partitioning information into account when building the schedule. The information from the partitioner is passed on to CSTEP through the VT. VT allows additional information about its components to be included in the form of qualifiers. The partitioner qualifies each operator with a number indicating the partition in which it belongs. Thus the VT that CSTEP uses contains all of the partitioning information that it needs. 

To take this partitioning information into consideration, CSTEP requires a separate maxlist array for each partition. Then the determination of whether an operator can be scheduled proceeds as described above, but the decision is made relative to the maxlist array that is associated with the partition that contains the operator under consideration. 

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. 

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

The CSTEP schedule lengths and the implied microcode sizes for all designs are shown in Table 8-3. For each design, the table lists ... 

The partitioned VT was fed into CSTEP to obtain a control schedule. It was specified that no more than 1 MINUS, LEQ, or PLUS operation should be scheduled at a time per partition under the assumption that these operations are similar enough to be implemented by the same hardware in the target technology. MULT operations were assumed to be implemented by separate hardware. Therefore a MULT could be scheduled in parallel with any other data operator. 

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

---