CSTEP

Common terminology criteria for adverse events v3.0, DTCD, NCI, NIH, DHHS. Publish date August 9, 2006 (http /cstep.cancer.gov). 

VHDL, using CAD Language Systems, Inc. s parser. Transformations / APARTY / CSTEP / EMUCS Synthesis Path Internal Behavioral Representation... 

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. 

Traneformation / APARTY / CSTEP / EMUCS Synthesis Path... 

Architectural partitioning, guiding CSTEP, EMUCS and Busser, and a fifth-order digital elliptic wave filter example. 

Architectural partitionii, g ding CSTEP, EMUCS and Busser, a fifth-order digital elliptic wave filter example, a Kalman filter example, the BTL310, an ADPCM, the MCS6502, and the IBM System/370. 

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. 

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. 

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. 

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. 

These conditions can be extended to consider operators that are not actually bound to hardware, but that might be implemented by the same hardware unit. CSTEP does not operate on pre-bound hardware, but it can determine whether operators are candidates to share hardware and treat them appropriately. CSTEP does not consider register sharing explicitly. 

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. 

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. 

---