🧠 메모리 교재 · 04_캐시

캐시와 캐시 친화적 코드

목표 학습 시간: 105분 + 복습 15분 · 전공 수준 정독용

이 챕터를 마치면: (1) 주소가 캐시의 어디로 매핑되는지(태그/세트/오프셋) 손으로 쪼개고, (2) 3종 미스를 구분해 각각 줄이는 법을 알고, (3) 행/열 순회의 미스율을 정량적으로 계산하고, (4) 블로킹(타일링)이 왜 작동하는지 재사용 관점에서 설명할 수 있다.

0. 학습 지도 (105분)

구간	분	내용
1	12	캐시 라인 — 전송의 단위
2	28	캐시 구조: 매핑·연관도·주소 분해
3	15	3종 미스와 쓰기 정책
4	30	캐시 친화적 코드: 순회·AoS/SoA·블로킹
5	5	프리페치와 측정
6	—	흔한 오해·정리
복습	15	인출 + 정량 문제

1. 캐시 라인 — 전송의 단위

세션 1에서 "데이터는 블록 단위로 층 사이를 오간다"고 했다. 캐시에서 그 블록이 캐시 라인(cache line, 보통 64바이트) 이다. 이 한 가지가 캐시 성능의 절반을 설명한다.

CPU가 메모리에서 int 하나(4B)를 읽어도, 하드웨어는 그 주소가 속한 64B 라인 전체를 캐시에 올린다. 즉 int 16개가 한 번에 따라온다.

a[0] 하나 요청 → 메모리에서 [ a[0] a[1] ... a[15] ] 64B 한 라인을 캐시로 적재
                 이후 a[1]..a[15] 접근은 전부 캐시 히트 (거의 공짜)

이것이 공간적 지역성이 공짜 성능을 주는 물리적 메커니즘이다. 반대로, 라인에서 단 1개만 쓰고 버리면(예: 큰 stride 접근) 64B를 옮기고 4B만 쓰는 셈 — 대역폭의 15/16을 낭비한다. "라인을 알뜰히 쓰는가"가 캐시 최적화의 본질이다.

2. 캐시 구조 — 주소는 캐시의 어디로 가는가

2.1 세 가지 사상(mapping) 방식

캐시는 라인을 담는 칸들의 모음이다. "어떤 메모리 주소가 어느 칸에 들어갈 수 있는가"로 셋이 나뉜다.

직접 사상(direct-mapped): 한 주소가 들어갈 칸이 딱 하나. 단순·빠르지만, 같은 칸에 매핑되는 두 주소를 번갈아 쓰면 서로를 계속 쫓아낸다(충돌 미스).
완전 연관(fully-associative): 어떤 라인이든 아무 칸에나 들어갈 수 있다. 충돌은 없지만, 찾을 때 모든 칸을 비교해야 해 비싸다 → 작은 캐시(TLB 등)에만.
집합 연관(set-associative): 절충. 칸들을 세트로 묶고, 한 주소는 정해진 한 세트 안의 여러 칸(way) 중 하나에 들어간다. "8-way set associative" = 한 세트에 8칸. 대부분의 L1/L2/L3가 이 방식.

연관도(way 수)가 높을수록 충돌 미스가 줄지만 하드웨어가 복잡해진다.

2.2 주소 분해 — 태그 / 세트 인덱스 / 블록 오프셋

물리(또는 가상) 주소를 세 부분으로 쪼개 캐시를 찾는다.

 [        태그 (tag)        |  세트 인덱스  |  블록 오프셋  ]
                                            └ 라인 안에서 몇 번째 바이트
                              └ 어느 세트로 갈지
  └ 그 세트의 어느 way가 진짜 이 주소인지 식별

블록 오프셋 비트 = log₂(라인 크기). 64B 라인 → 6비트.
세트 인덱스 비트 = log₂(세트 수).
태그 = 나머지 상위 비트.

2.3 손으로 쪼개기 — 워크드 예제

예제. 32KB, 8-way 집합 연관, 라인 64B 캐시(흔한 L1 구성)라고 하자. 주소는 48비트로 본다.

