Cache Thrashing

캐시 thrashing은 프로그램에서 자주 사용되는 두 개 혹은 그 이상의 데이터가 동일한 캐시 주소 에 사상되는 상황에서 발생하게 된다. 캐시 thrashing이 발행하면 필요한 데이터가 캐시에 올라올 때마다 이미 올라와 있는 또 다른 필요 데이터를 덮어쓰게 돼 캐시실패를 유발하고 데이터 재사 용에 나쁜 영향을 준다.

1M의 크기를 가지는 직접 사상 캐시 시스템에서 아래 코드를 실행하는 경우에 대해 살펴보자.

INTEGER, PARAMETER :: N = 128*512 REAL(8), DIMENSION(N) :: A, B, C COMMON/BLOK/A,C,B

. . .

DO I = 1, N

C(I) = A(I) + B(I) ENDDO

세 배열 A, B, C 각각 8*(128*512) = 524288 bytes = 0.5 M의 크기를 가진다. 그리고, 각 배열은 common block의 사용으로 A, C, B 순서로 메모리에 연속적으로 위치한다. 직접 사상 1M 캐시를 가지는 시스템에서 코드를 실행한다면 아래 그림에서와 같이 배열 A와 B의 각 원소는 캐시 내에 서 동일한 주소를 가지게 된다.

0.5MB

0.5MB

0.5MB 0.5MB

0.5MB

A C B

Main memory 1 MB cache

0.5MB

0.5MB

0.5MB 0.5MB

0.5MB

A C B

Main memory 1 MB cache

그림 4-4. Cache Thrashing

배열 A, B는 루프의 반복마다 서로를 thrash 한다. 이처럼 한 캐시라인이 다른 캐시라인에 의해 overwrite 되는 것을 캐시 thrashing이라고 한다.

캐시라인 크기가 32바이트(64바이트)인 경우 세 개(일곱 개)의 8바이트 데이터가 추가적으로 메 모리에서 꺼내어져 캐시에 올라온다. 추가적으로 올라온 데이터가 사용될 때까지 캐시에 있도록 해서 캐시실패를 줄여야 하지만 thrashing이 발생하면 추가적으로 올라온 데이터는 참조되기 전 에 삭제돼 버려, 결국 메모리 성능저하의 원인이 된다.

INTEGER, PARAMETER :: N = 128*512 REAL(8), DIMENSION(N) :: A, B, C COMMON/BLOK/C, A, B

. . .

위의 코드에서도 여전히 캐시 thrashing은 발생한다. load뿐 아니라 store 과정에서도 캐시라인에 대한 겹쳐 쓰기 문제가 남아있기 때문이며, C(j)가 B(j)를 겹쳐 쓰게 되는 문제가 있다.

4.4.1.1. Cache Padding

캐시 thrashing은 두 가지 방식의 캐시 padding에 의해 최소화 될 수 있다.

- 데이터 정렬 padding

- 배열 내부 padding

= array B shifted 32 bytes into C

0.5MB

= array B shifted 32 bytes into C

그림 4-5. 데이터 정렬 padding

common block에 배열 fake를 삽입함으로써 배열 B의 캐시주소를 배열 C의 주소로부터 32바이 트 아래로 이동 시키는 효과를 볼 수 있다. 이 32바이트 이동이 같은 인덱스를 가지는 두 개의

원소가 동일한 캐시주소를 공유하는 것을 방지해서 전체 캐시라인이 참조되기 전까지 캐시 겹쳐 쓰기가 발행하지 않게 된다. 그래서 배열 A, B, C에서 각각 4개의 8바이트 원소가 캐시에 올려지 면 모두 참조되고 난 후 삭제된다.

padding은 최신의 컴파일러에서 자동적으로 처리된다. 컴파일러는 배열 원소의 크기, 캐시라인의 크기, 메모리 크기 등을 고려해 pad 크기 결정하게 된다. padding을 수행한 컴파일러는 명시적인 리포트를 통해 pad된 캐시 블록과 더불어 그 크기를 보여줄 것이다.

② 배열 내부 padding

padding의 또 다른 방법은 한 배열의 캐시주소를 이동시켜 캐시 thrashing 발생을 제거하는 것으 로 배열 padding이라고 한다.

INTEGER, PARAMETER :: N = 128*512 REAL(8), DIMENSION(N) :: B, C

REAL(8), DIMENSION(N+4) :: A COMMON/BLOK/A,C,B

. . .

DO I = 1, N

C(I) = A(I) + B(I) ENDDO

위의 코드에서와 같이 배열 A의 길이를 4개(32바이트) 더 늘여 놓음으로써 배열 B가 배열 A와 캐시주소를 공유하지 못하도록 하는 padding의 효과를 얻을 수 있다. 배열 A 대신 배열 C의 크 기를 32바이트 증가시키는 것도 같은 효과를 줄 것이다.