Lecture Summary for 2 April 2014

DEPENDENCE ANALYSIS OF DATA ARRAYS

Iteration space:

The n- dimensional discrete cartesian space for n-deep loops is called an iteration space. the iteration is represented as coordinates in the iteration space.

Dependence equation

f(alpha) = g(beta).

The SIV test:

An SIV subscript for index i is said to be strong if it has the form

(ai + C1 , ai' + C2).

for strong SIV subscripts, define dependence distance as:

d = i'-i = (C1-C2)/a

A(a(alpha) + c1)/A(a(beta) + c2) = K

Distance, d = (c1 - c2)/a

for i = 1 to n

 a(i+1) = 2*a(i)

a2 = 2*a1  [First iteration]

a3 = 2*a2  [Second]

a4 = 2*a3  [Third]

We find that there exists flow dependence.

Graph for (alpha) vs (beta):

Let us consider another example:

for i = 1 to n

 a(i) = a(i+2)

Opening up the for-loop as before,

a(1) = a(3)  [First iteration]

a(2) = a(4)  [Second]

a(3) = a(5)  [Third]

We find that anti-flow dependence exists for a3 in the first and third iterations. Similarly a2 will have the same dependence in the second and fourth iterations.

For flow dependency and anti-flow dependency the distance should be less than the difference of upper limit and lower limit.

d  <   (U-L)   where,

d = distance, U= upper limit, L= lower limit

Weak Zero SIV

weak SIV subscript has the form:

(a1i + c1 , a2i`+c2)

i = (C2-C1)/a1

example:

a(i+1) = a(3)

a(2) = a(3)

a(3) = a(3)

a(4) = a(3)

We notice that in this case, both flow and anti-flow dependencies exist. We can use a technique called peeling to parallelize this code.

Consider the following code:

do i =1 → n

 a(i) = a(i) + a(n)

New Algo:

a(1) = a(1) + a(n)

do i = 2 → n-1

 a(i) = a(1) + a(n)

end

a(n) = a(1) + a(n);

Weak Crossing SIV

do i = 1,10

a(i) = a(-i + 10)

a(1)= a(9) [First iteration]

a(2) = a (8)

a(3) = a(7)

a(4)= a(6)

a(5) = a (5)

a(6) = a (4)

a (7) = a (3)

a (8) = a(2)

a(9) = a(1)

Here, the crossover point comes for   i = 5.

Reference:

Advanced Computer Architecture (Kai Hwang)

Submitted by:

Sunil Gupta (347/CO/11)

SuMit Dr@ll  (344/CO/11)