Memory Hierarchy
& Matrix Locality

1. 한 장 요약

2. 핵심 직관

프로그램은 CPU 명령만 실행하지 않는다. 대부분의 시간은 데이터를 가져오고, 기다리고, 다시 가져오는 데 쓰일 수 있다. 같은 O(n^3) 계산도 배열을 어떤 순서로 읽는지에 따라 전혀 다른 속도가 나온다.

3. Memory hierarchy

Memory hierarchy는 빠르지만 작고 비싼 저장소부터, 느리지만 크고 싼 저장소까지 층층이 둔 구조다. CPU는 보통 register, L1, L2, L3, main memory, storage 쪽으로 내려가며 데이터를 찾는다.

캐시는 main memory의 모든 값을 들고 있지 않는다. 자주 쓰거나 곧 쓸 가능성이 높은 block 일부를 가까운 곳에 복사해 둔다. 이때 “무엇을 가까이 둘 것인가”는 프로그램의 locality가 결정한다.

4. Cache organization: S, E, B, tag

Cache는 set, line, block으로 조직된다. 메모리 주소는 보통 [ tag | set index | block offset ]으로 쪼개어 해석한다.

E = 1이면 direct-mapped cache이고, S = 1이면 fully associative cache다. 일반적인 형태는 set을 먼저 고르고 그 set 안의 E개 line을 비교하는 E-way set associative cache다.

5. Hit, miss, AMAT

Miss의 종류

AMAT

AMAT, Average Memory Access Time은 평균 메모리 접근 비용을 보는 식이다.

AMAT = hit time + miss rate * miss penalty

miss rate가 조금만 줄어도 체감 성능이 크게 바뀐다. hit time이 1 cycle이고 miss penalty가 100 cycles라면, 97% hit는 평균 4 cycles이고 99% hit는 평균 2 cycles이다. 이 차이가 cache-friendly code가 중요한 이유다.

6. Locality

Locality는 프로그램이 “방금 쓴 것” 또는 “방금 쓴 것 근처”를 다시 쓸 가능성이 높다는 성질이다. 캐시는 이 습관을 믿고 설계된다.

7. Cache line, stride, working set

Cache line 또는 cache block은 캐시가 메모리에서 한 번에 가져오는 데이터 덩어리다. 보통 64B 크기를 자주 본다. double이 8B라면 cache line 하나에 8개가 들어간다.

for (int i = 0; i < n; i++)
    sum += a[i];

for (int i = 0; i < n; i++)
    sum += a[i * n];

Working set은 현재 루프나 계산 구간에서 반복적으로 만지는 데이터 묶음이다. working set이 L1에 들어가면 매우 빠르고, L2/L3로 밀리면 느려지고, main memory까지 내려가면 더 느려진다.

8. Memory mountain

Memory mountain은 read throughput을 working set size와 stride의 함수로 그린 성능 지형이다. 높은 곳은 빠른 접근 패턴이고, 낮은 곳은 느린 접근 패턴이다.

CS:APP 원본 memory mountain 차트

아래 이미지는 CS:APP 블로그에 공개된 memory mountain 차트 이미지 URL을 직접 참조한다. 여러 세대의 CPU에서 size, stride, throughput 지형이 어떻게 달라지는지 비교할 수 있다.

측정 코드의 의미

double data[MAXELEMS];  /* 전역 배열. 이 배열을 여러 size/stride로 순회한다. */

double test(int elems, int stride)
{
    long i, sx2 = stride*2, sx3 = stride*3, sx4 = stride*4;
    double acc0 = 0, acc1 = 0, acc2 = 0, acc3 = 0;
    long length = elems;
    long limit = length - sx4;

    /* 한 번에 4개씩 읽는 loop unrolling. */
    for (i = 0; i < limit; i += sx4) {
        acc0 += data[i];
        acc1 += data[i + stride];
        acc2 += data[i + sx2];
        acc3 += data[i + sx3];
    }

    /* 남은 꼬리 원소 처리. */
    for (; i < length; i++)
        acc0 += data[i];

    return ((acc0 + acc1) + (acc2 + acc3));
}

double run(int size, int stride, double Mhz)
{
    double cycles;
    int elems = size / sizeof(double);

    test(elems, stride);                  /* cache warm-up */
    cycles = fcyc2(test, elems, stride, 0); /* cycle 측정 */
    return (size / stride) / (cycles / Mhz);
}

