[TIL/크래프톤 정글9기] 32일차(CSAPP Chapter.6.2 지역성)

blueprint·2025년 6월 12일
CSAPP

크래프톤정글9기

목록 보기
27/55

CSAPP 챕터 6.2: 지역성 (Locality)

목차

  1. 지역성의 기본 개념
  2. 지역성의 두 가지 형태
  3. 프로그램 데이터의 지역성
  4. 명령어 페치의 지역성
  5. 지역성 평가 규칙
  6. 실무 적용 사례

1. 지역성의 기본 개념

1.1 지역성이란?

지역성 원리 (Principle of Locality): 잘 작성된 컴퓨터 프로그램들이 보이는 경향으로, 최근에 참조된 데이터 항목들 근처의 데이터나 최근에 참조된 데이터 자체를 다시 참조하는 성향

1.2 지역성의 중요성

성능에 미치는 영향

  • 좋은 지역성을 가진 프로그램 → 빠른 실행 속도
  • 나쁜 지역성을 가진 프로그램 → 느린 실행 속도
  • 성능 차이: 최대 40배까지 차이 날 수 있음

시스템 설계에 미치는 영향

하드웨어 레벨    → 캐시 메모리 설계
운영체제 레벨    → 가상 메모리, 파일 시스템 캐싱
응용프로그램 레벨 → 웹 브라우저 캐싱, 서버 캐싱

1.3 지역성을 활용하는 시스템들

하드웨어:

  • 캐시 메모리: 최근 참조된 명령어와 데이터 블록 저장

운영체제:

  • 가상 메모리: 주 메모리를 가상 주소 공간의 캐시로 사용
  • 파일 시스템: 최근 사용된 디스크 블록을 메모리에 캐싱

응용 프로그램:

  • 웹 브라우저: 최근 방문한 문서를 로컬 디스크에 캐싱
  • 웹 서버: 자주 요청되는 문서를 프론트엔드 캐시에 저장

2. 지역성의 두 가지 형태

2.1 시간적 지역성 (Temporal Locality)

정의

한 번 참조된 메모리 위치가 가까운 미래에 다시 여러 번 참조될 가능성이 높은 특성

특징

  • "최근 사용된 것을 다시 사용"
  • 반복문에서 같은 변수를 계속 사용
  • 함수 호출에서 같은 코드 반복 실행

예시

int sum = 0;
for (i = 0; i < N; i++) {
    sum += array[i];  // sum 변수가 시간적 지역성을 보임
}

2.2 공간적 지역성 (Spatial Locality)

정의

한 메모리 위치가 참조되면, 그 근처의 메모리 위치들이 가까운 미래에 참조될 가능성이 높은 특성

특징

  • "인접한 것들을 연속적으로 사용"
  • 배열 원소들의 순차 접근
  • 구조체 멤버들의 연속 접근

예시

int array[N];
for (i = 0; i < N; i++) {
    sum += array[i];  // 배열 원소들이 공간적 지역성을 보임
}

2.3 지역성 비교표

특성시간적 지역성공간적 지역성
핵심 개념같은 위치 재참조인근 위치 참조
메모리 패턴동일 주소 반복연속 주소 순차
대표 사례변수 재사용배열 순회
캐시 효과히트율 향상프리페칭 효과

3. 프로그램 데이터의 지역성

3.1 좋은 지역성의 예시: sumvec 함수

코드 분석

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

메모리 접근 패턴

주소:     0    4    8   12   16   20   24   28
내용:    v0   v1   v2   v3   v4   v5   v6   v7
접근순서: 1    2    3    4    5    6    7    8

지역성 분석

sum 변수:

  • ✅ 시간적 지역성: 매 루프마다 반복 참조
  • ❌ 공간적 지역성: 스칼라 변수이므로 해당 없음

배열 v:

  • ❌ 시간적 지역성: 각 원소를 한 번씩만 접근
  • ✅ 공간적 지역성: 메모리에 저장된 순서대로 순차 접근

결론: 전체적으로 좋은 지역성을 가짐

3.2 Stride 패턴 분석

Stride-1 패턴 (순차 접근)

// 좋은 공간적 지역성
for (i = 0; i < N; i++)
    sum += array[i];  // stride-1 패턴

Stride-k 패턴

