Cache Design & Locality

1. Overview

캐시 설계 및 지역성(Cache Design & Locality, CDL)은 현대 컴퓨팅에서 CPU 연산 속도와 메인 메모리 접근 속도 사이의 거대한 간극, 즉 '메모리 벽(Memory Wall)'을 물리적으로 우회하기 위한 전략적 고속 저장소 아키텍처입니다.

학습자는 정보가 재사용될 확률이 높다는 **지역성(Locality)**의 원리를 배우고, 이를 하드웨어로 구현한 Direct-mapped, Fully Associative, Set-associative와 같은 캐시 매핑 정책의 물리적 구조를 익힙니다. 이는 단순한 버퍼링을 넘어, 데이터가 어떻게 메모리에서 캐시 라인(Cache Line)으로 사상되고, 태그(Tag) 비교를 통해 히트(Hit)와 미스(Miss)가 결정되는지 분석함으로써, 소프트웨어의 성능을 결정짓는 하드웨어적 병목을 근본적으로 이해하는 통찰을 제공합니다.

2. Scope & Boundaries

In-Scope

• Locality Physics: 시간적 지역성(Temporal)과 공간적 지역성(Spatial)의 정의와 활용
• Cache Hierarchy: L1, L2, L3 캐시의 계층 구조 및 속도/용량 트레이드오프
• Mapping Mechanics: 메모리 주소의 비트 분해(Tag, Index, Offset) 및 매핑 기술
• Replacement Policies: LRU, FIFO 등 한정된 캐시 공간의 관리 물리

Out-of-Scope

• 멀티코어 환경에서의 데이터 일관성 이슈 (02-02-02 Cache Coherence 영역으로 위임)
• 캐시 쓰기 정책(Write-through/back) 상세 (동일 Mid-level 내 분화)

Boundaries

• CDL vs. Virtual Memory: 가상 메모리가 '용량 한계 극복과 보호'에 집중한다면, 캐시는 오직 '지연 시간(Latency) 감소와 연산 속도 극대화'에 집중하는 물리 장치입니다.

3. Counterexample

• 단순히 "빠른 메모리다"라는 설명은 CDL 학습이 아닙니다. 왜 특정 배열 순회 방식(Row-major vs. Column-major)이 공간적 지역성에 기대를 거는 캐시 구조에서 성능 차이를 극적으로 발생시키는지 물리적으로 입증할 수 있어야 하고, 주소 비트의 인덱스(Index) 필드가 중복될 때 발생하는 'Conflict Miss'의 수리적 원인을 지적할 수 있어야 합니다.

4. Prerequisites

• Integer & Float Representations (Basic): 주소 비트 단위 연산 이해가 필수입니다. (02-01-02 IFR)
• ALU & Data Path Design (Recommended): CPU의 메모리 접근 사이클 지식이 권장됩니다. (02-01-03 ADP)

5. Learning Map

1. Locality Observation: 프로그램 실행 패턴에서 데이터의 집중 현상을 포착합니다.
2. Indexing Logic: 거대한 메모리 주소를 작은 캐시 칸으로 사상하는 물리적 필터링을 구축합니다.
3. Hierarchy Scaling: 여러 층의 캐시를 두어 적중률(Hit rate)과 접근 비용을 최적화합니다.
4. Hardware Buffering: 캐시 라인 단위로 데이터를 실어 날라 공간적 이득을 극대화합니다.

6. Learning Topics

Basic

Core: 지역성의 원리와 유형 (Principles of Locality)

• Why to Learn: 프로그램의 동작 패턴이 왜 캐시라는 장치를 물리적으로 유효하게 만드는지 이해하기 위함입니다.
• What to Learn:
  • 시간적 지역성: 한 번 접근한 정보는 곧 다시 접근될 것이라는 물리
  • 공간적 지역성: 접근한 정보 근처의 정보가 곧 접근될 것이라는 물리
  • 작업 집합(Working Set)의 개념과 이동성
