Scheduling basic block

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. 

Uses ASAP scheduling, calling it AEAP (As Early As Possible), and applying it to one basic block at a time. 

One or more control steps are created for each basic block Rj. Each operation Xa in Bi is assigned to either a single control step cs y or a contiguous range of two or more control steps [ csij2>csij2 ] Scheduling affects the outcome of synthesis in several ways. First, it fixes the order and duration of each operator s execution as it is... 

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. 

In basic list scheduling as is done for microcode compaction, an operator cannot be scheduled in a control step until all of the operators that provide it with inputs are scheduled in previous control steps. An operator that meets these conditions is said to be data ready. To support cascaded operator scheduling, this definition must be modified. An operator can be placed in the same control step as an operator that provides it with an input if the accumulated delay does not exceed the clock period. With these modifications, an operator Xa in basic block Rj is data ready for placement into control step csij when for each input ia,b a one of the following conditions is met ... 

Scheduling is straightforward for this design because of the small basic blocks that make up the data flow. 

The Optimization of Horizontal Microcode Within and Beyond Basic Blocks An Application of Processor Scheduling with Resources. 

The time-constrained scheduling finds its application in real time digital signal processing where the sampling rate dictates how fast a data must be processed. We restrict the input to the time-constrained scheduler be single basic blocks or iterative loops. The resource-constrained scheduler, on the other hand, is applicable to more general applications and accepts inputs that contain multiple loops and/or branches. 

We have developed different algorithms to schedule the operations of a basic block, a pipelined data path and a loop. We propose for each case an optimum ILP formulation followed by a heuristic. 

Our resource-constrained scheduler for a basic block consists of four substeps ... 

As synthesis research progressed, scheduling and binding techniques evolved to relax the basic block restriction by considering also the conditional control-... 

---