RAM보다 더 빠르게: 캐시

두 줄 요약.

1. 캐시는 RAM 보다 훨씬 빠르다.

2. 병목을 줄이기 위해서는 Cache hit의 횟수를 늘려야한다. 

 

개발을 하다보면 결국에는 최적화를 해야할 시기가 다가옵니다. 그리고 최적화를 할 수 있는 방법은 정말 다양한데, 그 중 대표적인 것이 데이터의 움직임을 최소화하는 것입니다. 왜 최소화를 해야할까? 그 이유는 CPU 코어에서 멀어질수록 데이터를 가져오는데 시간이 많이 걸리기 때문이죠. 그럼 어떻게 하면 데이터의 움직임을 최소화 할 수 있을까?

 

Cache

---

CPU는 연산을 위해서 메모리(RAM)에서 필요한 데이터를 가져옵니다. 하지만 이 과정은 CPU 칩 바깥으로 나가야 하는 물리적 한계와 RAM 자체의 느린 성능 때문에, CPU의 연산 속도가 빠름에도 불구하고 병목 현상이 생기게 되죠. 이러한 병목을 해결하기 위해서 나온게 캐시(Cache) 입니다.

메모리 계층 구조

 

캐시는 대표적으로 L1, L2, L3 계층으로 나뉘어져있고, L 뒤에 숫자가 커질 수록 용량은 커지지만 속도는 느려집니다. 속도의 차이는 CPU 코어의 클럭 수로 비교를 할 수 있습니다.

 

	CPU 클럭 사이클 기준
L1	대략 4
L2	대략 10
L3	대략 50
RAM	대략 200

 

이처럼 캐시의 클럭 사이클이 RAM에 비해 훨씬 낮다보니, 연산의 속도가 훨씬 빨라질 수 밖에 없습니다. 그리고 이 Cache의 효과를 극대화하기 위해서는, RAM이 아닌 캐시에 저장되어있는 데이터를 최대한 활용을 해야합니다. 이게 무슨 말일까요?

 

Cache Hit

---

Cache Hit은 프로그램이 찾고자하는 데이터가 Cache에 존재할 때, 사용되는 말입니다. 만약에 데이터가 존재하지 않으면 Cache Miss가 나오며, 아랫단계의 Cache 혹은 memory로 넘어가게 됩니다. 그러므로 우리는 Cache Hit를 최대한 늘려야하는 상황을 가져와야합니다. 그럼 어떻게 하면 Cache Hit를 늘릴 수 있을까요? 다양한 방법이 있겠지만 직관적인 방법으로는 공간적 지역성(Spatial Locality)를 참고하는 방법입니다.

int M = 10000; // 행
int N = 10000; // 열

// Malloc 할당
int** arr2D = (int**)malloc(M * sizeof(int*));

// Row별 malloc 호출 (메모리가 사방 파편화됨)
for (int i = 0; i < M; i++) {
    arr2D[i] = (int*)malloc(N * sizeof(int));
}

//순회
int sum = 0;
for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
        sum += arr2D[i][j]; 
    }
}

 

malloc을 루프 돌며 여러 번 호출하게 되면, 힙(Heap) 영역의 메모리 상태에 따라 각 행들이 불연속적인 공간에 파편화되어 할당됩니다. 즉, 다음 행으로 넘어갈 때 메모리 주소가 인접해 있지 않고 멀리 떨어져 있을 수 있기 때문에, 하드웨어의 캐시 라인(Cache Line) 활용도가 떨어지고 Cache Miss가 빈번하게 발생하게 됩니다.

 

int M = 10000;
int N = 10000;

// 단 한 번의 malloc으로 모든 데이터를 연속된 공간에 할당
int* arr1D = (int*)malloc(M * N * sizeof(int));

// 순회 (100% 연속된 메모리 접근으로 Spatial Locality 극대화)
int sum = 0;
for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
        sum += arr1D[i * N + j]; // 컴파일러가 인덱스를 일렬로 계산
    }
}

 

 

 

이를 극복하기 위해서, 위와 같이 Spatial Locality를 고려하고 코드를 짜게 된다면, 열을 순회함으로서 지속해서 인접 메모리를 Cache로 올리는 효과를 가져오게 됩니다. 고로 Cache Hit를 극대화 시킬 수 있습니다.

 

결론

---

메모리의 한계를 캐시로 뛰어넘고, Cache Miss를 낮춰 그 속도를 극대화하는 방법을 알아보았습니다. 물론 캐시보다 더 빠른 레지스터가 존재하기도 해서, 캐시가 유일한 속도 극복법은 아닙니다. 하지만 앞으로 코딩하실 때, Spatial Locality를 고려한 프로그래밍을 한다면, 괜찮은 성능 향상을 확인할 수 있을거라 생각합니다.