총 라인 수    = 32KB / 64B               = 512 라인
세트 수       = 512 / 8(way)             = 64 세트
오프셋 비트   = log2(64)                 = 6 비트
세트 인덱스   = log2(64)                 = 6 비트
태그 비트     = 48 - 6 - 6               = 36 비트

이제 어떤 주소가 주어지면, 하위 6비트는 라인 안 위치, 그다음 6비트는 세트 번호, 나머지 36비트는 그 세트에서 비교할 태그다. 이 분해를 직접 할 수 있으면 캐시 구조를 안다고 말할 수 있다.

주소 분해 — 세트 인덱스로 세트를 고르고, 그 세트의 8개 way 중 태그가 맞는 라인이 히트, 오프셋이 라인 내 위치.

통찰: 세트 인덱스가 주소의 중간 비트라는 점이 중요하다. 그래서 정확히 캐시 크기만큼 떨어진(또는 그 배수) 두 주소는 같은 세트로 가 충돌하기 쉽다 — 이것이 2의 거듭제곱 stride가 종종 성능 함정인 이유(3.1의 conflict 미스).

2.4 교체 정책 — 세트가 꽉 차면 누구를 쫓아내나

집합 연관 캐시에서 한 세트의 way가 모두 차 있는데 새 라인을 넣어야 하면, 그 세트 안에서 하나를 골라 내보내야(eviction) 한다. 이 선택이 캐시판 교체 정책이다(세션 6의 페이지 교체와 같은 문제의 더 작은 버전).

LRU(최근 최소 사용): 가장 오래 안 쓴 way를 버린다. 시간적 지역성에 잘 맞지만, 정확한 LRU는 way마다 사용 순서를 갱신해야 해 연관도가 높으면 하드웨어가 비싸다.
pseudo-LRU(근사 LRU): 트리 비트 한 묶음으로 "대충 오래된 쪽"을 가리키는 싼 근사. 실제 L1/L2가 흔히 쓴다.
랜덤 / RRIP 계열: 무작위 희생은 거의 공짜이고 의외로 나쁘지 않다. 최신 고연관 캐시는 RRIP로 "한 번 쓰고 버려질 라인"을 우선 내보내기도 한다.

핵심: CPU 캐시 교체는 하드웨어가 자동으로 하며 개발자가 직접 못 고른다 — 세션 6의 페이지 교체(OS가 소프트웨어로 수행)와 "누가 하느냐"가 다르다. 다만 둘 다 지역성에 베팅한다는 원리는 같다.

2.5 포함 관계 — inclusive · exclusive · NINE

여러 층 캐시(L1/L2/L3) 사이의 데이터 중복 정책도 설계 선택이다(세션 1의 "위층은 아래층의 부분집합" 보강).

inclusive(포함): 상위(L1)에 있는 라인은 하위(L3)에도 반드시 있다. 다른 코어가 그 라인을 갖는지 L3만 보면 돼 코히어런스 검색이 쉽다(세션 10). 대신 용량이 중복돼 실효 용량이 준다.
exclusive(배타): 같은 라인을 한 층에만 둬 실효 용량을 키운다(일부 AMD). 코히어런스가 복잡해진다.
NINE(non-inclusive non-exclusive): 강제하지 않는 절충(많은 Intel L3).

"L1에 있는데 L3에서 쫓겨나면?"(inclusive면 L1도 무효화당함) 같은 성능 질문이 여기서 나온다.

