F.4    SCHEDULING OF EDGES WITH DELAYS

The bit-serial scheduling algorithm described to this point will generate optimal solutions for DFGs that consist of delay-free edges. Many DSP algorithms are inherently recursive and contain delay elements. Purely feed-forward circuits are not also guaranteed to contain all delay-free edges either. Therefore the bit-serial scheduling algorithm must be able to handle edges that contain delays.

Consider the simple circuit described by the following equations:

image

Where a and b are constants, and it is assumed that W = 16, a constant multiplication is assumed to have a latency of 16 u.t., and an addition is assumed to have a latency of 1 u.t. The data-flow diagram for this circuit is shown in Fig. F.6 along with scheduling delays. The triangular symbols represent constant multiplications. If the z−1 operator is removed, one can see that the two delays of 16 and 33 cycles may be amalgamated, but this is not possible with the z−1 operator in the DFG, since the two branches are applied to apparently different signals, x and x[–1]. It is possible to find more complicated examples in which the scheduling of hardware operators will be affected in a nonoptimal way by the presence of the z−1 operators during the scheduling.

A preferable method is to incorporate the word delays right into the linear programming equations. This is done by slightly modifying ...

Get VLSI Digital Signal Processing Systems: Design and Implementation now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.