컴퓨터 시스템 : CSAPP 6장 정리 - 6.2 지역성

6.2 지역성 (Locality)

잘 작성된 컴퓨터 프로그램은 일반적으로 좋은 지역성을 보인다. 즉, 최근에 참조한 데이터 항목 근처에 있는 데이터를 참조하거나, 최근에 참조한 데이터를 다시 참조하는 경향을 가진다. 이 경향을 **지역성 원칙(principle of locality)**이라고 부르며, 하드웨어와 소프트웨어 시스템 설계 및 성능에 지대한 영향을 미친다​.

지역성에는 두 가지 주요 형태가 있다:

• 시간적 지역성(Temporal Locality): 한 번 참조된 메모리 위치가 가까운 미래에 다시 참조될 가능성이 높다.
• 공간적 지역성(Spatial Locality): 한 메모리 위치가 참조되면, 그 주변 메모리 위치도 곧 참조될 가능성이 높다.

프로그래머는 지역성 원칙을 이해해야 한다. 일반적으로 지역성이 좋은 프로그램이 지역성이 나쁜 프로그램보다 더 빠르게 실행된다. 모든 수준의 컴퓨터 시스템은 지역성을 활용하도록 설계되어 있다. 하드웨어에서는 캐시 메모리를 통해, 운영체제에서는 메인 메모리를 가상 주소 공간의 일부를 캐싱하는 데 사용한다​.

---

6.2.1 프로그램 데이터 참조의 지역성 (Locality of References to Program Data)

단순한 예제로, 벡터 요소의 합을 구하는 함수 sumvec(a)를 고려한다.

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

(a) 좋은 지역성을 갖는 함스, (b) 벡터 v(N=8)에 대한 참조 패턴 : 벡터 원소들이 메모리에 저장된 것과 같은 순서로 어떻게 접근하는지에 유의하라

이 함수의 지역성을 분석하면 다음과 같다:

• 변수 sum은 루프의 각 반복에서 참조되므로 좋은 시간적 지역성을 가진다.
• 그러나 sum은 스칼라 변수이므로 공간적 지역성은 없다.

벡터 v의 경우:

• v의 요소들은 메모리에 순서대로 저장되어 있으며, 루프가 이 순서대로 연속적으로 읽어 들인다.
• 따라서 v에 대해서는 좋은 공간적 지역성이 존재하고, 각 요소는 딱 한 번만 참조되므로 시간적 지역성은 없다​.

Stride-1 참조 패턴:

• sumvec처럼 배열의 요소를 순차적으로 접근하는 것을 stride-1 참조 패턴이라 부른다.
• 일반적으로 stride-1 패턴은 프로그램에 좋은 공간적 지역성을 제공한다.
• 만약 배열 요소를 매 k 개씩 건너뛰며 참조하면 이를 stride-k 참조 패턴이라 부른다. k가 클수록 공간적 지역성은 떨어진다.

다차원 배열 참조:

• 다차원 배열에서도 stride-1 패턴을 유지하는 것이 중요하다.
• 예를 들어 sumarrayrows 함수는 2차원 배열을 행(row) 단위로 순회하여 좋은 공간적 지역성을 가진다.

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;
}

(a) 좋은 지역성을 갖는 또 다른 함수, (b) 배열 a(M = 2, N = 3) 에 대한 참조 패턴, 배열은 이들이 메모리에 저장된 것과 같은 행우선 순서로 접근되기 때문에 좋은 공간 지역성을 갖는다.

• 이 함수는 메모리에 저장된 순서(행 우선(row-major) 순서)대로 배열을 순회한다.
• 반면 열(column) 순서로 순회하는 함수는 공간적 지역성이 나빠진다​.

---

6.2.2 명령어 인출의 지역성 (Locality of Instruction Fetches)

프로그램 명령어도 메모리에 저장되며 CPU에 의해 읽혀야 한다. 따라서 프로그램은 명령어 인출 측면에서도 지역성을 평가할 수 있다​.

예를 들어, 반복문 루프 본문의 명령어들은 메모리에 연속적으로 저장되어 있으며, 실행 시에도 순차적으로 인출된다. 따라서 루프 본문은 다음과 같은 지역성을 가진다:

• 공간적 지역성(Spatial Locality): 명령어들이 메모리상에서 연속적으로 배치되고 순차적으로 접근된다.
• 시간적 지역성(Temporal Locality): 루프 본문이 여러 번 반복 실행되기 때문에 동일한 명령어가 여러 번 인출된다.

또한 코드와 데이터 사이에는 중요한 차이가 있다:

• 프로그램 코드(명령어)는 실행 중에 거의 수정되지 않는다.
• CPU는 프로그램을 실행하는 동안 메모리로부터 명령어를 읽기만 하고, 일반적으로 명령어를 덮어쓰거나 수정하지 않는다​.

이러한 성질 덕분에 CPU는 명령어 캐시(i-cache) 등을 통해 명령어 인출에 최적화된 고성능 동작이 가능하다.

---

6.2.3 지역성 요약 (Summary of Locality)

이 절에서는 지역성(locality)의 기본 개념을 소개하고, 프로그램 내에서 지역성을 정성적으로 평가하는 간단한 규칙들을 정리한다​.

지역성 평가 규칙:

• 시간적 지역성(Temporal Locality):
  같은 변수를 반복해서 참조하는 프로그램은 좋은 시간적 지역성을 가진다.
• 공간적 지역성(Spatial Locality):
  • stride-k 참조 패턴을 가진 프로그램에서, stride 값이 작을수록 좋은 공간적 지역성을 가진다.
  • stride-1 참조 패턴(연속 참조)을 가지면 공간적 지역성이 좋다.
  • 메모리를 큰 stride로 건너뛰어 접근하는 프로그램은 공간적 지역성이 나쁘다.
• 루프 구조:
  루프는 명령어 인출 측면에서 좋은 시간적, 공간적 지역성을 제공한다. 루프 본문의 크기가 작고 반복 횟수가 많을수록 지역성이 더 좋아진다.

---

추가 설명:

• 이후 캐시 메모리에 대해 배우고 나면, 지역성을 캐시 히트(hit)와 미스(miss)로 정량화할 수 있게 된다.
• 지역성이 좋은 프로그램이 일반적으로 더 빠르게 실행되는 이유도 명확해진다.
• 소스 코드를 대충 훑어보면서 프로그램이 얼마나 좋은 지역성을 가졌는지 감을 잡는 능력은 프로그래머에게 매우 중요한 기술이다​.

---