Cache Design & Locality

1. Overview

캐시 설계와 지역성(Cache Design & Locality, CDL)은 매우 빠른 CPU와 상대적으로 느린 메인 메모리(DRAM) 사이의 큰 속도 차이(Von Neumann Bottleneck)를 줄이기 위해, 데이터의 시간적/공간적 밀집성을 이용해 중간 저장 계층을 설계하는 메모리 계층 아키텍처입니다.

학습자는 메모리 주소를 태그(Tag), 인덱스(Index), 오프셋(Offset)으로 분해하는 **캐시 매핑 물리(Cache Mapping)**를 살펴보고, 캐시 적중률(Hit Rate)을 높이기 위해 직접 매핑(Direct Mapped)과 완전 연관(Fully Associative) 사이에서 균형을 잡는 세트 연관(Set-Associative) 설계의 트레이드오프를 분석합니다. 나아가 코드의 반복문 구조가 하드웨어의 공간적 지역성(Spatial Locality)과 어떻게 결합하거나 충돌하는지 이해하여, 배열 순회 순서만 바꿔도 프로그램 속도를 10배 이상 개선할 수 있는 로우 레벨 최적화 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 지역성의 물리적 원리 (Physics of Locality): 시간적 지역성(Temporal Locality), 공간적 지역성(Spatial Locality).
• 캐시 아키텍처 (Cache Architecture): 태그(Tag), 인덱스(Index), 블록 오프셋(Block Offset), 라인 사이즈(Cache Line Size).
• 매핑 방식 (Mapping Policies): 직접 사상(Direct Mapped), 세트 연관(Set-Associative), 완전 연관(Fully Associative).
• 교체와 쓰기 정책 (Replacement & Write Policies): LRU(Least Recently Used), FIFO, Write-Through, Write-Back, Write-Allocate.

Out-of-Scope

• 멀티 코어 간 캐시 동기화: 여러 코어가 L1 캐시 데이터를 갱신할 때 발생하는 데이터 불일치 문제 $\rightarrow$ 02-02-02. Cache Coherence & MESI 영역.
• 운영체제의 가상 메모리 페이징: 페이지 폴트(Page Fault)와 디스크 스와핑(Swapping) $\rightarrow$ 03-01. Process & Memory Mechanics 영역.

Boundaries

• CDL vs. Virtual Memory (03-01): 운영체제의 가상 메모리(03-01)가 '메모리가 부족해서 디스크를 메모리처럼 활용하는(Swapping)' 소프트웨어적 추상화라면, CDL은 '메모리가 느리기 때문에 비싼 SRAM을 CPU 가까이에 두고 자주 쓰는 데이터를 먼저 제공하는' 하드웨어 메모리 계층 설계입니다.

3. Counterexample

• 행 우선/열 우선 순회 병목 (Stride Thrashing): C/C++(Row-major)에서 2차원 배열 A[i][j]를 다룰 때, 바깥쪽 루프를 j(열)로, 안쪽 루프를 i(행)로 작성하는 설계입니다. 하드웨어 캐시는 메모리를 1바이트씩 가져오지 않고 64바이트 덩어리(Cache Line) 단위로 읽어오는데(공간적 지역성), 열(Column) 방향으로 메모리를 건너뛰면 가져온 64바이트 중 일부만 사용하고 매번 캐시 미스(Cache Miss)를 발생시켜 알고리즘 속도가 10배 이상 떨어질 수 있습니다.
• 거짓 공유 착각 (False Sharing Ignore): "멀티스레드를 돌리니까 각 스레드별 독립된 변수에 접근하면 병렬화되겠지"라고 믿고, 구조체 안에 인접한 변수 Thread1_Data와 Thread2_Data를 배치하는 상황입니다. 두 변수가 '동일한 64바이트 캐시 라인'에 걸쳐 있으면, 물리적으로는 독립된 데이터임에도 하드웨어 캐시 일관성 프로토콜이 전체 라인을 무효화(Invalidate)시켜 싱글 스레드보다 느려지는 거짓 공유(False Sharing)가 발생합니다.

4. Prerequisites

• 레지스터와 단일 사이클 경로 (Basic): 캐시가 CPU 코어와 어떻게 물리적으로 연결되어 있고, 왜 메모리 읽기에 수백 클럭이 필요한지 폰 노이만 병목의 비용을 이해해야 합니다. (02-01-03 ADP)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 지역성의 물리학 (Physics of Locality)

• Why to Learn: CPU 클럭은 0.2나노초(5GHz)마다 진행되지만 메인 메모리(DRAM)에서 데이터를 가져오려면 100나노초(500클럭)가 걸릴 수 있으므로, 데이터 접근 규칙성을 이용해 이 병목을 줄이기 위함입니다.
• What to Learn:
  • Concepts: 시간적 지역성(Temporal Locality), 공간적 지역성(Spatial Locality), 폰 노이만 병목(Von Neumann Bottleneck).
  • Skills: 캐시 라인(Cache Line / Block Size), 워킹 셋(Working Set).
  • Tools: 배열 순회 벤치마킹.
  • Trade-offs: 캐시를 크게 만들면 히트율은 올라가지만, 전자가 이동하는 물리적 면적이 넓어져 캐시 자체의 접근 속도가 느려지고 CPU 다이(Die) 단가가 증가하는 물리적/경제적 한계.