• How to Learn:
  • 단순 루프 코드(For문)에서 카운터 변수와 배열 데이터가 각각 어떤 지역성을 활용하는지 구분 실습
  • 캐시가 전혀 없는 가상의 시스템에서 지역성이 무시될 때 발생하는 지연 시간 누적 시뮬레이션
• Implement: 특정 메모리 접근 스트림을 분석하여 시간적/공간적 지역성 점수를 산출하는 프로파일러

Recommended

Core: 캐시 매핑 아키텍처 (Mapping Strategies)

• Why to Learn: 하드웨어가 주소 값을 보고 캐시의 어느 칸을 찾아갈지 결정하는 고속 로직을 배우기 위해서입니다.
• What to Learn:
  • Direct Mapped: 하나의 주소가 하나의 칸에만 고정되는 단순 물리
  • Fully Associative: 어디든 들어갈 수 있지만 비교 비용이 비싼 구조
  • $n$-way Set Associative: 현대 CPU의 표준인 절충형 물리 구조
• How to Learn:
  • 메모리 주소를 [Tag | Index | Offset] 비트로 쪼개고, 캐시 크기에 따른 각 필드의 비트 수 계산 연습
  • 특정 주소 패턴이 들어올 때 Conflict Miss가 발생하는 'Thrashing' 현상 가시화 분석
• Implement: 셋업된 캐시 규격에 따라 주소를 입력하면 Hit/Miss 여부를 리턴하는 캐시 시뮬레이터

Practical

Core: 캐시 히트/미스와 성능 (Hit Rate & Performance)

• Why to Learn: 캐시 적중률 1%의 차이가 실제 시스템 성능에 미치는 파괴적인 영향력을 정량화하기 위함입니다.
• What to Learn:
  • AMAT (Average Memory Access Time) 공식: $Hit\_Time + Miss\_Rate \times Miss\_Penalty$
  • 3C Miss 모델: Compulsory, Capacity, Conflict 미스의 물리적 발생 원인
  • 캐시 라인 크기(Line Size) 결정이 적중률과 대역폭에 미치는 영향
• How to Learn:
  • L1 히트 타임과 메모리 미스 패널티(100배 이상)의 차이를 보고 전체 성능 저하율 계산 실습
  • 블록 크기를 늘렸을 때 공간적 지역성 이득과 캐시 오염(Pollution) 사이의 트레이드오프 분석
• Implement: 다양한 상황의 AMAT를 계산하고, 목표 성능을 위해 필요한 최소 캐시 적중률을 제안하는 툴

Advanced

Core: 소프트웨어 수준의 캐시 최적화 (Software Cache Awareness)

• Why to Learn: 하드웨어 설계를 바꿀 수 없는 소프트웨어 개발자가 코드 구조만으로 캐시 이득을 극대화하기 위해서입니다.
• What to Learn:
  • 루프 타일링(Loop Tiling/Blocking): 데이터 재사용성을 높이기 위한 타일링 물리
  • 데이터 정렬(Alignment)과 패딩: 의도치 않은 캐시 라인 중첩 방지
  • Prefetching: 하드웨어/소프트웨어가 미리 데이터를 당겨오는 전술
• How to Learn:
  • 거대 행렬 곱셈 알고리즘에 타일링 기법을 적용했을 때 캐시 미스 횟수가 줄어드는 수리적 입증
  • 'False Sharing' 현상이 무엇인지 이해하고, 이를 피하기 위한 변수 배치 전략 수립练习
• Implement: 캐시 라인 경계를 고려하여 구조체 멤버 순서를 재배치해주는 메모리 레이아웃 최적화기

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 툴을 통해 캐시 미스 통계를 분석하고, 특정 코드 블록의 캐시 미스 발생 원인을 하드웨어 사상 관점에서 추론할 수 있는 가?