It is difficult to find a high-level synthesis design that does not involve the scheduling of operations onto logic blocks. Typically, the calculation of an equation is done by sharing hardware for different operations in the equation. For example, a single multiplier can be used for all of the multiply operations and an adder for all the addition operations. This saves the cost of having extra multipliers, but will likely lengthen the time needed to perform the calculations.
Scheduling is deciding which logic blocks will perform which operations and at what time. Any equation is bounded by a precedence ordering. In other words, some operations must be done before others. The goal of scheduling is to minimize the time needed to complete the calculation.
Scheduling is complicated when the calculation is part of a loop. It is further complicated if the calculation is dependent upon results from the previous loop. Finally, it is common that the nature of the circuit will restrict when certain operations can be performed. An example of this is if inputs are only available at a subset of times.
In [1] considers the simple solution of combining retiming and unfolding of loops to speed the calculation. Retiming is reordering the operations so try to minimize delays. Unfolding is the unrolling of loops so that two (or more) loops are calculated in one loop of the DFG. Unfolding will typically allow more flexibility in the scheduling as operations from multiple loops can be performed in parellel (on different logic blocks).
In [2] a more complex algorithm is explored, that of Rotation Scheduling. In Rotation Scheduling a node is rotated by shifting, if possible, delays before the node to after the node. The opposite operation, shifting delays after the node to before the node can also be performed. Shifting of nodes in this manner can make it possible for better schedules to be found. A simple acyclic sheduling algorthm can be used to rescheduling the part of the DFG affected by the rotation.
Finally, [3] modifies Rotation Scheduling to allow for communication sensitive applications. For example, they take into account if a certain operation must be performed at a particular time step. In short, these are additional bounds on the rotation algorithms.
[1] Chao, Liang-Fang and Edwin Hsing-Mean Sha. "Scheduling Data-Flow Graphs via Retiming and Unfolding." IEEE Transactions on Parallel and Distributed Systems, Vol. 8, No. 12, December 1997.
[2] Chao, Liang-Fang, Andrea S. LaPaugh, and Edwin Hsing-Mean Sha. "Rotation Scheduling: A Loop Pipelining Algorithm." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 16, No. 3, March 1997.
[3] Tongsima, Sissades, Nelson L. Passos, and Edwin Hsing-Mean Sha. "Communication Sensitive Rotation Scheduling." Proceedings of the International Conference on Computer Design, October 1994.
Here is a link back to the ECMP 486 Home Page.