19) Loop Transformations

19) Loop Transformations

데이터 의존성 까지 고려 하는 것이다.

Loop variables

-induction variable

변수에서의 모든 변화가 단지 증가 또는 감소가 constant value로 발생 하는 경우

-Basic induction variable

루프당 딱 1번 변화하는 것을 발한다. 1번 루푸당 1번씩 변화하는것

Primary induction variable

basic induction variable이 loop를 제어하면 그것이 Primary induction variable이 된다.

Derived induction variable

its value is decided with a linear function of the basic induction variable

Induction Variable Substitution

필요 없는 것을 loop에서 제거 해버린다.

Before and after induction-variable substitution of KI in the inner loop

INC = 2

KI = 0

Do I = 1, 100

DO J = 1, 100

KI = KI + INC

U(KI) = U(KI) + W(J)

ENDDO

S(I) = U(KI)

ENDDO

KI를 제거 하자.

U(KI + INC * J) = U(KI + INC * J) + W(J)

ENDDO

KI  = KI + 100 * INC

Before and after induction-variable substitution of KI in the outer loop

INC = 2

KI = 0

Do I = 1, 100

DO J = 1, 100

U(KI + INC * J) = U(KI + INC * J) + W(J)

ENDDO

KI  = KI + 100 * INC

S(I) = U(KI)

ENDDO

INC = 2

KI = 0

Do I = 1, 100

DO J = 1, 100

U(KI + 100 * (I-1) * INC + INC * J) = U(KI + 100 * (I-1)  * INC + INC * J) + W(J)

ENDDO

S(I) = U(KI + 100* I * INC)

ENDDO

KI  = KI + 100 * 100* INC

Before and after constant propagation of KI and INC

INC = 2

KI = 0

Do I = 1, 100

DO J = 1, 100

U(KI + 100 * (I-1) * INC + INC * J) = U(KI + 100 * (I-1)  * INC + INC * J) + W(J)

ENDDO

S(I) = U(KI + 100* I * INC)

ENDDO

KI  = KI + 100 * 100* INC

INC = 2

KI = 0

Do I = 1, 100

DO J = 1, 100

U(200 * I - 200 + J * 2) = U(200 * I - 200 + J * 2) + W(J)

ENDDO

S(I) = U(200 * I)

ENDDO

KI  = 20000

Loop Merge

Improve locality

Reduce loop overhead

- 첫번쨰 루푸의 생산결과가 다음 루프에서 바로 사용될 질경우, 이 둘을 병합하면, 지역성을 높일 수 있다.

merge의 가능성을 높이는 기법으로는

enablers, bump, extend/reduce, split, reverse 가 있다.

Tools [1] - loop Bump

Loop extend /reduce