Loop Blocking

캐시 적중률을 높이기 위해 메모리 참조를 최적화 하는 방법으로 앞서의 예와 같이 단순히 루프 재배치에 의해 메모리 참조를 연속적으로 하기 어려운 경우 또는 캐시보다 훨씬 큰 크기를 가지 는 배열 데이터를 참조해야 할 때 유용하게 사용할 수 있다. 루프 블로킹은 기본적으로 strip mining과 루프 interchange를 통해 데이터 지역성을 최대로 하는 것이 목표이다.

4.3.7.1. Strip Mining

strip mining은 루프 블로킹, Unrolling, Fusion 또는 병렬화를 위해 사용된다. strip mining은 단일 루프를 splitting해서 루프 nest로 만든다. 그 결과 inner 루프는 원래 루프의 한 구역(strip)에 걸쳐 반복되고, outer 루프의 반복에 의해 모든 구역에 걸친 루프 계산이 완료되게 된다. 이때 inner 루프의 반복 횟수를 ‘strip length’라고 한다.

DO I = 1, 10000 A(I) = A(I) * B(I) ENDDO

위의 루프 계산을 strip length = 1000으로 하여 strip mining을 하면 다음과 같다.

DO IOUTER = 1, 10000, 1000

DO ISTRIP = IOUTER, IOUTER+999 A(ISTRIP) = A(ISTRIP) * B(ISTRIP) ENDDO

ENDDO

위 코드에서는 루프 반복이 동일하게 분할 되었지만 경우에 따라서는 전체 루프 반복 횟수가 strip length의 배수가 되지 않는 경우도 있을 것이다.

4.3.7.2. Simple Loop Blocking

캐시보다 큰 배열을 처리하기 위해 루프 블로킹을 수행하는 과정을 살펴보자. 블로킹 작업은 컴파 일러가 의해 수행할 수 있다.

다음 코드에서 배열은 약 16메가바이트 정도의 메모리 공간을 차지한다. 이런 경우 루프 블로킹 을 통해 메모리 접근 속도를 향상 시킬 수 있다.

REAL*8 A(1000,1000), B(1000,1000) REAL*8 C(1000), D(1000)

COMMON /BLK/ A, B, C

…

DO J = 1, 1000 DO I = 1, 1000

A(I,J) = B(J,I) + C(I) + D(J) ENDDO

ENDDO

우선 I 루프에 대해 strip mining을 하면 다음과 같다.

DO J = 1, 1000

DO IOUT = 1, 1000, IBLOCK DO I = IOUT, IOUT+IBLOCK-1 A(I,J) = B(J,I) + C(I) + D(J) ENDDO

ENDDO ENDDO

여기서 IBLOCK이 strip length(또는 block factor라고도 함)가 되며 그 크기는 배열과 캐시 크기 에 의해 결정된다. 다음 과정은 바깥쪽 strip 루프(IOUT)를 가능한 바깥쪽으로 이동시키는 것이다 (interchange).

DO IOUT = 1, 1000, IBLOCK DO J = 1, 1000

DO I = IOUT, IOUT+IBLOCK-1

A(I,J) = B(J,I) + C(I) + D(J)

A(5,2)

END DO

위와 같은 행렬의 곱셈에서 배열 C의 한 원소의 계산은 배열 A의 한 행과 배열 B의 한 열을 필 요로 한다.

C(1, 1) = A(1, 1) * B(1, 1) + A(1, 2) * B(2, 1) + . . . + A(1, L) * B(L, 1) C(2, 1) = A(2, 1) * B(1, 1) + A(2, 2) * B(2, 1) + . . . + A(2, L) * B(L, 1)

…

C(M, N) = A(M, 1) * B(1, N) + A(M, 2) * B(2, N) + . . . + A(M, L) * B(L, N)

●

C

M×N M×L

L×N i^throw

j^thcolumn

= *

●

C

M×N M×L

L×N i^throw

j^thcolumn

= *

그림 4-3. 행렬의 곱셈

따라서 배열 C의 M*N개 원소 계산을 위해 배열 A의 M개 행이 N번 사용되고 배열 B의 N개 행 이 M번 사용 된다. 이와 같은 패턴으로 메모리의 데이터를 꺼내오는 것이 큰 부하를 발생시킨다.

