VLSI Digital Signal Processing Systems: Design and Implementation

7.4    SELECTION OF SCHEDULING VECTOR

For any specified projection vector, processor space vector and scheduling vector, the systolic array can be designed using linear mapping technique. In this section, the method of selecting feasible scheduling vectors using scheduling inequalities is discussed. Based on the selected scheduling vector s^T, the projection vector d and the processor space vector p^T can be selected according to equations (7.3) and (7.2). Hence the desired systolic array can be obtained.

7.4.1    Selection of s^T Based on Scheduling Inequalities

Consider the dependence relation X → Y,

where I_x and I_y are the indices of node X and node Y, respectively. The scheduling inequality for this dependence is defined as

where T_x is the time to compute node X and S_x, S_y are the scheduling times for nodes X, Y, respectively. The scheduling equations can be classified into 2 types:

1. Linear scheduling, where

   

2. Affine scheduling, where

   

Using the foregoing definition, we can rewrite the scheduling equation for affine scheduling as

Note that the scheduling equation for linear scheduling ...