VLSI Digital Signal Processing Systems: Design and Implementation

B.3    TRANSFORMATIONAL SCHEDULING ALGORITHMS

A transformational scheduling algorithm begins with an initial schedule that is either maximally serial or maximally parallel. Transformations are then applied to the initial and intermediate schedules to obtain other schedules until a final solution is produced. The fundamental transformations move the nodes that are in serial (parallel) to locations in the schedule where they are more in parallel (serial). These types of approaches differ from one another by the type of transformations they employ. These scheduling algorithms generally provide better results than the iterative/constructive algorithms.

Fig. B.8    The force-directed scheduling algorithm.

B.3.1    Force Directed Scheduling Algorithm

A good example of transformational scheduling is force-directed scheduling (FDS) developed in the HAL system where its node selection criteria and its node scheduling technique utilize more global information [5]. HAL calculates a force that is exerted between an operation and a particular time step. This force is proportional to the number of operations that can be scheduled to the same functional unit at a particular time step. The scheduling process then minimizes the overall force which tends to balance the concurrency of the nodes in the DFG. Fig. B.8 shows the basic force-directed scheduling algorithm.

As can be seen from Fig. B.8