• How to Learn:
  • 1단계: for (int i=0; i<N; i++) sum += arr[i]; 코드에서 sum 변수는 계속 재사용되므로 시간적 지역성이 강하고, arr[i]는 메모리상에서 바로 옆 주소를 순차적으로 접근하므로 공간적 지역성이 강함을 분석합니다.
  • 2단계: DRAM 칩에서 데이터 4바이트를 요구해도 하드웨어 제어기가 64바이트 덩어리(Cache Line)를 캐시로 가져오는 이유가 공간적 지역성을 활용하기 위한 선읽기 전략임을 살펴봅니다.
• Implement: $10000 \times 10000$ 크기의 2차원 배열을 C/C++로 만들고, 행 우선 순회(Row-major)와 열 우선 순회(Column-major)를 할 때 CPU 클럭 타이머(rdtsc)를 찍어 캐시 미스로 인한 실행 시간 차이(보통 10배 이상)를 콘솔에 증명하는 캐시 브레이커 테스트.

Recommended

Core Topic 02: 주소 해체와 다이렉트 매핑 (Direct-Mapped Cache)

• Why to Learn: 32비트 메모리 주소(0x12345678)가 주어졌을 때, 하드웨어가 매우 짧은 시간 안에 "캐시에 데이터가 있다(Hit)/없다(Miss)"를 판별하는 비트 분할(Bit Splitting) 원리를 이해하기 위해서입니다.
• What to Learn:
  • Concepts: 태그(Tag), 인덱스(Index), 바이트 오프셋(Byte Offset), 유효 비트(Valid Bit).
  • Skills: 주소 파티셔닝(Address Partitioning), 캐시 적중/실패(Hit/Miss) 판별.
  • Tools: 하드웨어 비교기(Comparator).
  • Trade-offs: 캐시 인덱스를 통해 배열처럼 $O(1)$ 만에 슬롯을 찾아가는 높은 속도(Direct Mapped) vs 서로 다른 메모리 주소들이 같은 캐시 슬롯(Index)을 배정받아 서로 밀어내는 핑퐁 현상(Conflict Miss)의 부작용.
• How to Learn:
  • 1단계: 64바이트 블록 크기면 하위 6비트($2^6$)를 오프셋으로 쓰고, 캐시 슬롯이 1024개면 다음 10비트($2^{10}$)를 인덱스로 쓰고, 남은 상위 비트 전체를 태그(Tag)로 쓰는 비트 분할 구조를 살펴봅니다.
  • 2단계: 메모리 0x0000(주소 A)과 0x1000(주소 B)이 공교롭게도 인덱스 비트가 완전히 일치할 때, 루프 안에서 A와 B를 번갈아 읽으면 매번 캐시 라인이 비워지고 채워지는 최악의 스래싱(Thrashing)이 일어남을 해부합니다.
• Implement: 32비트 주소, 캐시 용량(예: 32KB), 블록 크기(64B)를 파라미터로 입력하면, 주소를 2진수로 분해하여 [Tag: 17비트] [Index: 9비트] [Offset: 6비트]의 구역을 시각적으로 쪼개고, 해당 인덱스 슬롯에 태그를 기록하는 가상 다이렉트 매핑 시뮬레이터 로직 작성.

Practical

Core Topic 03: 세트 연관 설계와 충돌 해결 (Set-Associative Cache)

• Why to Learn: 다이렉트 매핑의 고질적인 주소 충돌(Conflict Miss) 핑퐁을 줄이고, 동시에 풀 매핑(Fully Associative)의 높은 전력 소모를 피하는 현대 CPU L1/L2 캐시의 타협점 설계를 이해하기 위함입니다.
• What to Learn:
  • Concepts: $N$-way 세트 연관(Set-Associative), 세트(Set)와 슬롯(Way), 완전 연관(Fully Associative).
  • Skills: 충돌 미스(Conflict Miss) 감소율, 병렬 하드웨어 검색(Parallel Tag Search).
  • Tools: 교체 알고리즘(LRU 기법 구조).
  • Trade-offs: 4-Way 설계를 하면 인덱스 하나당 슬롯이 4개 생겨 충돌 미스가 크게 줄어드는 효과 vs 4개의 슬롯 태그를 동시에 읽고 비교기(Comparator) 4개를 동작시켜야 하므로 칩 면적과 전력 소모(발열)가 늘어나는 하드웨어 비용.
