VLSI Digital Signal Processing Systems: Design and Implementation

7.6    SYSTOLIC DESIGN FOR SPACE REPRESENTATIONS CONTAINING DELAYS

Systolic mapping methodology can be modified to accommodate delay elements in the space representation [9]. The precedence constraints in such space representations represent inter-iteration and intra-iteration precedence constraints. This methodology can also be used to for multilevel systolic mapping (for example, for design of 1D systolic arrays for matrix-matrix multiplication).

Fig. 7.21    Dependence graph containing delays.

Consider the DG shown in Fig. 7.21, where I_x, I_y are the indices of nodes x and y, respectively, and w is the number of delay elements from node x to node y. Strictly speaking, the DG containing delay elements should be referred to as data-flow graphs. Nevertheless, we refer to them as DGs here. Before we derive the scheduling constraint for each edge in the DG with delays, we need to define the following parameters:

• N′ : number of nodes mapped to a processor.
• s^Td : If a processor computes the node x at s^TI, then it computes the node displaced from x by d at s^T(I + d).

Now, assume that the iteration l of node x is executed at T_l. Then, the (l + 1)-th iteration of node x is executed at T_l + N′|s^Td|. Therefore, the iteration period is equal to N′|s^Td|. The iteration l of node x is scheduled at time instance S^TI_x + lN′|s^Td|, and the (l + w)-th iteration of node y is scheduled at time instance ...