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 sT, the projection vector d and the processor space vector pT can be selected according to equations (7.3) and (7.2). Hence the desired systolic array can be obtained.
Consider the dependence relation X → Y,
where Ix and Iy are the indices of node X and node Y, respectively. The scheduling inequality for this dependence is defined as
where Tx is the time to compute node X and Sx, Sy are the scheduling times for nodes X, Y, respectively. The scheduling equations can be classified into 2 types:
Using the foregoing definition, we can rewrite the scheduling equation for affine scheduling as
Note that the scheduling equation for linear scheduling ...