O'Reilly logo

VLSI Digital Signal Processing Systems: Design and Implementation by Keshab K. Parhi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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.

image

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required