3. 3종 미스(3 C's)와 쓰기 정책

3.1 미스의 세 원인 — 그리고 각각의 처방

미스 종류	원인	줄이는 법
Compulsory(강제)	그 라인을 난생처음 접근	프리페치, 라인을 알뜰히 쓰기(공간적 지역성)
Capacity(용량)	작업 집합이 캐시보다 큼	작업 집합 축소 — 블로킹, 데이터 줄이기
Conflict(충돌)	서로 다른 주소가 같은 세트로 매핑돼 쫓아냄	연관도↑, 데이터 배치 조정(2의 거듭제곱 stride 회피)

이 분류가 중요한 이유: 미스를 봤을 때 어떤 처방을 쓸지가 종류에 따라 다르기 때문이다. 작업 집합이 캐시를 넘쳐서 나는 capacity 미스는 연관도를 올려도 안 풀리고, 데이터를 줄이거나 블로킹해야 한다.

3.2 쓰기 정책 (간단히, 하지만 알아둘 것)

읽기만 캐시되는 게 아니다. 쓰기도 정책이 있다.

write-back(후기입): 쓰기를 일단 캐시에만 반영하고(dirty 표시), 그 라인이 쫓겨날 때 메모리에 기록. 메모리 트래픽이 적어 보통 이 방식.
write-through(직기입): 쓸 때마다 메모리에도 즉시 기록. 단순하지만 트래픽 많음.
write-allocate: 쓰기 미스 시 라인을 캐시로 가져온 뒤 쓴다(이후 그 라인 재사용에 유리).

실무 함의: 쓰기도 라인 단위로 일어난다. 그래서 라인의 일부만 쓰는 패턴, 그리고 세션 10의 false sharing(다른 코어가 같은 라인을 번갈아 쓰는 것)이 성능 문제가 된다.

4. 캐시 친화적 코드 — 정량적으로

여기가 이 세션의 실전 핵심이다. 빅오가 같아도 상수가 캐시에서 갈린다(세션 1)는 명제를 코드로 증명한다.

4.1 행 우선 vs 열 우선 — 미스율 계산

C는 2차원 배열을 행 우선(row-major) 으로 저장한다: m[0][0], m[0][1], ..., m[0][N-1], m[1][0], .... 즉 같은 행의 원소가 메모리에 연속한다.

// (A) 행 우선 순회
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += m[i][j];

// (B) 열 우선 순회
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        sum += m[i][j];

미스율을 계산해 보자. 라인 64B, int 4B → 라인당 int 16개.

(A) 행 우선: m[i][0], m[i][1], ...는 메모리 연속. 라인 하나를 가져오면 16개를 연달아 히트한다. → 16접근당 1미스, 미스율 ≈ 1/16 ≈ 6.25%.
(B) 열 우선: m[0][j], m[1][j], ...는 한 행 폭(N×4B)씩 점프. 행렬이 충분히 크면(한 행이 캐시 라인보다 큼) 매 접근이 새 라인이고, 가져온 라인의 나머지 15개는 다음 행으로 넘어가기 전에 쫓겨난다. → 거의 매 접근이 미스, 미스율 ≈ 100%.

즉 (B)는 (A)보다 약 16배 많은 미스를 낸다. 시간복잡도는 둘 다 O(N²)인데, 실측 속도는 수 배~십수 배 차이 난다(미스 페널티가 크니까 — 세션 1의 AMAT). 이것이 루프 교환(loop interchange) 최적화의 근거다: 가장 안쪽 루프가 메모리 연속 방향을 훑도록 순서를 맞춰라.

열 우선 (B) · 안쪽 루프 i

행이 메모리에 연속 → 라인 1개로 16개 히트 미스율 ≈ 1/16 (6.25%) 행 폭만큼 점프 → 매 접근 새 라인 미스율 ≈ 100% (약 16배)

C는 행 우선 저장 — 안쪽 루프가 행(j)을 훑으면 라인을 알뜰히 쓰고(좌), 열(i)을 훑으면 매번 새 라인이라 ~16배 미스(우).

4.2 AoS vs SoA — 라인 활용률

// AoS (Array of Structs): 객체 단위로 뭉침
struct P { float x, y, z; int id; };   // 16B
struct P arr[N];
// x들의 합만 구한다면? 각 라인(64B=4객체)에서 x는 4개뿐,
// 나머지 y,z,id 12개는 끌려왔다 버려진다 → 라인 활용률 4/16 = 25%

// SoA (Struct of Arrays): 필드별로 따로
struct Ps { float x[N], y[N], z[N]; int id[N]; };
// x[]만 순회 → x들이 라인에 빽빽(16개/라인) → 활용률 100%

"여러 객체에서 특정 필드만 쭉 훑는" 접근 패턴이면 SoA가 라인을 4배 알뜰히 써 캐시 미스를 크게 줄인다. 반대로 "한 객체의 모든 필드를 함께 쓰는" 패턴이면 AoS가 낫다. 접근 패턴이 레이아웃을 결정한다.

4.3 블로킹(타일링) — capacity 미스를 죽이는 법

행렬 곱 C = A × B를 보자(N×N).

// 단순(naive) 곱
for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
    for (int k = 0; k < N; k++)
      C[i][j] += A[i][k] * B[k][j];

문제: 가장 안쪽에서 A[i][k]는 행 방향(좋음)이지만 B[k][j]는 열 방향(stride N, 나쁨). 게다가 i가 한 칸 갈 때마다 B 전체를 다시 훑는다. B가 캐시보다 크면(N이 조금만 커도) B의 라인들은 재사용되기 전에 쫓겨나 매번 다시 적재 — 전형적 capacity 미스다.

블로킹의 아이디어: 행렬을 B×B 타일로 쪼개, 타일들을 캐시에 올려둔 동안 그 안에서 가능한 모든 곱셈-덧셈을 끝내 재사용을 극대화한다.

for (int ii = 0; ii < N; ii += BS)
 for (int jj = 0; jj < N; jj += BS)
  for (int kk = 0; kk < N; kk += BS)
   for (int i = ii; i < ii+BS; i++)
    for (int j = jj; j < jj+BS; j++)
     for (int k = kk; k < kk+BS; k++)
      C[i][j] += A[i][k] * B[k][j];

왜 빨라지나(재사용 분석): 한 번 캐시에 올린 A 타일·B 타일·C 타일을, 쫓겨나기 전에 그 블록의 모든 연산에 재사용한다. 대략 블록 크기 BS에 비례해 데이터 재사용 횟수가 늘고, 메모리에서 새로 끌어오는 횟수가 준다. 타일 크기는 세 타일(A,B,C)이 캐시에 동시에 들어가도록 정한다:

3 × BS² × sizeof(요소) ≤ 캐시 크기   →   BS를 이 조건에서 최대로

블로킹은 작업 집합을 "캐시 안에 욱여넣어" capacity 미스를 구조적으로 없애는, 세션 1 "작업 집합" 개념의 직접적 응용이다.

4.4 데이터 구조 선택의 캐시 비용

배열 vs 연결 리스트: 배열은 연속(공간적 지역성↑), 리스트는 노드가 힙에 흩어져(pointer chasing) 미스↑. 같은 O(n) 순회라도 배열이 빠르다(세션 1 예제).
해시맵 충돌 처리: 개방 주소법(배열 연속) vs 체이닝(포인터 점프)도 캐시 관점에서 갈린다.

5. 프리페치와 측정

하드웨어 프리페처: CPU는 순차/일정 stride 접근 패턴을 감지해 다음 라인을 미리 가져온다. 그래서 순차 접근은 더 빨라진다. 반대로 무작위/포인터 점프는 프리페처가 예측 못 해 이득을 못 본다 — pointer chasing이 이중으로 느린 또 다른 이유.
측정 도구: 리눅스 perf stat -e cache-misses,cache-references ./a.out 로 실제 미스 수를 볼 수 있다. 행/열 순회, AoS/SoA, 블로킹 전후를 직접 측정해 보면 4절의 계산이 살아 있는 숫자로 확인된다(강력 권장).

6. 흔한 오해 바로잡기

❌ "캐시는 바이트 단위로 가져온다." → 라인(64B) 단위. 1바이트를 읽어도 64B가 온다.
❌ "캐시는 내가 직접 채운다." → 하드웨어 캐시는 자동. 접근 패턴으로만 간접 제어한다.
❌ "충돌 미스는 연관도를 올리면 다 풀린다." → conflict는 그렇지만 capacity 미스는 작업 집합을 줄여야(블로킹) 풀린다. 종류 구분이 처방을 가른다.
❌ "2차원 배열 순회 순서는 취향." → C는 행 우선이라 안쪽 루프가 행을 훑어야(j가 안쪽) 빠르다. 반대면 ~16배 미스.
❌ "구조체는 작을수록 무조건 좋다." → 접근 패턴이 핵심. 필드별 순회면 SoA, 객체 단위면 AoS.

7. 한 장 정리

전송 단위는 64B 라인. 라인을 알뜰히 쓰는가가 캐시 최적화의 본질.
주소는 태그/세트 인덱스/오프셋으로 쪼개져 (집합 연관) 캐시를 찾는다. 오프셋=log₂(라인), 세트=log₂(세트 수).
미스 3종(compulsory/capacity/conflict)은 각기 다른 처방을 요구한다.
캐시 친화 코드: 행 우선 순회(미스율 1/16 vs 100%), SoA(필드 순회 시 활용률 100%), 블로킹(capacity 미스 제거, 3·BS²·요소 ≤ 캐시).
프리페처는 순차/일정 stride를 좋아하고 포인터 점프를 싫어한다. perf로 미스를 측정하라.

8. 복습 (15분) — 답을 가리고

Q1. 라인이 64B인데 int 하나를 읽으면 실제로 무엇이, 왜 올라오나?

그 주소가 속한 64B 라인 전체(=int 16개). 캐시는 라인 단위로 전송하며, 이는 공간적 지역성에 대한 베팅이다 — 곧 이어질 인접 접근을 히트로 만든다.

Q2. 64KB, 4-way, 라인 64B 캐시의 오프셋·세트 인덱스·태그 비트를 구하라(48비트 주소).

라인 수 = 64KB/64 = 1024. 세트 수 = 1024/4 = 256. 오프셋 = log2(64) = 6비트. 세트 인덱스 = log2(256) = 8비트. 태그 = 48−6−8 = 34비트.

Q3. N=1024 int 행렬에서 행 우선과 열 우선 순회의 미스율을 추정하고 배율을 말하라.

행 우선 ≈ 1/16 ≈ 6.25%(라인당 16개 히트). 열 우선 ≈ ~100%(매 접근 새 라인). 약 16배 차이.

Q4. capacity 미스와 conflict 미스를 구분하고, 각각의 처방을 말하라.

capacity: 작업 집합이 캐시보다 커서 발생 → 작업 집합 축소(블로킹·데이터 다이어트). conflict: 다른 주소가 같은 세트로 매핑돼 발생 → 연관도↑ 또는 2의 거듭제곱 stride 회피·배치 조정.

Q5. x들의 합만 반복해서 구하는 코드에서 AoS와 SoA의 라인 활용률을 계산하라(struct P{float x,y,z;int id;}).

객체 16B, 라인 64B → 라인당 4객체. AoS: x는 라인당 4개뿐 → 활용률 4/16 = 25%. SoA: x[]만 빽빽 → 라인당 16개 → 100%. SoA가 4배 알뜰.

Q6. 블로킹이 단순 행렬 곱보다 빠른 이유를 "재사용"과 "미스 종류"로 설명하라.

단순 곱은 B를 i마다 다시 훑어 B가 캐시보다 크면 재사용 전에 쫓겨나 capacity 미스가 폭증한다. 블로킹은 B×B 타일을 캐시에 올린 동안 그 안의 모든 곱셈-덧셈에 재사용해, 메모리 재적재 횟수를 BS에 비례해 줄인다. 타일은 3·BS²·요소 ≤ 캐시가 되도록 정한다.

Q7. 세션 1·2와의 연결을 한 문장씩.

세션 1: 라인 단위 전송·미스 페널티는 AMAT로 정량화된다(미스율↓이 곧 속도). 세션 2: 구조체 패딩으로 객체가 커지면 라인당 담기는 수가 줄어 공간적 지역성이 나빠진다(레이아웃이 캐시를 좌우).

다음: 세션 5 — 가상 메모리 ① 페이징 (이어지는 파일)