VLSI Digital Signal Processing Systems: Design and Implementation

F.2    OUTLINE OF THE SCHEDULING ALGORITHM

The bit-serial scheduling algorithm consists of assigning a “schedule time” to every operator in a bit-serial architecture. This time represents the time when the operation will nominally take place. Informally, each operator must be scheduled at a time after all of its inputs become available (i.e., they have been generated by a previous operator). The scheduling problem can be formulated as a linear programming problem and because all scheduled time of the operators must be integers, the scheduling algorithm must find the optimal integer solution to this problem.

Consider a pair of operators joined by an edge as shown in Fig. F.3. One of the outputs produced by the operator OP_i is the operand OPND_x. This operand in turn is the input to the operator OP_j (and possibly to others). The scheduled times of operators OP_i and OP_j are denoted by T_i and T_j respectively. The timing specifications of the relevant output and input ports of OP_i and OP_j are denoted by t_i and t_j, respectively.

Fig. F.2    Example of the bit-serial scheduling problem. (a) DFG prior to scheduling. (b) DFG after scheduling showing allocated synchronization registers.

Since OP_i is scheduled at time T_i, the output OPND_x will become available at time T_i + t_i as shown. Further, this same operand will be required as an input to the operator OP_j at time T_j + t_j. By the requirement ...