컴퓨터 시스템 : CSAPP 6장 정리 - 6.5 캐시 친화적 코드 작성

6.5 캐시 친화적인 코드 작성 (Writing Cache-Friendly Code)

6.2절에서는 지역성(locality)이라는 개념을 소개했다. 이제 캐시 메모리의 구조를 이해했으므로, 좋은 지역성을 갖춘 프로그램이 무엇인지 더 명확히 설명할 수 있다​.

핵심은 다음과 같다:

• 좋은 지역성을 가진 프로그램은 낮은 미스율(miss rate)을 가진다.
• 낮은 미스율을 가진 프로그램은 높은 미스율을 가진 프로그램보다 일반적으로 빠르게 실행된다.

따라서, 좋은 프로그래머는 항상 캐시 친화적인(cache-friendly) 코드를 작성해야 한다.

기본 접근 방법:

1. 일반적인 경우를 빠르게 만든다
   대부분의 프로그램은 몇몇 핵심 함수(core functions) 안에서 대부분의 시간을 보낸다.
   그 안에서도 주로 **내부 루프(inner loops)**에 집중하라.
2. 내부 루프에서 캐시 미스 수를 최소화한다
   같은 로드(load)와 저장(store) 수를 가진다면, 미스율이 낮은 루프가 더 빠르게 동작한다​.

예제: 행의 합 구하기 (Summing the Rows of a Matrix)

sumvec 함수 예제

간단한 벡터 합계 함수 sumvec를 보자:

int sumvec(int v[N]) {
    int i, sum = 0;
    for (i = 0; i < N; i++)
        sum += v[i];
    return sum;
}

이 함수는 캐시 친화적인가?

• 지역 변수 i와 sum은 루프 바디 안에서 반복 참조된다.
  • 이 변수들은 보통 컴파일러에 의해 레지스터에 캐시 되어 시간적 지역성이 매우 좋다​.
• 배열 v에 대한 참조는 stride-1 패턴을 가진다.
  • 즉, 메모리 상에서 연속된 요소를 차례로 접근한다.
  • 캐시 블록 크기가 B바이트라면, stride-k 접근 패턴의 평균 미스 수는 min(1, (워드 크기 × k) / B)이다.
  • k=1이면 가장 미스가 적다.

예시:

• 워드 크기가 4바이트이고,
• 캐시 블록 하나가 4개의 워드를 저장하며,
• 캐시가 비어 있는 상태(cold cache)라면,
• v[0] 접근은 미스(miss)가 발생하고, v [0]~v [3] 블록이 캐시 된다.
• 그다음 v [1], v [2], v [3] 접근은 모두 히트(hit) 발생.
• v [4] 접근 시 새로운 블록이 필요하여 다시 미스 발생.

패턴 요약:

접근 인덱스	결과
v[0]	미스(m)
v[1]	히트(h)
v[2]	히트(h)
v[3]	히트(h)
v[4]	미스(m)
v[5]	히트(h)
v[6]	히트(h)
v[7]	히트(h)

결론:

• 이 함수는 시간적 지역성(register 사용)과 공간적 지역성(stride-1 접근) 모두 훌륭하다.
• 결과적으로 매우 캐시 친화적이다​.

---

예제: 열의 합 구하기 (Summing the Columns of a Matrix)

이번에는 행이 아니라 열을 따라 합을 구하는 코드를 보자.

int sumarraycols(int a[M][N]) {
    int i, j, sum = 0;
    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            sum += a[i][j];
    return sum;
}

접근 패턴 분석

• 이 코드에서는 i가 내부 루프이고, j가 외부 루프이다.
• 즉, 열 단위로(col-wise) 메모리를 순회하게 된다​.
• 배열 a [i][j]는 2차원 배열 a의 i행 j열 원소를 의미한다.
  메모리 상에서는 2차원 배열이 **행 우선(row-major)**으로 저장된다.
• 따라서, 같은 열의 원소들을 접근하려면 메모리 주소를 stride-N 만큼 건너뛰어야 한다.

캐시 지역성 영향

• 만약 배열 전체가 캐시에 들어간다면, 행 합 구하기(sumarrayrows)와 비슷하게 좋은 성능을 낼 수 있다.
• 그러나 대부분 경우, 배열 크기가 캐시보다 크기 때문에 다음 문제가 발생한다:

문제:

• a [i][j]를 접근할 때마다 새로운 캐시 블록이 필요해진다.
• 결과적으로, 모든 참조가 캐시 미스(miss)를 유발한다​.

미스 패턴 요약:

열 인덱스 j	i=0	i=1	i=2	i=3	...
0	miss	miss	miss	miss	...
1	miss	miss	miss	miss	...
2	miss	miss	miss	miss	...
...	...	...	...	...	...

(매번 미스 발생)

성능 영향

• 열 합 구하기 코드는 행 합 구하기에 비해 매우 높은 미스율을 가진다.
• 결과적으로 실행 시간이 25배 이상 느려질 수 있다​.

핵심 교훈

프로그래머는 반드시 지역성을 고려해서 코드를 작성해야 한다.

• 가능한 경우, 데이터는 메모리에 저장된 순서대로(=stride-1 접근) 읽어야 한다.
• 열 단위 접근은 큰 배열에서는 캐시 성능을 심각하게 저하시킬 수 있다.

---

예제: 행렬 전치 (Matrix Transposition)

기본 문제

N × N 크기의 행렬 A를 전치(transpose)하여 Aᵗ를 만드는 문제다.
구체적으로, src [i][j]를 dst[j][i]에 복사하는 것이다​.

기본 코드

void transpose(int *dst, int *src, int dim) {
    int i, j;
    for (i = 0; i < dim; i++)
        for (j = 0; j < dim; j++)
            dst[j*dim + i] = src[i*dim + j];
}

 

• src [i][j]를 dst [j][i]로 옮긴다.
• 배열은 1차원 배열처럼 포인터 산술(pointer arithmetic)로 접근한다.

접근 패턴 분석

src 배열 접근:

• src[i][j] 접근은 행 우선(row-major) 순서다.
• 내부 루프(j)에 대해 i는 고정이고, j가 0에서 dim-1까지 변하므로, 메모리 상 연속된 요소를 순서대로 읽는다 (stride-1 접근).

dst 배열 접근:

• dst[j][i] 접근은 열 우선(column-wise)이다.
• j가 변함에 따라 dst [j*dim + i]가 변하는데, 메모리 상으로는 dim 만큼 띄워진 stride-dim 패턴이다.

결론:

• src 읽기는 캐시 친화적이다.
• dst 쓰기는 캐시 비친화적이다​.

캐시 성능 문제

• 읽기는 공간적 지역성이 좋아서 대부분 캐시 히트(hit) 발생.
• 쓰기는 공간적 지역성이 나빠서 거의 매번 캐시 미스(miss) 발생.
• 즉, 매 번 dst [j][i]에 쓸 때마다 새로운 캐시 블록을 가져와야 한다.

결과적으로:

• 쓰기 미스가 전체 성능을 심각하게 저하시킨다.

최적화 방향 제시

• 단순한 전치 코드는 이해하기 쉽지만, 캐시 미스가 많아 매우 느리다.
• 캐시 성능을 개선하려면 데이터 접근 패턴을 바꿔야 한다.
• 특히 blocking(블로킹) 기법을 사용해 한 번에 작은 블록 단위로 읽고 쓰는 식으로 개선할 수 있다 (6.6절에서 자세히 다룬다).