첫 계산에서 A(1,1)과 같이 A(2,1), A(3,1), A(4,1)이 올라온다. 그렇지만 다음 계산에서 A(2,1)이 아니라 A(1,2)가 필요하다. A(2,1)은 L+1번째 계산에서 필요하게 된다. 그래서 L번의 루프 계산 동안 A(2,1)이 캐시에 남아 있게 된다면 배열 A의 공간적 지역성 사용이 가능해 진다. A(3,1)과 A(4,1)은 각각 2L+1, 3L+1 번째 계산에서 필요하고 이때까지 캐시에 남아 있을 수 있다면 좋을 것이다. B(1,1)은 첫 루프 계산에서 캐시로 올라오고 배열 C의 M개 원소 계산 동안 계속 사용 돼 야 한다. B(1,1)이 M*L 루프 반복 동안 캐시에 남아 있으면 시간적 지역성 이용이 가능해 질것이 다.

만약 A, B, C가 캐시 크기에 비해 크다면, 캐시 라인들에 겹쳐 쓰기가 발생해 이러한 공간적, 시 간적 지역성은 감소되거나 아예 사라져 버릴 수도 있다. L가 충분히 크다면 A(2,1)은 L+1번째 루 프 계산 이전에 사라져 버리고 그 만큼 많은 캐시 미스가 발생하게 되는 것이다.

이러한 상황에서 캐시 블로킹을 통해 성능 저하를 방지할 수 있다. 블로킹은 많은 항을 포함하는

계산을 소수의 항을 가지는 일련의 독립된 계산으로 나누는 것이다. 독립적인 계산 각각에 포함되 는 항의 개수는 그 계산에 필요한 모든 데이터가 캐시에 들어갈 수 있도록 설정한다.

C(I, 1) = A(I, 1) * B(1, 1) + A(I, 2) * B(2, 1) + . . . + A(I, L) * B(L, 1)의 계산을 L/KBLOCK 계 산으로 나눈다.

Strip Mining:

DO KOUT = 1, L, KBLOCK

DO K = KOUT, KOUT + (KBLOCK – 1) C(I,1) = C(I,1) + A(I,K) * B(K,1) END DO

END DO

배열 C의 전체 첫 열은 인덱스 I의 반복에 의해 계산 가능하다.

DO I = 1, M

DO KOUT = 1, L, KBLOCK

DO K = KOUT, KOUT + (KBLOCK – 1) C(I,1) = C(I,1) + A(I,K) * B(K,1) END DO

END DO END DO

내포된 루프의 첫 K 반복 계산 동안 B(1,1)은 한 번만 사용되고 A(2,1)은 사용되지 않고 있다.

여기서 다음과 같이 KOUT 루프와 I 루프의 위치를 바꿔주면 배열 A의 공간적 지역성과 B(1,1) 의 시간적 지역성을 개선 시킬 수 있다.

Interchange:

DO KOUT = 1, L, KBLOCK DO I = 1, M

DO K = KOUT, KOUT + (KBLOCK – 1) C(I,1) = C(I,1) + A(I,K) * B(K,1) END DO

END DO END DO

A(2,1)은 KBLOCK 반복 이후에 사용되고 B(1,1)은 모든 KBLOCK 반복 계산에서 사용된다. 만약

M이 충분히 크다면 I 루프에 대한 unrolling 이나 블로킹을 통해 더 나은 공간적, 시간적 지역성 이용 효과를 볼 수 있다.

Unrolling:

DO KOUT = 1, L, KBLOCK DO I = 1, M, IBLOCK

DO K = KOUT, KOUT + (KBLOCK – 1) C(I,1) = C(I,1) + A(I,K) * B(K,1)

C(I + 1,1) = C(I + 1,1) + A(I + 1,K) * B(K,1) C(I + 2,1) = C(I + 2,1) + A(I + 2,K) * B(K,1) ...

C(I+IBLOCK-1, 1) = C(I+IBLOCK-1, 1) + A(I+IBLOCK-1,K) * B(K,1) END DO

END DO END DO

Blocking:

DO IOUT = 1, M, IBLOCK DO KOUT = 1, L, KBLOCK DO J = 1, N

DO I = IOUT, IOUT+IBLOCK-1 DO K = KOUT, KOUT+KBLOCK-1 C(I, J) = C(I, J) + A(I, K) * B(K, J) END DO

END DO END DO END DO

ENDDO ENDDO

이와 같이 캐시 블로킹을 통하여 다음과 같은 효과를 얻을 수 있다.

- K루프에 관하여 B의 공간적 지역성 사용 - I루프에 관하여 B의 시간적 지역성 사용 - I루프에 관하여 A의 공간적 지역성 사용 - J루프에 관하여 A의 시간적 지역성 사용 - I루프에 관하여 C의 공간적 지역성 사용 - K루프에 관하여 C의 시간적 지역성 사용