18) Loops and Data Dependence

Loops and Data Dependence

Dependency Types

3가지 종류의 의존성이 존재함.

S1: A=B+C

S2: D=A+2

S3: A=E+F

- Flow Dependence (true dependence)  S1S2

새로 어사인된 변수가 다음 구문에서 바로 이용될 때

- Anti-dependence  S2  S3

사용되어 지는 변수가 다음 번에 바로 어사인 되어 버릴때

- Output dependence S1 S3

새로 어사인된 변수가 다음번 구문에서 재차 어사인 되었을때

Dependency Types - LOOP

for k < m

= : k번쨰 인터레이션이 그것의 것에 의존 할때

m 이라는것이 k에 의존할때

k가 m에 의존 할떄

Distance Vector

Normalization Examples

The iteration space can be normalized

The normalization distorts dependences, but is is otherwise preferred to support loop analysis

How to make

Make lower bound 1 (or 0)

Make stride 1

In general,

i' = (i - lowerBound) / I(step)

for (i = 2; i <=100; i = i+3)

Z[i] = 0;

= 100 -2 / 3 = 32

for(i=0; i<=32; i = i++)

Z[ i*3+2  ] =0 

for ( i =3; i<=7; i++)

for(j=6; j >=2; j=j-2)

Z[i,j] = Z[i, j+2] + 1

for( i =0; i<=4; I++)

for(j = 0; j<=2; J++)

i+3, j*-2+6 = Z [i+3, j*-2+8] + 1

Cf. Affine Functions.

어떤 변수들이 i1, i2, i3, i4, i5, i6 이러하 연속 성을 가지고,

1) 상수 들의 합

2) 변수 곱하기 상수 한 것들의 합

Formal Definition of Loop-Carriedness 의존성 문제

▣GCD = 최대공약수

루프 간의 의존성으 공약수로 나눠지 냐 안 나눠지냐로 알 수 있다.

나눌수 없으면 확실히 의존성이 없는 것이며, 나눌수 있다고해서 의존성이 있는 것은 아니다.