ASAP Scheduling

For AG driven ASAP scheduling, a synthesized attribute called control step is used and the semantic rule corresponding to (1) is ... 

Mobility, ASAP Schedule, and ALAP Schedule for EXAMPLE... 

FCFS, also known as As-Soon-As-Possible, or ASAP) scheduling, list scheduling, and scheduling the critical path first. 

Data Path for EXAMPLE, Using the ASAP Schedule... 

Done by the InHAL module, using a force-directed scheduling algorifiim that tries to schedule the operations so as to balance the distribution of operations using the same hardware resources, without lengthening the schedide. First, both an ASAP schedule... 

Done by the InHAL module, first scheduling the operations on the critical path, then the others. For the others, both an ASAP schedule and an ALAP schedule are generated, and the results combined to indicate the possible control steps for each operation. Operations are distributed when possible to minimize the scheduling of similar operations into the same time step. The MidHAL module is Ihen called to estimate the allocation of operations to functional units, and operations are reassigned when necessary to minimize the scheduling of operations using similar resources into the same time step. Note that there is no mention here of force-directed scheduling. 

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

ASAP scheduling — uses a parallelism evaluator (PE) to assign operations to control steps using a first-come first-served (FCFS) algorithm. 

Generates an ASAP schedule with a functional unit for each operation, a register for each value, and a bus for each edge, and then attempts to fold together pairs of resources (functional units, registers, buses, etc.) that perform the same function, or that can be generalized to perform the same function. If the cost exceeds the constraint, the schedule is lengthened. 

First, an ASAP schedule is constructed, assuming infinite resources, and one cycle per operation. Then optimizations are applied, moving operations to other control steps to reduce the maximum number of operations of each type in any one control step, and grouping operations into functional units so as to have a minimum number of functional units. Uien the scheduler traverses the control step schedule, passing the operations in each control step to the data path allocator. The data path allocator tries to bind those operations using heuristics if it fails, the scheduler tries to delay operations until later control steps, and if that also fails, the user is notified that the resource constraints should be increased. 

The function h determines if the operators reside in the same control step according to a previously determined ASAP schedule, g determines if the operators are of the same type. Thus if two operators might share hardware if placed in the same partition, but doing so would require more hardware in that partition to maintain the same schedule length, the incompatibility measure tends to push these operators into different partitions. At the same time, the data similarity measure tends to group operators that share data. 

Figure 1. DiffEq example a) Differential equation to be solved, b) iterative solution, c) ASAP schedule, d) ALAP schedule.

For the resource-constrained scheduling, we have proposed an optimum ILP formulation. We apply the list scheduling, the ASAP scheduling and the ALAP scheduling to greatly reduce the solution space. We have also extended the formulation to schedule multicycle operations as well as to take constraints on both the number of buses and the number of registers. 

Conflicts are defined as the difference between the number of the ready operations and the number of the available resources. The coirflict reduction scheduling now tries to estimate the number of conflicts of following control steps. The estimation of following conflicts will be effected by an ASAP scheduling without resource restriction and can therefore be made efficiently. The conflict reduction scheduling has been implemented in [KRM088]. Practical experience with this method has especially shown advantages for scarce resources. 

---