캐시 친화적 코드 작성하기

지역성

잘 작성한 컴퓨터 프로그램은 좋은 지역성을 보여준다. 즉 이들은 다른 최근에 참조했던 데이터 아이템 근처의 데이터 아이템이나 최근에 자신이 참조했던 데이터 아이템을 참조하려는 경향이 있다. 지역성의 원리라고 알려진 이러한 경향은 하드웨어와 소프트웨어 시스템의 성능과 설계에 엄청난 영향을 주는 지속적인 개념이다.

지역성은 일반적으로 두 개의 서로 다른 형태를 가지는 것으로 설명된다.

시간 지역성

좋은 시간 지역성을 갖는 프로그램에서는 한번 참조된 메모리 위치는 가까운 미래에 다시 여러 번 참조될 가능성이 높다.

공간 지역성

좋은 공간 지역성을 갖는 프로그램에서는 만일 어떤 메모리 위치가 일단 참조되면, 이 프로그램은 가까운 미래에 근처의 메모리 위치를 참조할 가능성이 높다.

캐시 친화적 코드 작성하기

앞서 소개한 지역성 개념에 따르면 더 나은 지역성을 갖는 프로그램들은 더 낮은 미스 비율을 갖게 되며, 더 낮은 미스 비율을 갖는 프로그램들은 높은 미스 비율을 보이는 프로그램보다 더 빨리 실행되는 경향을 보인다. 따라서 좋은 프로그래머란 항상 캐시 친화적으로, 즉 좋은 지역성을 가지도록 프로그램을 작성해야 한다.

다음은 코드가 캐시 친화적이게 만들기 위해 사용할 수 있는 기본적인 방법들이다.

1. 공통적인 경우를 빠르게 동작하도록 만들어라
   프로그램들은 대개 대부분의 시간을 몇 개의 핵심 함수들에서 소모한다. 이 함수들은 대부분의 시간을 몇 개의 루프에서 보낸다. 그래서 핵심 함수들의 내부 루프에 집중하고 나머지는 무시한다.
   
   
2. 각 내부 루프의 캐시 미스 수를 최소화하라
   Load와 Store 연산의 총수가 같다는 등의 다른 것들이 동일하다면 우수한 미스 비율을 갖는 루프들이 더 빨리 동작한다.

이를 다음의 실제 코드와 함께 이해해보자.

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 참조 패턴(이때 k는 워드 수)은 루프 반복 실행당 min[1, (wordsize x k) / B]의 평균 미스 횟수를 나타낸다. 이는 k = 1인 경우 최소 값을 가지며, 그래서 v에 대해 stride-1 참조는 실제로 캐시 친화적이다.

예를 들어 v가 블록 단위로 정렬되어 잇으며 워드들은 4 바이트, 캐시 블록은 4 워드이고, 처음에 캐시는 cold cache(비어 있는 상태)라고 가정하자. 그러면 캐시 구성과는 상관없이 v에 대한 참조는 다음과 같은 적중과 미스 패턴을 갖는다.

그림 2. Stride-1 참조인 경우 확보되는 공간 지역성

요약하자면 sumvec 함수는 캐시 친화적인 코드를 작성하는 것에 관해 두 가지 중요한 점들을 보여준다.

1. 지역 변수들에 대한 반복적인 참조는 좋으며, 그 이유는 컴파일러가 이들을 레지스터 파일에 캐싱할 수 있기 때문이다. (시간 지역성)
2. Stride-1 참조 패턴은 좋으며, 그 이유는 메모리 계층 구조의 모든 레벨에서 데이터를 연속적인 블록들로 저장하기 때문이다. (공간 지역성)

공간 지역성은 특히 다차원 배열에 대해 연산을 수행하는 프로그램에서 중요하다. 예를 들어, 아래 코드의 sumarrayrows 함수에 대해서 생각해보자. 이 함수는 이차원 배열의 원소들을 행우선 순서로 더하는 함수이다.

int sumarrayrows(int a[m][n])
{
    int i, j, sum = 0;

    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++)
            sum += a[i][j];
    }
    return sum;
}

C가 배열들을 행 우선 순서로 저장하므로, 이 함수의 내부 루프는 sumvec과 동일한 바람직한 stride-1 접근 패턴을 가진다. 예를 들어 sumvec에서와 같이 캐시에 관해서 동일한 가정을 한다고 하자. 그러면 배열 a에 대한 참조들은 다음과 같은 적중과 미스 패턴을 가진다.

그림 3. 행 우선 순서 접근 시의 캐시 패턴

그러나 만일 루프 실행 순서를 열 우선 순서로 변경할 경우 캐시 패턴에 문제가 발생한다.

int sumarraycols(int a[m][n])
{
    int i, j, sum = 0;

    for (j = 0; j < m; i++) {
        for (i = 0; i < n; j++)
            sum += a[i][j];
    }
    return sum;
}

그림 4. 열우선 순서 접근 시의 캐시 패턴

이 경우에  행 대신에 열 우선으로 배열을 탐색하고 있다. 만일 운이 좋아서 전체 배열이 캐시에 모두 들어간다면 같은 미스 비율로 1/4를 갖게 될 것이다. 그러나 만일 배열의 크기가 캐시보다 더 크다면, 각각의 모든 a[i][j]에 대한 접근은 미스가 된다.