VLSI Digital Signal Processing Systems: Design and Implementation

F.3    MINIMUM COST SOLUTION

In general, the bit-serial scheduling problem will have many solutions that satisfy the set of inequalities for a given architecture and hence there are many ways to synchronize the circuit. The goal of optimal bit-serial scheduling is to generate a solution that provides the minimal cost, where cost is defined to be the total number of shift-register delays required to properly synchronize the circuit. If a linear cost function can be defined, the minimum cost problem can be easily formulated as a linear programming problem.

Minimizing the total number of synchronization delays required for each edge between functional units of a circuit is not sufficient. Note that there exists the possibility of multiple fanout from any functional unit. Therefore, the delays from a multiple fanout output should be allocated sequentially and not in parallel. Consider a simple case where an output of some operator OP_O is used as an input to several other operators as shown in Fig. F.4. In this figure, the output of OP_O is used as an input to 3 other operators, OP_A, OP_B, and OP_C. As shown in this example, delays of 10, 12, and 25 clock cycles need to be applied to the operand before it is input to the three operators. The total number of delays is equal to 10 + 12 + 25 = 47. Fig. F.5 shows an alternative arrangement of the delays, where the delays are arranged sequentially. The total number of delays in this alternative solution is equal to 25, which is the length of ...