지역성이란 ?
캐시가 효율적으로 동작하려면, 캐시에 저장할 데이터가 지역성을 가져야 한다. 지역성이란 데이터 접근이 시간적, 혹은 공간적으로 가깝게 일어나는 것을 의미한다. (위키백과)
시간지역성
- 한번 참조된 메모리 위치는 가까운 미래에 다시 여러 번 참조될 가능성이 높음
- 동일한 변수들을 반복적으로 참조하는 프로그램은 좋은 시간 지역성을 누린다.
공간지역성
- 어떤 메모리가 일단 참조되면, 이 프로그램은 가까운 미래에 근처의 메모리 위치를 참조할 가능성이 높음
- 데이터가 저장되어있는 순서대로 참조하는 프로그램은 좋은 공간 지역성을 누린다.
캐시 친화적 코드 작성을 위한 기본적인 접근법
-
공통적인 경우를 빠르게 동작하게 만들어라.
-> 대부분의 시간을 소모하는 핵심 함수의 내부 루프에 집중하고 나머지는 무시한다. -
각 내부 루프의 캐시 미스 수를 최소화하라.
캐시 친화적인 행렬 곱셈
for i in range(n):
for j in range(n):
sum = 0
for k in range(n):
sum += A[i][k]*B[k][j]
C[i][j] = sum가장 일반적으로 n x n 행렬의 곱셈을 위해 작성하는 코드이다.
과연 이 코드는 캐시 친화적인 코드일까?
결론부터 말하자면 아주 나쁜 코드는 아니지만 더 캐시 친화적인 코드로 작성할 수 있다.
위 접근법을 통해 어떻게 루프를 배치했을 때 가장 많이 실행되는 내부 루프의 캐시 미스 횟수가 최소가 되는지 확인해보자.
먼저 측정을 위해 몇 가지 가정을 해보자.
- 각 배열은 int의 n x n 배열이며, sizeof(int) = 4이다.
- 32 바이트 블록 크기를 갖는 단일 캐시를 갖고있다.
- 배열 크기 n은 매우 커서 단일 행렬의 행은 L1 캐시에 들어가지 않는다.
ijk버전
그럼 이제 가장 일반적인 위 ijk순서의 행렬 곱셈 코드의 캐시 미스 횟수를 분석해보자.
이 코드의 가장 내부 루프는 배열 A와 B를 참조한다.
이때 배열 A를 참조함에 있어서 8번의 실행마다 1번의 캐시 미스가 발생한다.
32 바이트 크기의 캐시 블록에는 8개의 int 타입이 저장될 수 있기에 캐시 미스가 일어나면 8개의 순차적인 데이터를 캐시 블록에 저장한다.
따라서 다음 7번의 A배열 내 원소에 대한 순차적 접근에서는 캐시 미스가 일어나지 않는 것이다.
따라서 매 반복 실행마다 0.125의 미스 비율을 갖는다.
배열 B에는 행 단위로 뛰어넘어 원소에 접근하는 행 단위의 접근을 한다. 단일 행렬의 행은 캐시 블록에 들어갈 수 없다는 조건에 따라 매 실행마다 1번의 캐시 미스가 발생한다.
즉 매 반복 실행마다 1의 미스 비율을 갖는다.
따라서 ijk 순서의 루프를 도는 행렬 곱셈 버전은 매 반복 실행마다 1.125번의 미스가 발생한다. ijk와 jik 버전은 같은 미스 횟수를 가진다.
jki버전
jki 버전을 살펴보자.
for j in range(n):
for k in range(n):
r = B[k][j]
for i in range(n):
c[i][j] += A[i][k] * r 이때 내부 루프는 A와 C를 참조한다.
이때 두 배열 모두에 행 단위로 접근을 하고 있기 때문에 매 반복실행마다 총 2번의 캐시 미스가 발생한다. kji버전도 동일한 캐시 미스 횟수가 발생한다.
앞서 살펴본 ijk버전 보다 공간지역성이 좋지 못하다.
kij버전
마지막으로 kij 버전을 확인해보자.
for k in range(n):
for i in range(n):
r = A[i][k]
for j in range(n):
C[i][j] += B[k][j] * r내부 루프는 B와 C를 참조한다.
이때 두 배열 모두에 같은 행에 대해 열 단위로 순차적으로 접근하고 있기 때문에 각각 8번의 실행마다 1번의 캐시 미스가 발생한다.
즉 매 반복실행마다 0.25번의 캐시 미스가 발생한다. ikj버전 역시 동일하다.
위 두 버전과 비교해봤을때 1번 이상의 캐시 미스 횟수가 줄어들었다.
CSAPP에서는 큰 n값에 대해서 가장 빠른 버전은 가장 느린 버전보다 거의 40배 더 빠르게 실행된다고 말한다.
위 내용을 통해 같은 O(n^3)의 시간복잡도를 갖는 동일한 수의 연산을 실행하는 코드들이지만 공간지역성에 따라 40배의 실행시간이 차이가 날 수 있다는 것을 알아보았다.
알고리즘 문제를 풀면서 아무 생각없이 i,j,k 순서로 루프를 만들어 행렬 곱셈을 구했었는데 이번 공부는 CS지식이 중요하다는 말에 더 공감하게 되는 공부였다.
실력있는 개발자가 되자!