현대 CPU는 prefetching을 하므로 stride-1 같은 예측 가능한 접근은 더 이득을 볼 수 있다. 하지만 큰 stride나 큰 working set은 여전히 cache line 낭비와 낮은 hit rate로 이어진다.

9. Matrix multiplication과 loop order

행렬 곱셈의 수학은 같다.

C[i][j] = sum over k of A[i][k] * B[k][j]

하지만 C의 2차원 배열은 row-major order다. 한 행의 원소들이 메모리에 연속으로 붙어 있다. 그래서 두 번째 인덱스가 변하면 연속 접근이고, 첫 번째 인덱스가 변하면 행 크기만큼 점프한다.

A[i][0], A[i][1], A[i][2], ...

A[0][j], A[1][j], A[2][j], ...

배열별 판정법

10. 여섯 loop order 비교표

세 글자 ijk는 바깥 루프부터 안쪽 루프까지의 순서를 뜻한다. 마지막 글자가 가장 안쪽 루프다. 성능은 주로 이 마지막 글자가 A, B, C를 어떻게 움직이는지로 결정된다.

ijk를 읽는 법

마지막 글자로 먼저 분류하기

CSAPP 공식 자료와 연결

CSAPP 공식 figure/source 자료에는 matrix multiply 성능 데이터와 여섯 루프 순열 코드가 따로 공개되어 있다. 아래 차트는 공식 corei7mm.xls의 corei7mmdata 값을 바탕으로 다시 그린 것이다.

CSAPP식 세 묶음

이 miss 수치는 32B block, 8B double, 충분히 큰 n 같은 분석 가정 아래의 근사다. 열 방향 접근이 언제나 100% miss라는 뜻은 아니다. cache size, associativity, prefetching, TLB, compiler optimization에 따라 실제 측정값은 달라진다.

첫 두 루프를 바꾸면 왜 pair 성능이 비슷한가

ijk와 jik, jki와 kji, kij와 ikj는 각각 가장 안쪽 루프가 같다. 바깥 두 루프의 순서가 바뀌어도 안쪽 루프에서 A, B, C를 움직이는 핵심 access pattern은 거의 같다. 그래서 큰 성능 분류도 pair 단위로 묶인다.

실제 기계에서는 prefetching, TLB, write policy, compiler optimization 때문에 완전히 같지는 않다. 그래도 Chapter 6의 큰 결론은 “안쪽 루프의 locality가 전체 성능을 크게 지배한다”이다.

대표 코드

for (i = 0; i < n; i++)
  for (k = 0; k < n; k++) {
    double r = A[i][k]; // A는 scalar처럼 재사용
    for (j = 0; j < n; j++)
      C[i][j] += r * B[k][j]; // B, C row-wise
  }

for (j = 0; j < n; j++)
  for (k = 0; k < n; k++) {
    double r = B[k][j]; // B는 scalar처럼 재사용
    for (i = 0; i < n; i++)
      C[i][j] += A[i][k] * r; // A, C column-wise
  }

11. Blocking / tiling

Blocking 또는 tiling은 큰 행렬을 캐시에 들어갈 만한 작은 타일로 나누어 계산하는 기법이다. 목적은 작은 A/B/C 블록을 캐시에 올려두고 가능한 많이 재사용하는 것이다.

for (i = 0; i < n; i += L)
  for (j = 0; j < n; j += L)
    for (k = 0; k < n; k += L) {
      // A, B, C의 작은 tile을 cache 안에서 반복 재사용한다.
      for (i1 = i; i1 < i + L; i1++)
        for (j1 = j; j1 < j + L; j1++)
          for (k1 = k; k1 < k + L; k1++)
            C[i1*n + j1] += A[i1*n + k1] * B[k1*n + j1];
    }

여기서 L은 matrix tile의 한 변 길이다. cache organization에서 쓴 B = 2^b bytes, 즉 cache block size와 다른 기호다. CSAPP식 단순 miss model에서는 double 원소, cache line당 8 doubles(64B line — 앞의 loop order 표는 32B line = double 4개 가정이라 이 blocking 예시와는 cache line 가정이 다르다), 충분히 큰 n, A/B/C tile이 usable cache에 들어간다는 가정 아래 blocking 없이 약 (9/8)n^3 misses가 난다. blocking을 하면 tile L이 cache에 남아 반복 재사용되는 만큼 miss가 크게 줄어든다(tile이 클수록 유리). 숫자 자체보다 중요한 건 “큰 문제를 cache에 들어가는 작은 문제로 쪼갠다”는 생각이다.