// 나쁜 공간적 지역성
for (i = 0; i < N; i += k)
    sum += array[i];  // stride-k 패턴 (k > 1)

Stride와 지역성의 관계

  • Stride ↓ → 공간적 지역성 ↑
  • Stride-1: 최고의 공간적 지역성
  • Stride가 클수록: 공간적 지역성 감소

3.3 다차원 배열에서의 지역성

3.3.1 행 우선 순회 (Row-Major Order) - 좋은 지역성

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

메모리 배치와 접근 패턴:

메모리 주소:  0    4    8   12   16   20
배열 내용:   a00  a01  a02  a10  a11  a12
접근 순서:    1    2    3    4    5    6

지역성 분석:

  • ✅ 공간적 지역성: 메모리 저장 순서와 접근 순서 일치
  • ✅ Stride-1 패턴: 연속된 메모리 위치 순차 접근

3.3.2 열 우선 순회 (Column-Major Order) - 나쁜 지역성

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

메모리 배치와 접근 패턴:

메모리 주소:  0    4    8   12   16   20
배열 내용:   a00  a01  a02  a10  a11  a12
접근 순서:    1    3    5    2    4    6

지역성 분석:

  • ❌ 공간적 지역성: 메모리를 건너뛰며 접근
  • ❌ Stride-N 패턴: N만큼 떨어진 위치 접근

3.3.3 성능 차이

// M=1000, N=1000인 2차원 배열의 경우
// 행 우선 순회: 캐시 친화적 → 빠른 실행
// 열 우선 순회: 캐시 비친화적 → 느린 실행
// 성능 차이: 수배에서 수십 배까지 가능

3.4 지역성 개선 예시

Before: 나쁜 지역성

// 2차원 배열을 열 우선으로 처리
for (j = 0; j < N; j++)
    for (i = 0; i < M; i++)
        result += matrix[i][j];

After: 좋은 지역성

// 2차원 배열을 행 우선으로 처리
for (i = 0; i < M; i++)
    for (j = 0; j < N; j++)
        result += matrix[i][j];

간단한 루프 순서 변경만으로 극적인 성능 향상 가능!

4. 명령어 페치의 지역성

4.1 명령어 지역성의 특성

기본 개념

  • 프로그램 명령어들도 메모리에 저장되어 CPU가 페치(fetch)해야 함
  • 명령어에 대해서도 지역성 평가 가능

명령어의 특징

  • 런타임에 거의 수정되지 않음 (코드 vs 데이터)
  • CPU는 명령어를 읽기만 하고 덮어쓰기는 거의 안 함

4.2 루프에서의 명령어 지역성

예시 분석

for (i = 0; i < N; i++)
    sum += v[i];

공간적 지역성:

  • 루프 본문의 명령어들이 메모리에서 순차적으로 저장
  • CPU가 순서대로 명령어 페치 → 좋은 공간적 지역성

시간적 지역성:

  • 루프 본문이 여러 번 반복 실행
  • 동일한 명령어들이 반복적으로 페치 → 좋은 시간적 지역성

4.3 명령어 지역성 최적화

루프 크기와 지역성

  • 작은 루프 본문 → 더 좋은 지역성
  • 많은 반복 횟수 → 더 좋은 시간적 지역성

분기문과 지역성

// 좋은 지역성: 순차적 실행
if (condition) {
    statement1;
    statement2;
}

// 나쁜 지역성: 점프가 많은 코드
if (cond1) goto label1;
if (cond2) goto label2;
// ...

5. 지역성 평가 규칙

5.1 지역성 판단 기준

시간적 지역성 규칙

  1. 같은 변수를 반복 참조하는 프로그램 → 좋은 시간적 지역성
  2. 루프 변수, 카운터 → 시간적 지역성의 대표 사례
  3. 함수 내 지역 변수 → 함수 실행 동안 시간적 지역성

공간적 지역성 규칙

  1. Stride-k 패턴에서 k가 작을수록 → 더 좋은 공간적 지역성
  2. Stride-1 패턴 → 최고의 공간적 지역성
  3. 메모리를 크게 건너뛰는 패턴 → 나쁜 공간적 지역성

명령어 지역성 규칙

  1. 루프: 시간적/공간적 지역성 모두 좋음
  2. 작은 루프 본문: 더 좋은 지역성
  3. 많은 반복 횟수: 더 좋은 시간적 지역성

