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









+ Recent posts