Systolic Arrays - Signal Processing Systems - page 1099

Fig. 6 Convolution
(localized, single assignment
version)

-1
-1

y1(n,- 1

1
y1(n,k)=y1(n,k-1)+h1(n,k)*x1(n,k)
h1(n,k)=h1(n-1,k)
x1(n,k)=x1(n-1,k-1)

-1

memory locations to be assigned to these intermediate results by expanding the one
dimensional array { y [ n ] } into a two-dimensional array { y 1[ n, k ] } :

y [ n ] → y 1 [ n , k ] such that y 1 [ n ,− 1 ]= 0 , y 1 [ n , k ]= y 1 [ n , k − 1 ]+ h 1 [ n , k ] x 1 [ n , k ]

where the previously localized variables h 1and x 1 are used. With above modifica-
tions, Fig. 5 is reformulated as shown in Fig. 6 .

3.3 Data Dependence and Dependence Graph

An iteration H( j )is dependent on iteration H( i )ifH( j ) will read from a memory
location whose value is last written during execution of iteration H( i ). The corre-
sponding dependence vector d is defined as:

d = j − i .

Amatrix D consisting of all dependence vectors of an algorithm is called
a dependence matrix .This inter-iteration dependence relation imposes a partial
ordering on the execution of the iterative loop nest. From Fig. 6 , three dependence
vectors can be derived:

n
k

n
k

0
1

; n

k

n 1

0

;

− 1

d 1 = − = d 2 = − =

− 1 k

n
k

n 1

1

− 1

d 3 = − = . (10)

k − 1

In the index space, a lattice point whose coordinates fall within the range of the
loop bounds represents the execution of the loop body of the particular loop index
values. The dependence vectors may be represented by directed arcs starting from
the iteration that produces the data to the iteration where the data is needed. Together
with these index points and directed arcs, one has a dependence graph (DG)
representing the computation tasks required of a localized RIA. The corresponding
DG of the convolution algorithm is depicted in Fig. 7 for K = 5and N = 7.