12. 언어별 메모리 레이아웃 감각

JavaScript 예시

// 2D 배열 감각을 flat 1D typed array로 표현
const n = 1024;
const a = new Float64Array(n * n);

function get(i, j) {
  return a[i * n + j]; // row-major index
}

일반 객체를 숫자 커널에 쓰면 속성 모양 변화, sparse array, boxing 등으로 엔진 최적화가 흔들릴 수 있다. 숫자 밀집 데이터는 typed array가 더 예측 가능하다.

JavaScript runtime 감각: V8과 Bun을 분리해서 기억하기

Python / Ruby 감각: 기본 컨테이너는 pointer chasing에 가깝다

# Python list: 칸마다 객체 reference를 들고 있다고 생각한다.
heights = [170, 181, 176, 190]

# 숫자 커널: 같은 dtype의 값을 조밀하게 담는 배열이 locality에 유리하다.
import numpy as np
height_arr = np.array([170, 181, 176, 190], dtype=np.int32)

CPython list 감각

list object
  |
  v
[ptr][ptr][ptr][ptr]  // PyObject* reference 배열
  |    |    |    |
  v    v    v    v
 int  int  int  int   // 객체 본체는 별도 위치일 수 있음

NumPy numeric ndarray 감각

[170][181][176][190]  // 같은 dtype 값 buffer

Python과 Ruby에서 “배열처럼 생겼다”는 말이 곧 C 배열처럼 값이 연속이라는 뜻은 아니다. CPython의 일반 list는 객체 reference 컨테이너로 보는 편이 안전하다. 큰 숫자 배열, 행렬, 컬럼 데이터를 빠르게 돌려야 하면 NumPy의 homogeneous ndarray, Polars처럼 Arrow columnar memory model을 쓰는 도구가 CSAPP의 locality 감각에 더 가깝다.

13. Java class array cache locality

Java에서 int[], double[] 같은 primitive array는 값들이 배열 내부에 연속 배치되는 감각을 준다. 반면 Player[] 같은 class array는 객체 자체가 아니라 객체 참조들이 배열 안에 들어간다. 실제 객체들은 heap 곳곳에 따로 있을 수 있다.

primitive 배열: 값 자체가 한 줄로 놓인다

int[] hp = new int[5];

hp[0] = 100;
hp[1] = 80;
hp[2] = 60;
hp[3] = 40;
hp[4] = 20;

hp 배열의 메모리 감각

[100][ 80][ 60][ 40][ 20]
  0    1    2    3    4

이 구조에서는 hp[0], hp[1], hp[2]가 연속된 위치에 놓인다. 반복문으로 순회하면 CPU가 연속된 값을 읽고, cache line 하나를 가져왔을 때 여러 값을 함께 활용할 수 있다.

for (int i = 0; i < size; i++) {
    if (hp[i] <= 0) {
        // 죽은 플레이어 처리
    }
}

class 배열: reference 표가 먼저 있고 객체는 따로 있다

final class Player {
    int id;
    int hp;
    float x;
    float y;
}

Player[] players = new Player[5];

Java class 배열의 메모리 감각

players:
[ ref ][ ref ][ ref ][ ref ][ ref ]
   |     |     |     |     |
   v     v     v     v     v
 Player Player Player Player Player

배열은 reference를 연속으로 담는다.
객체 본체는 heap의 다른 위치에 있을 수 있다.

hp[i]
  ↓
값

players[i]
  ↓
Player 객체 reference
  ↓
Player 객체
  ↓
hp 값

for (int i = 0; i < size; i++) {
    Player p = players[i];  // reference 읽기

    if (p.hp <= 0) {        // 객체 안의 필드 읽기
        // 죽은 플레이어 처리
    }
}

해결 방향: 객체를 필드별 primitive 배열로 풀기

final class Player {
    int id;
    int hp;
    float x;
    float y;
    boolean alive;
}

Player[] players = new Player[capacity];

final class PlayerTable {
    int size;
    int[] ids;
    int[] hps;
    float[] xs;
    float[] ys;
    boolean[] alive;
}

객체 배열 방식

Player 0 = { id, hp, x, y, alive }
Player 1 = { id, hp, x, y, alive }
Player 2 = { id, hp, x, y, alive }

필드별 primitive 배열 방식

ids:   [  1][  2][  3]
hps:   [100][ 80][ 60]
xs:    [1.0][2.0][3.0]
ys:    [5.0][6.0][7.0]
alive: [true][true][true]

