AFAP scheduling

Heuristic AFAP scheduling, design iteration, the Intel 8251, a Kalman filter example, the FRISC, and a greatest common divisor algorithm example. 

The scheduling approach in HIS differs from most scheduling techniques traditionally used in high-level synthesis (e.g., list scheduling [21], force-directed scheduling [35]). HIS uses As-Fast-As-Possible (AFAP) scheduling [11] for... 

Constraint intervals depend on the order of the operations in the control-flow graph. Since data-independent operations may be arbitrarily ordered, any valid ordering is possible. AFAP scheduling just uses the given order, which may be obtained, for example, by using a list scheduler. 

Figure 4 shows a finite-state machine example. The AFAP scheduhng in this case requires some operations to be scheduled in more than one state, e.g., operations 7, 8, 9 and 10. More details on AFAP scheduling can be found in [11]. 

If each assignment to a variable is mapped onto a separate register, it may be necessary for AFAP schedules to explicitly store control information, increasing the controller cost (see [4] for a more detailed explanation). 

Uses AFAP path-based scheduling, as described above. After the paths are merged, where there is more than one possible cut, the dataflow analysis is used to choose the cut with the smallest number of live values, thus minimizing the number of registers. 

Global data-flow analysis and path analysis are used for scheduling and allocation. AFAP (as-fast-as-possible) schedules are obtained by scheduling all... 

---