• How to Learn:
  • 1단계: 세트 연관 방식은 주소를 나누어 세트 번호(Index)를 찾은 다음, 그 안에서는 모든 슬롯(Way)의 태그를 동시에 비교(Fully Associative)하는 '다이렉트와 풀 매핑의 하이브리드' 구조임을 분석합니다.
  • 2단계: 캐시 미스의 3대 원인인 3C(Compulsory(어쩔 수 없는 최초 접근), Capacity(용량 초과), Conflict(충돌)) 중에서, N-Way 설계가 Conflict 미스를 어떻게 줄이는지 살펴봅니다.
• Implement: 메모리 접근 주소 트레이스(Trace) 리스트를 입력하고, Direct-Mapped 방식과 4-Way Set-Associative 방식일 때의 총 Cache Miss 횟수를 카운트하여 4-Way가 Conflict Miss를 얼마나 줄이는지 통계 로그를 출력하는 캐시 모델.

Advanced

Core Topic 04: 쓰기 정책과 LRU 교체 알고리즘 (Write Policies & Replacement)

• Why to Learn: 캐시에 데이터를 쓸 때 메인 메모리까지 즉시 갱신하면 폰 노이만 병목이 다시 커지므로, 캐시에 먼저 쓰고 캐시 라인이 교체될 때 메모리에 반영하는 성능 최적화 방식을 설계하기 위해서입니다.
• What to Learn:
  • Concepts: 라이트 스루(Write-Through), 라이트 백(Write-Back), 라이트 할당(Write-Allocate).
  • Skills: 더티 비트(Dirty Bit), LRU(Least Recently Used) 추적 논리, 의사-LRU(Pseudo-LRU) 트리.
  • Tools: 쓰기 버퍼(Write Buffer).
  • Trade-offs: 캐시에 데이터가 변경될 때마다 메모리에 즉시 반영하는 Write-Through의 단순한 일관성(구현 쉬움) vs 캐시에 '더티(Dirty)' 표시를 붙이고 교체될 때 한 번에 반영하는 Write-Back의 높은 속도와 더 어려운 일관성 동기화.
• How to Learn:
  • 1단계: 4-Way 세트에서 빈자리가 없을 때 4개 중 어떤 라인을 교체하고 새 데이터를 넣을지 결정하기 위해, "가장 오래전에 사용한 라인을 교체한다(LRU)"는 정책을 하드웨어로 구현하는 에이징(Aging) 카운터 구조를 분석합니다.
  • 2단계: N-Way가 16-Way 이상 커지면 실제 LRU를 구현하기 위해 유지해야 하는 카운터 비트 수가 기하급수적으로 증가하므로, 트리를 써서 '대략 오래된 그룹'을 찾는 Pseudo-LRU의 하드웨어 비용 절감 방식을 살펴봅니다.
• Implement: 클래스로 CacheLine(tag, data, valid, dirty, last_used_tick)을 정의하고, CPU가 Store(Address, Data) 연산을 반복할 때 Write-Back 정책에 따라 더티 비트만 켜지고 메모리 I/O가 0건이다가, LRU로 교체되는 순간(Eviction)에만 메모리 갱신 이벤트가 발생하는 워크플로우를 모사하는 더티 비트 시뮬레이터.

7. Terminology

8. References

Primary

• [P1] CS2023 - AR/Memory System Organization and Architecture — 계층 구조 표준.
• [P2] SWEBOK v4.0 - Computing Foundations / Memory Hierarchy — Industry definitions.

Secondary

• [Computer Architecture: A Quantitative Approach] Hennessy & Patterson — The definitive source for AMAT.
• [What Every Programmer Should Know About Memory] Ulrich Drepper — Crucial guide for developers.

Industry

• [Intel 64 and IA-32 Architectures Optimization Reference Manual] — Real-world cache behaviors.
• [ARM Cache Management Guide] — Practical mobile/embedded cache tuning.

9. Final Checklist

Primary

• 32KB 4-way Set Associative 캐시에서 32비트 주소가 [Tag | Index | Offset]으로 물리적으로 어떻게 분할되는지 계산할 수 있는가? (P1)
• '공간적 지역성'이 보장되지 않는 무작위 주소 접근 패턴이 캐시 계층 구조에서 왜 비용이 큰지 AMAT 공식을 근거로 입증 가능한가? (P1)

Secondary

• 캐시 라인 크기(e.g. 64 Bytes)가 너무 커졌을 때 발생할 수 있는 'False Sharing'과 'Internal Fragmentation'의 물리적 위험을 소통 가능한가?
• LRU(Least Recently Used) 교체 알고리즘이 '시간적 지역성' 원리를 하드웨어적으로 어떻게 구현하는지 논리적으로 설명할 수 있는가?

Industry

• 고성능 게임 엔진이나 DB 커널 설계 시, 데이터 구조를 'Cache-friendly'하게 설계(SOA vs AOS)하여 성능을 2배 이상 끌어올리는 전략을 제안할 수 있는가? (SFIA)
• 리눅스 perf 툴을 통해 캐시 미스 통계를 분석하고, 특정 코드 블록의 캐시 미스 발생 원인을 하드웨어 사상 관점에서 추론할 수 있는가?