for (int i = 0; i < size; i++) {
    if (alive[i]) {
        xs[i] += dx;
        ys[i] += dy;
    }
}

AoS와 SoA

// 객체 배열: reference를 따라간 뒤 hp 필드 접근
for (int i = 0; i < size; i++)
    if (players[i].hp <= 0) deadCount++;

// field array: hps 배열만 연속으로 순회
for (int i = 0; i < size; i++)
    if (hps[i] <= 0) deadCount++;

Hot / cold data 분리

모든 필드를 SoA로 바꿀 필요는 없다. 자주 읽고 대량으로 처리하는 hot data만 primitive array로 분리하고, 이름, 스킨, 설명문처럼 드물게 쓰는 cold data는 객체에 남기는 편이 현실적이다.

final class PlayerRuntimeTable {
    long[] playerIds;
    int[] hps;
    float[] xs;
    float[] ys;
    boolean[] alive;
}

final class PlayerProfile {
    long playerId;
    String nickname;
    String skinName;
    String guildName;
    long createdAt;
}

boxing 피하기

Integer[] scores1;      // Integer 객체 reference 배열
List<Integer> scores2;  // 내부적으로 boxing 비용이 생길 수 있음
int[] scores3;          // primitive 값 배열

성능이 중요한 숫자 루프에서는 boxed type보다 primitive array가 예측 가능하다. 단, 이런 최적화는 코드 구조를 복잡하게 만들 수 있으므로 병목이 확인된 루프부터 적용한다.

14. 실전 체크리스트

• 가장 안쪽 루프 변수를 먼저 본다.
• 그 변수가 각 배열의 첫 번째 인덱스인지 두 번째 인덱스인지 본다.
• C row-major에서는 두 번째 인덱스가 변해야 연속 접근이다.
• 안 변하는 값은 register에 잡힌 scalar처럼 재사용되는지 본다.
• stride가 1인지, 행 크기만큼 점프하는지 확인한다.
• working set이 L1/L2/L3 중 어디에 들어갈지 추정한다.
• miss가 compulsory, capacity, conflict 중 어디에 가까운지 분류한다.
• 큰 행렬에서는 blocking으로 작은 타일을 cache에 넣을 수 있는지 본다.
• Java에서는 객체 배열이 값 배열이 아니라 참조 배열이라는 점을 기억한다.
• JavaScript 숫자 커널은 typed array와 flat indexing을 우선 고려한다.

15. 연습 문제

1. 문제: 64B cache line에 8B double은 몇 개 들어가는가?
   답: 8개.
2. 문제: C 배열 A[i][j]에서 j가 안쪽 루프에서 변하면 왜 좋은가?
   답: row-major에서 같은 행의 원소들이 연속 배치되어 stride-1 접근이 되기 때문이다.
3. 문제: ijk에서 A와 B 중 어느 쪽이 cache-friendly하지 않은가?
   답: B. 안쪽 루프 k가 변하면 B[k][j]는 열 방향으로 움직인다.
4. 문제: ikj와 kij가 빠른 공통 이유는?
   답: 안쪽 루프가 j라서 B와 C를 행 방향으로 연속 접근하고, A는 scalar처럼 재사용된다.
5. 문제: blocking의 핵심 목적은 spatial locality인가 temporal locality인가?
   답: 주 목적은 temporal locality 강화다. 작은 타일을 cache에 넣고 여러 번 재사용한다.
6. 문제: Java에서 Player[]가 int[] hp보다 대량 체력 검사에 불리할 수 있는 이유는?
   답: Player[]는 객체 참조 배열이고 실제 객체는 흩어져 있을 수 있다. hp만 연속으로 읽기 어렵다.

최종 암기 카드

참고 기준

아래 공개 자료의 개념 흐름과 수식 기준으로 대조했다.

• CMU 15-213 Cache Memories lecture
• CMU 15-213 Memory Hierarchy lecture
• CS:APP Chapter 6 preview
• CS:APP official figure source files
• CS:APP Figure 6.43-6.45 memory mountain XLS
• CS:APP Figure 6.48 matrix multiply performance XLS
• CS:APP memory mountain source code
• CS:APP, A Gallery of Memory Mountains
• Cornell CS 3410 Cache Optimization notes
• V8 hidden classes, V8 elements kinds
• Bun runtime documentation, WebKit JavaScriptCore documentation
• MDN JavaScript typed arrays
• Python C API list object, NumPy ndarray documentation
• Apache Arrow columnar memory format, Polars documentation