5.2 지역성 평가 체크리스트

□ 변수들이 반복적으로 사용되는가? (시간적 지역성)
□ 배열 접근이 순차적인가? (공간적 지역성)
□ 루프가 메모리를 건너뛰며 접근하는가? (Stride 패턴)
□ 다차원 배열 접근 순서가 저장 순서와 일치하는가?
□ 함수 호출이 지나치게 많은가? (명령어 지역성)

6. 실무 적용 사례

6.1 행렬 곱셈 최적화

기본 구현 (나쁜 지역성)

// 표준 3중 루프: 캐시 미스 많음
for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        for (k = 0; k < n; k++)
            C[i][j] += A[i][k] * B[k][j];  // B[k][j] 접근이 stride-n

블록 단위 구현 (좋은 지역성)

// 블록 단위 처리: 캐시 지역성 향상
for (ii = 0; ii < n; ii += BLOCK_SIZE)
    for (jj = 0; jj < n; jj += BLOCK_SIZE)
        for (kk = 0; kk < n; kk += BLOCK_SIZE)
            for (i = ii; i < ii + BLOCK_SIZE; i++)
                for (j = jj; j < jj + BLOCK_SIZE; j++)
                    for (k = kk; k < kk + BLOCK_SIZE; k++)
                        C[i][j] += A[i][k] * B[k][j];

6.2 데이터 구조 설계

Array of Structures (AoS) vs Structure of Arrays (SoA)

AoS (나쁜 지역성):

struct Point {
    float x, y, z;
};
struct Point points[N];

// 모든 x 좌표만 처리하고 싶을 때
for (i = 0; i < N; i++)
    sum_x += points[i].x;  // x, y, z가 섞여서 저장됨

SoA (좋은 지역성):

struct Points {
    float x[N];
    float y[N]; 
    float z[N];
};
struct Points points;

// 모든 x 좌표만 처리할 때
for (i = 0; i < N; i++)
    sum_x += points.x[i];  // x들만 연속으로 저장됨

6.3 캐싱 전략

웹 서버 캐싱

// 시간적 지역성 활용
if (cache_contains(url)) {
    return cached_content(url);  // 캐시 히트
} else {
    content = fetch_from_disk(url);
    cache_store(url, content);   // 향후 재사용을 위해 캐싱
    return content;
}

데이터베이스 버퍼 풀

-- 최근 접근한 페이지들을 메모리에 유지
-- 공간적 지역성: 인접한 레코드들을 같은 페이지에 저장
-- 시간적 지역성: 자주 접근하는 페이지들을 캐시에 유지

7. 지역성 최적화 기법

7.1 코드 최적화 기법

루프 교환 (Loop Interchange)

// Before: 나쁜 지역성
for (j = 0; j < N; j++)
    for (i = 0; i < M; i++)
        matrix[i][j] += value;

// After: 좋은 지역성
for (i = 0; i < M; i++)
    for (j = 0; j < N; j++)
        matrix[i][j] += value;

루프 타일링 (Loop Tiling)

// 큰 배열을 작은 블록으로 나누어 처리
for (ii = 0; ii < M; ii += TILE_SIZE)
    for (jj = 0; jj < N; jj += TILE_SIZE)
        for (i = ii; i < min(ii + TILE_SIZE, M); i++)
            for (j = jj; j < min(jj + TILE_SIZE, N); j++)
                process(matrix[i][j]);

7.2 데이터 레이아웃 최적화

구조체 멤버 순서 조정

// Before: 캐시 라인 낭비
struct BadLayout {
    char flag;     // 1 byte
    int data1;     // 4 bytes (3 bytes padding)
    char status;   // 1 byte
    int data2;     // 4 bytes (3 bytes padding)
};

// After: 메모리 효율적
struct GoodLayout {
    int data1;     // 4 bytes
    int data2;     // 4 bytes
    char flag;     // 1 byte
    char status;   // 1 byte (2 bytes padding)
};
profile
blueprint
이전 포스트

[TIL/크래프톤 정글9기] 31일차(백준 RGB거리 / DP)

다음 포스트

[TIL/크래프톤 정글9기] 33일차(C언어 포인터)

0개의 댓글