캐시 메모리
캐시 메모리¶
개요¶
캐시(Cache) 메모리는 CPU와 메인 메모리 사이의 속도 격차를 해소하기 위한 고속 버퍼 메모리입니다. 캐시의 설계는 컴퓨터 성능에 직접적인 영향을 미치며, 사상 방식, 교체 정책, 쓰기 정책 등 다양한 설계 결정이 필요합니다. 이 레슨에서는 캐시의 동작 원리와 다양한 설계 기법을 학습합니다.
난이도: ⭐⭐⭐
선수 지식: 메모리 계층 구조, 지역성 원리
목차¶
1. 캐시의 개념과 동작¶
1.1 캐시란?¶
캐시(Cache)의 어원: 프랑스어 "cacher" (숨기다)
정의: CPU와 메인 메모리 사이에 위치한 소용량 고속 메모리
목적: 자주 사용되는 데이터를 빠르게 접근할 수 있도록 유지
┌─────────────────────────────────────────────────────────────┐
│ 캐시의 역할 │
├─────────────────────────────────────────────────────────────┤
│ │
│ CPU 캐시 메인 메모리 │
│ ┌───────┐ ┌───────────┐ ┌───────────┐ │
│ │ │ 빠른 접근 │ │ 느린 접근 │ │ │
│ │ │◀────────▶│ │◀────────▶│ │ │
│ │ │ (~4 ns) │ │ (~60 ns) │ │ │
│ └───────┘ └───────────┘ └───────────┘ │
│ │
│ 자주 사용하는 데이터를 캐시에 유지하여 평균 접근 시간 단축 │
│ │
└─────────────────────────────────────────────────────────────┘
1.2 캐시 구조 기초¶
캐시 라인 (Cache Line) / 블록 (Block):
- 캐시와 메모리 간 데이터 전송의 기본 단위
- 일반적으로 64바이트 (현대 프로세서)
┌─────────────────────────────────────────────────────────────┐
│ Cache Line (64 bytes) │
├─────────┬─────────────────────────────────────────────────┬──┤
│ Valid │ Tag │ │
│ (1b) │ (주소 상위) │ │
├─────────┴─────────────────────────────────────────────────┴──┤
│ ┌────────────────────────────────────────────────────────┐ │
│ │ Data (64 bytes) │ │
│ │ 0x00 0x01 0x02 ... 0x3E 0x3F │ │
│ └────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────┘
캐시 용어:
- 히트(Hit): 요청 데이터가 캐시에 있음
- 미스(Miss): 요청 데이터가 캐시에 없음
- 히트율(Hit Rate): 히트 수 / 총 접근 수
- 미스율(Miss Rate): 1 - 히트율
1.3 주소 분해¶
메모리 주소를 캐시 접근에 사용하기 위해 분해:
32비트 주소 예시 (4KB 캐시, 64B 라인, 직접 사상):
┌─────────────────────────────────────────────────────────────┐
│ 31 12 11 6 5 0 │
│ ├─────────────────────────┼─────────────┼────────────────┤ │
│ │ Tag (20b) │ Index (6b) │ Offset (6b) │ │
│ └─────────────────────────┴─────────────┴────────────────┘ │
└─────────────────────────────────────────────────────────────┘
Offset (6비트):
- 캐시 라인 내 위치
- 64바이트 = 2^6, 따라서 6비트
Index (6비트):
- 캐시 라인 선택
- 4KB / 64B = 64 라인 = 2^6, 따라서 6비트
Tag (20비트):
- 같은 인덱스의 다른 주소 구분
- 나머지 비트 = 32 - 6 - 6 = 20비트
1.4 캐시 동작 흐름¶
캐시 읽기 동작:
┌─────────────────────────────────────────────────────────────┐
│ CPU 주소 요청 │
│ │ │
│ ▼ │
│ ┌────────────────────────┐ │
│ │ Index로 캐시 라인 선택 │ │
│ └────────────┬───────────┘ │
│ │ │
│ ▼ │
│ ┌────────────────────────┐ │
│ │ Tag 비교 & Valid 확인 │ │
│ └────────────┬───────────┘ │
│ │ │
│ ┌────────────┴────────────┐ │
│ │ │ │
│ Tag 일치 & Tag 불일치 or │
│ Valid = 1 Valid = 0 │
│ │ │ │
│ ▼ ▼ │
│ ┌─────────────────┐ ┌─────────────────────┐ │
│ │ Cache Hit! │ │ Cache Miss! │ │
│ │ Offset로 데이터 │ │ 메모리에서 블록 로드 │ │
│ │ 선택/반환 │ │ 캐시에 저장 후 반환 │ │
│ └─────────────────┘ └─────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
2. 캐시 사상 방식¶
2.1 직접 사상 (Direct Mapped)¶
특징: 각 메모리 블록은 캐시의 한 위치에만 저장 가능
계산:
Cache Index = (Memory Block Address) mod (Number of Cache Lines)
예시: 8라인 캐시
메모리 블록 캐시 인덱스
0 → 0
1 → 1
2 → 2
...
7 → 7
8 → 0 (충돌!)
9 → 1
...
16 → 0 (충돌!)
┌─────────────────────────────────────────────────────────────┐
│ 직접 사상 캐시 │
├─────────────────────────────────────────────────────────────┤
│ Index │ Valid │ Tag │ Data (64B) │
├────────┼───────┼───────────┼───────────────────────────────┤
│ 0 │ 1 │ 0x100 │ [block 0 또는 8 또는 16...] │
│ 1 │ 1 │ 0x101 │ [block 1 또는 9 또는 17...] │
│ 2 │ 0 │ - │ - │
│ 3 │ 1 │ 0x102 │ [block 3 또는 11...] │
│ 4 │ 1 │ 0x103 │ [...] │
│ 5 │ 0 │ - │ - │
│ 6 │ 1 │ 0x100 │ [...] │
│ 7 │ 1 │ 0x101 │ [...] │
└────────┴───────┴───────────┴───────────────────────────────┘
장점:
- 간단한 하드웨어
- 빠른 접근 (병렬 Tag 비교 불필요)
- 결정적 교체 (교체 정책 불필요)
단점:
- 충돌 미스 많음
- 같은 인덱스를 사용하는 블록들이 경쟁
2.2 완전 연관 사상 (Fully Associative)¶
특징: 메모리 블록은 캐시의 어떤 위치에든 저장 가능
┌─────────────────────────────────────────────────────────────┐
│ 완전 연관 사상 캐시 │
├─────────────────────────────────────────────────────────────┤
│ Entry │ Valid │ Tag │ Data (64B) │
├────────┼───────┼──────────────┼────────────────────────────┤
│ 0 │ 1 │ 0x0001000 │ [any block] │
│ 1 │ 1 │ 0x0002008 │ [any block] │
│ 2 │ 1 │ 0x0001008 │ [any block] │
│ 3 │ 1 │ 0x0003010 │ [any block] │
│ 4 │ 0 │ - │ - │
│ 5 │ 1 │ 0x0002000 │ [any block] │
│ 6 │ 1 │ 0x0004020 │ [any block] │
│ 7 │ 1 │ 0x0001020 │ [any block] │
└────────┴───────┴──────────────┴────────────────────────────┘
검색 과정:
┌─────────────────────────────────────────────────────────────┐
│ 요청 주소의 Tag를 모든 엔트리의 Tag와 동시 비교 (병렬 비교) │
│ │
│ Request Tag: 0x0001008 │
│ │
│ Entry 0: 0x0001000 ≠ 0x0001008 → Miss │
│ Entry 1: 0x0002008 ≠ 0x0001008 → Miss │
│ Entry 2: 0x0001008 = 0x0001008 → Hit! ← │
│ Entry 3: 0x0003010 ≠ 0x0001008 → Miss │
│ ... │
└─────────────────────────────────────────────────────────────┘
장점:
- 충돌 미스 없음
- 최대 유연성
단점:
- 복잡한 하드웨어 (모든 태그 병렬 비교 필요)
- 느린 접근 (CAM - Content Addressable Memory 필요)
- 비싼 구현 비용
- 실제로는 TLB 같은 작은 구조에만 사용
2.3 집합 연관 사상 (Set Associative)¶
특징: 직접 사상과 완전 연관의 절충
- 캐시를 여러 집합(Set)으로 나눔
- 각 집합 내에서는 완전 연관
N-way Set Associative:
- 각 집합에 N개의 캐시 라인 (Way)
- 메모리 블록은 하나의 집합에만 배치 가능
- 집합 내에서는 어떤 Way에든 배치 가능
예시: 4-way Set Associative (32라인, 8집합)
┌─────────────────────────────────────────────────────────────┐
│ 4-way Set Associative 캐시 │
├─────────────────────────────────────────────────────────────┤
│ │ Way 0 │ Way 1 │ Way 2 │ Way 3 │
│ Set │ V│Tag│Data│ V│Tag│Data│ V│Tag│Data│ V│Tag│Data │
├────────┼───────────┼───────────┼───────────┼──────────────┤
│ 0 │ 1│100│... │ 1│108│... │ 0│ - │ - │ 1│110│... │
│ 1 │ 1│101│... │ 1│109│... │ 1│111│... │ 0│ - │ - │
│ 2 │ 1│102│... │ 0│ - │ - │ 1│10A│... │ 1│112│... │
│ 3 │ 1│103│... │ 1│10B│... │ 1│113│... │ 1│11B│... │
│ 4 │ 0│ - │ - │ 1│10C│... │ 0│ - │ - │ 1│114│... │
│ 5 │ 1│105│... │ 1│10D│... │ 1│115│... │ 0│ - │ - │
│ 6 │ 1│106│... │ 0│ - │ - │ 1│10E│... │ 1│116│... │
│ 7 │ 1│107│... │ 1│10F│... │ 1│117│... │ 1│11F│... │
└────────┴───────────┴───────────┴───────────┴──────────────┘
주소 분해 (32비트, 4-way, 8집합, 64B 라인):
┌─────────────────────────────────────────────────────────────┐
│ 31 9 8 6 5 0 │
│ ├───────────────────────┼───────────┼──────────────────┤ │
│ │ Tag (23비트) │Set Index │ Block Offset │ │
│ │ │ (3비트) │ (6비트) │ │
│ └───────────────────────┴───────────┴──────────────────┘ │
└─────────────────────────────────────────────────────────────┘
2.4 사상 방식 비교¶
┌─────────────────┬─────────────┬──────────────┬──────────────┐
│ 특성 │ 직접 사상 │ 집합 연관 │ 완전 연관 │
├─────────────────┼─────────────┼──────────────┼──────────────┤
│ 유연성 │ 낮음 │ 중간 │ 높음 │
├─────────────────┼─────────────┼──────────────┼──────────────┤
│ 하드웨어 복잡도 │ 낮음 │ 중간 │ 높음 │
├─────────────────┼─────────────┼──────────────┼──────────────┤
│ 접근 속도 │ 빠름 │ 중간 │ 느림 │
├─────────────────┼─────────────┼──────────────┼──────────────┤
│ 충돌 미스 │ 많음 │ 적음 │ 없음 │
├─────────────────┼─────────────┼──────────────┼──────────────┤
│ 비교기 수 │ 1개 │ N개(N-way) │ 전체 라인 │
├─────────────────┼─────────────┼──────────────┼──────────────┤
│ 실제 사용 │ 초기 캐시 │ 대부분 캐시 │ TLB │
└─────────────────┴─────────────┴──────────────┴──────────────┘
일반적인 구성 (현대 프로세서):
- L1 캐시: 8-way set associative
- L2 캐시: 4-8 way set associative
- L3 캐시: 16-way set associative
- TLB: 완전 연관 또는 높은 연관도
3. 캐시 교체 정책¶
3.1 교체 정책의 필요성¶
집합 연관 또는 완전 연관 캐시에서:
- 캐시 미스 시 새 블록을 로드해야 함
- 집합(또는 전체 캐시)이 가득 찬 경우
- 어떤 블록을 교체할지 결정 필요
목표: 미래에 사용되지 않을 블록 교체 → 미스율 최소화
문제: 미래를 예측할 수 없음 → 휴리스틱 사용
3.2 LRU (Least Recently Used)¶
원리: 가장 오래 전에 사용된 블록 교체
근거: 최근에 사용된 블록은 곧 다시 사용될 가능성 높음 (시간적 지역성)
예시: 4-way 캐시, 접근 순서 A, B, C, D, E, A, B, F
초기 상태 (빈 캐시):
┌────┬────┬────┬────┐
│ - │ - │ - │ - │ LRU 순서: -
└────┴────┴────┴────┘
접근 A (Miss):
┌────┬────┬────┬────┐
│ A │ - │ - │ - │ LRU 순서: A
└────┴────┴────┴────┘
접근 B (Miss):
┌────┬────┬────┬────┐
│ A │ B │ - │ - │ LRU 순서: A, B
└────┴────┴────┴────┘
접근 C (Miss):
┌────┬────┬────┬────┐
│ A │ B │ C │ - │ LRU 순서: A, B, C
└────┴────┴────┴────┘
접근 D (Miss):
┌────┬────┬────┬────┐
│ A │ B │ C │ D │ LRU 순서: A, B, C, D
└────┴────┴────┴────┘
접근 E (Miss, A 교체 - 가장 오래됨):
┌────┬────┬────┬────┐
│ E │ B │ C │ D │ LRU 순서: B, C, D, E
└────┴────┴────┴────┘
접근 A (Miss, B 교체):
┌────┬────┬────┬────┐
│ E │ A │ C │ D │ LRU 순서: C, D, E, A
└────┴────┴────┴────┘
접근 B (Miss, C 교체):
┌────┬────┬────┬────┐
│ E │ A │ B │ D │ LRU 순서: D, E, A, B
└────┴────┴────┴────┘
LRU 구현:
- 정확한 LRU: N! 상태 필요 → 하드웨어 비용 높음
- 근사 LRU: 비트 행렬, 트리 기반 등으로 근사
3.3 Pseudo-LRU (Tree-based)¶
트리 기반 근사 LRU (4-way 예시):
┌───┐
│ 0 │ ← 루트: 0이면 왼쪽, 1이면 오른쪽이 더 최근
└─┬─┘
┌───┴───┐
┌─┴─┐ ┌─┴─┐
│ 0 │ │ 1 │ ← 내부 노드
└─┬─┘ └─┬─┘
┌──┴──┐ ┌──┴──┐
│ │ │ │
Way0 Way1 Way2 Way3
교체할 Way 찾기:
1. 루트에서 시작
2. 비트가 0이면 왼쪽, 1이면 오른쪽으로 이동
3. 리프에 도달하면 해당 Way 교체
접근 시 비트 갱신:
- 접근한 Way로 가는 경로의 비트들을 반대 방향으로 설정
- 다음 교체 시 해당 Way를 피하도록 유도
장점: log2(N) 비트만 필요 (4-way: 3비트 vs 정확한 LRU: 더 많음)
단점: 정확한 LRU 순서를 보장하지 않음
3.4 FIFO (First In, First Out)¶
원리: 가장 먼저 들어온 블록 교체
예시: 4-way 캐시, 접근 순서 A, B, C, D, E, A
┌────┬────┬────┬────┐
│ - │ - │ - │ - │ Head=0
└────┴────┴────┴────┘
A (Miss) → B (Miss) → C (Miss) → D (Miss):
┌────┬────┬────┬────┐
│ A │ B │ C │ D │ Head=0 (A가 가장 먼저)
└────┴────┴────┴────┘
E (Miss, A 교체):
┌────┬────┬────┬────┐
│ E │ B │ C │ D │ Head=1 (B가 다음)
└────┴────┴────┴────┘
A (Miss, B 교체 - A를 최근에 접근했어도!):
┌────┬────┬────┬────┐
│ E │ A │ C │ D │ Head=2
└────┴────┴────┴────┘
장점:
- 매우 간단한 구현 (포인터 하나)
- 공정한 교체
단점:
- 접근 패턴 무시
- Belady's anomaly: 캐시 크기 증가 시 미스율 증가 가능
3.5 Random 교체¶
원리: 무작위로 블록 선택하여 교체
구현:
- 난수 생성기 사용
- 또는 간단한 카운터
┌────┬────┬────┬────┐
│ A │ B │ C │ D │
└────┴────┴────┴────┘
E 삽입, 무작위 선택 = Way 2:
┌────┬────┬────┬────┐
│ A │ B │ E │ D │ C 교체됨
└────┴────┴────┴────┘
장점:
- 매우 간단한 구현
- 병적인(pathological) 접근 패턴에 강함
- Belady's anomaly 없음
단점:
- 평균적으로 LRU보다 성능 낮음
- 최근 사용 블록도 교체될 수 있음
실제 사용:
- ARM 프로세서의 일부 캐시
- L2/L3 캐시에서 랜덤+LRU 혼합 사용
3.6 교체 정책 비교¶
미스율 비교 (일반적인 워크로드):
┌────────────────┬───────────────┬───────────────────────────┐
│ 정책 │ 상대 미스율 │ 특징 │
├────────────────┼───────────────┼───────────────────────────┤
│ Optimal (OPT) │ 1.00x │ 이론적 최적 (미래 예측) │
├────────────────┼───────────────┼───────────────────────────┤
│ LRU │ 1.05x │ 매우 좋음, 구현 복잡 │
├────────────────┼───────────────┼───────────────────────────┤
│ Pseudo-LRU │ 1.08x │ LRU 근사, 효율적 구현 │
├────────────────┼───────────────┼───────────────────────────┤
│ Random │ 1.15x │ 간단함, 합리적 성능 │
├────────────────┼───────────────┼───────────────────────────┤
│ FIFO │ 1.20x │ 가장 간단, 낮은 성능 │
└────────────────┴───────────────┴───────────────────────────┘
4. 캐시 쓰기 정책¶
4.1 Write-Through¶
원리: 쓰기 시 캐시와 메모리 모두 갱신
┌─────────────────────────────────────────────────────────────┐
│ Write-Through 동작 │
├─────────────────────────────────────────────────────────────┤
│ │
│ CPU │
│ │ │
│ │ Write X = 5 │
│ ▼ │
│ ┌─────────┐ │
│ │ Cache │ ───────────────────────┐ │
│ │ X = 5 │ │ X = 5 │
│ └─────────┘ ▼ │
│ ┌──────────┐ │
│ │ Memory │ │
│ │ X = 5 │ │
│ └──────────┘ │
│ │
│ 캐시와 메모리가 항상 일치 (Consistent) │
│ │
└─────────────────────────────────────────────────────────────┘
장점:
- 캐시와 메모리 항상 일치
- 캐시 교체 시 Write-back 불필요
- 단순한 구현
- 데이터 복구 용이 (정전 등)
단점:
- 매 쓰기마다 메모리 접근 → 느림
- 메모리 대역폭 소모
완화책: Write Buffer
┌──────────────────────────────────────────────┐
│ CPU → Cache → Write Buffer → Memory │
│ ↑ │
│ 버퍼가 다 찰 때까지 CPU 계속 진행 │
└──────────────────────────────────────────────┘
4.2 Write-Back¶
원리: 쓰기 시 캐시만 갱신, 메모리는 교체 시 갱신
┌─────────────────────────────────────────────────────────────┐
│ Write-Back 동작 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 1. 쓰기 발생 │
│ CPU │
│ │ │
│ │ Write X = 5 │
│ ▼ │
│ ┌─────────┐ │
│ │ Cache │ 메모리 접근 없음! │
│ │ X = 5 │◄── Dirty = 1 │
│ └─────────┘ │
│ │
│ 2. 캐시 교체 시 │
│ ┌─────────┐ │
│ │ Cache │ │
│ │ X = 5 │ ─── Dirty = 1 이면 메모리에 기록 ───┐ │
│ └─────────┘ ▼ │
│ ┌──────────┐ │
│ │ Memory │ │
│ │ X = 5 │ │
│ └──────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
Dirty Bit:
- 캐시 라인이 수정되었는지 표시
- 1: 수정됨 (메모리와 불일치)
- 0: 수정 안 됨 (메모리와 일치)
장점:
- 쓰기 성능 향상 (메모리 접근 감소)
- 같은 주소 반복 쓰기에 효율적
- 메모리 대역폭 절약
단점:
- 구현 복잡 (Dirty bit, 교체 시 write-back)
- 캐시-메모리 불일치 가능
- 교체 시 지연 발생
4.3 Write Allocate vs No-Write Allocate¶
쓰기 미스 시 처리 방식:
Write Allocate (Fetch on Write):
┌─────────────────────────────────────────────────────────────┐
│ 쓰기 미스 발생 │
│ ↓ │
│ 블록을 메모리에서 캐시로 로드 │
│ ↓ │
│ 캐시에서 쓰기 수행 │
│ │
│ 주로 Write-Back과 함께 사용 │
│ 공간적 지역성 활용: 인접 데이터도 캐시에 로드 │
└─────────────────────────────────────────────────────────────┘
No-Write Allocate (Write Around):
┌─────────────────────────────────────────────────────────────┐
│ 쓰기 미스 발생 │
│ ↓ │
│ 메모리에 직접 쓰기 (캐시 로드 안 함) │
│ │
│ 주로 Write-Through와 함께 사용 │
│ 한 번만 쓰고 안 읽는 데이터에 효율적 │
└─────────────────────────────────────────────────────────────┘
일반적인 조합:
┌──────────────────┬─────────────────┐
│ 쓰기 정책 │ 할당 정책 │
├──────────────────┼─────────────────┤
│ Write-Back │ Write Allocate │
│ Write-Through │ No-Write Alloc │
└──────────────────┴─────────────────┘
4.4 쓰기 정책 비교¶
┌─────────────────┬────────────────────┬────────────────────┐
│ 특성 │ Write-Through │ Write-Back │
├─────────────────┼────────────────────┼────────────────────┤
│ 쓰기 지연 │ 높음 (메모리) │ 낮음 (캐시) │
├─────────────────┼────────────────────┼────────────────────┤
│ 구현 복잡도 │ 낮음 │ 높음 │
├─────────────────┼────────────────────┼────────────────────┤
│ 메모리 트래픽 │ 높음 │ 낮음 │
├─────────────────┼────────────────────┼────────────────────┤
│ 데이터 일관성 │ 보장 │ 관리 필요 │
├─────────────────┼────────────────────┼────────────────────┤
│ 교체 시 오버헤드│ 없음 │ Dirty면 있음 │
├─────────────────┼────────────────────┼────────────────────┤
│ 실제 사용 │ L1 (일부), 임베디드│ L1, L2, L3 │
└─────────────────┴────────────────────┴────────────────────┘
5. 캐시 미스의 종류¶
5.1 3C 분류¶
캐시 미스의 세 가지 원인 (3C Model):
1. Cold Miss (Compulsory Miss) - 필수 미스
2. Capacity Miss - 용량 미스
3. Conflict Miss - 충돌 미스
5.2 Cold Miss (Compulsory Miss)¶
정의: 처음 접근하는 블록에 대한 미스
- 캐시가 비어있을 때 발생
- 캐시 크기와 무관하게 발생
- 피할 수 없음 (프리페치로 완화 가능)
┌─────────────────────────────────────────────────────────────┐
│ 프로그램 시작 시: │
│ │
│ 접근 1: A → Miss (A 첫 접근) │
│ 접근 2: B → Miss (B 첫 접근) │
│ 접근 3: A → Hit (이미 캐시에 있음) │
│ 접근 4: C → Miss (C 첫 접근) │
│ │
│ 처음 3번의 미스는 Cold Miss │
└─────────────────────────────────────────────────────────────┘
완화 방법:
- 프리페칭 (Prefetching)
- 더 큰 블록 크기 (공간적 지역성 활용)
5.3 Capacity Miss¶
정의: 캐시 용량 부족으로 인한 미스
- Working Set > 캐시 크기일 때 발생
- 이전에 있던 블록이 용량 부족으로 교체된 후 재접근
┌─────────────────────────────────────────────────────────────┐
│ 4-블록 캐시, 접근 순서: A, B, C, D, E, A │
│ │
│ 접근 A → Miss, 캐시: [A, -, -, -] │
│ 접근 B → Miss, 캐시: [A, B, -, -] │
│ 접근 C → Miss, 캐시: [A, B, C, -] │
│ 접근 D → Miss, 캐시: [A, B, C, D] ← 캐시 가득 참 │
│ 접근 E → Miss, 캐시: [E, B, C, D] ← A 교체됨 │
│ 접근 A → Miss! ← Capacity Miss │
│ 캐시: [E, A, C, D] (A가 용량 부족으로 밀림) │
│ │
└─────────────────────────────────────────────────────────────┘
완화 방법:
- 캐시 크기 증가
- 데이터 구조 최적화 (Working Set 감소)
- 루프 타일링 등 알고리즘 최적화
5.4 Conflict Miss¶
정의: 같은 캐시 위치를 경쟁하는 블록들로 인한 미스
- 직접 사상 또는 집합 연관 캐시에서 발생
- 캐시에 공간이 있어도 특정 위치 경쟁으로 미스
- 완전 연관 캐시에서는 발생하지 않음
┌─────────────────────────────────────────────────────────────┐
│ 2-way 캐시, 2 집합, 접근 순서: A, E, I (모두 Set 0에 매핑) │
│ │
│ 초기: Set 0: [-, -], Set 1: [-, -] │
│ │
│ 접근 A (Set 0) → Miss │
│ Set 0: [A, -], Set 1: [-, -] │
│ │
│ 접근 E (Set 0) → Miss │
│ Set 0: [A, E], Set 1: [-, -] ← Set 0 가득 참 │
│ │
│ 접근 I (Set 0) → Miss │
│ Set 0: [I, E], Set 1: [-, -] ← A 교체, Set 1은 비어있음!│
│ │
│ 접근 A (Set 0) → Miss! ← Conflict Miss │
│ Set 0: [I, A], Set 1: [-, -] (Set 1은 여전히 비어있음) │
│ │
│ 캐시의 50%가 비어있는데도 미스 발생 = Conflict Miss │
└─────────────────────────────────────────────────────────────┘
완화 방법:
- 연관도 증가 (N-way 증가)
- 스큐드 캐시 (Skewed Cache)
- 빅팀 캐시 (Victim Cache)
5.5 3C 미스 비율¶
일반적인 프로그램의 미스 비율:
┌─────────────────────────────────────────────────────────────┐
│ │
│ │ 100%│ ████████████████████████████████████████ │
│ │ │ █ Compulsory (Cold) █ │
│ │ │ █████████████████████████████ │
│ │ 50%│ █ Capacity █ │
│ │ │ █████████████████████████████████████████ │
│ │ │ █ Conflict █ │
│ │ 0%│ │
│ └─────┴───────────────────────────────────────── │
│ 작은 캐시 ────────────────▶ 큰 캐시 │
│ │
│ - 캐시 크기 증가: Capacity Miss 감소 │
│ - 연관도 증가: Conflict Miss 감소 │
│ - Cold Miss: 캐시 크기와 거의 무관 │
│ │
└─────────────────────────────────────────────────────────────┘
6. 다중 레벨 캐시¶
6.1 다중 레벨 캐시의 필요성¶
문제: L1 캐시 최적화의 딜레마
- 히트 시간 최적화 → 작은 캐시, 낮은 연관도
- 미스율 최적화 → 큰 캐시, 높은 연관도
해결: 다중 레벨 캐시
┌─────────────────────────────────────────────────────────────┐
│ │
│ CPU ← 빠른 접근 필요 │
│ │ │
│ ┌────┴────┐ │
│ │ L1 캐시 │ 작고 빠름 (히트 시간 최적화) │
│ │ 32KB │ 4 사이클 │
│ └────┬────┘ │
│ │ │
│ ┌────┴────┐ │
│ │ L2 캐시 │ 중간 (균형) │
│ │ 256KB │ 12 사이클 │
│ └────┬────┘ │
│ │ │
│ ┌────┴────┐ │
│ │ L3 캐시 │ 크고 공유 (미스율 최적화) │
│ │ 8-32MB │ 40 사이클 │
│ └────┬────┘ │
│ │ │
│ ┌────┴────┐ │
│ │ 메모리 │ 100+ 사이클 │
│ └─────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
6.2 Inclusive vs Exclusive 캐시¶
Inclusive Cache:
- 하위 레벨이 상위 레벨의 데이터를 포함
- L1의 모든 데이터가 L2에도 있음
- L2의 모든 데이터가 L3에도 있음
┌─────────────────────────────────────────────────────────────┐
│ L1: [A, B, C, D] │
│ L2: [A, B, C, D, E, F, G, H, ...] │
│ L3: [A, B, C, D, E, F, G, H, ..., X, Y, Z] │
│ │
│ 장점: │
│ - 캐시 일관성 유지 쉬움 │
│ - 스누핑 시 L3만 확인하면 됨 │
│ │
│ 단점: │
│ - 유효 용량 감소 (중복 저장) │
│ - L3 교체 시 L1/L2도 무효화 필요 │
└─────────────────────────────────────────────────────────────┘
Exclusive Cache:
- 각 레벨이 서로 다른 데이터 저장
- 한 블록은 한 레벨에만 존재
┌─────────────────────────────────────────────────────────────┐
│ L1: [A, B, C, D] │
│ L2: [E, F, G, H] (L1에 없는 데이터) │
│ L3: [I, J, K, L] (L1, L2에 없는 데이터) │
│ │
│ 장점: │
│ - 전체 유효 용량 = L1 + L2 + L3 │
│ │
│ 단점: │
│ - 캐시 간 데이터 이동 복잡 │
│ - L1 미스 시 L2, L3 순차 검색 필요 │
└─────────────────────────────────────────────────────────────┘
NINE (Non-Inclusive, Non-Exclusive):
- 일관성 보장 없이 자유롭게 배치
- 구현 복잡하지만 유연
6.3 전용 캐시 vs 공유 캐시¶
현대 멀티코어 프로세서 구조:
┌─────────────────────────────────────────────────────────────┐
│ │
│ Core 0 Core 1 Core 2 Core 3 │
│ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐│
│ │ L1-I │ │ L1-I │ │ L1-I │ │ L1-I ││
│ │ L1-D │ │ L1-D │ │ L1-D │ │ L1-D ││
│ └──┬───┘ └──┬───┘ └──┬───┘ └──┬───┘│
│ │ │ │ │ │
│ ┌──┴───┐ ┌──┴───┐ ┌──┴───┐ ┌──┴───┐│
│ │ L2 │ │ L2 │ │ L2 │ │ L2 ││
│ │(전용)│ │(전용)│ │(전용)│ │(전용)││
│ └──┬───┘ └──┬───┘ └──┬───┘ └──┬───┘│
│ │ │ │ │ │
│ └───────────────┴───────┬───────┴───────────────┘ │
│ │ │
│ ┌────────┴────────┐ │
│ │ L3 │ │
│ │ (공유) │ │
│ │ 8-32MB │ │
│ └────────┬────────┘ │
│ │ │
│ ┌────────┴────────┐ │
│ │ Main Memory │ │
│ └─────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
전용 캐시 (L1, L2):
- 각 코어 전용
- 접근 지연 최소화
- 코어 간 간섭 없음
공유 캐시 (L3):
- 모든 코어가 공유
- 코어 간 데이터 공유 효율적
- 동적 용량 할당 (바쁜 코어에 더 많은 공간)
- 일관성 유지 필요
6.4 Local vs Global 미스율¶
Local Miss Rate:
해당 레벨에서의 미스율
Global Miss Rate:
전체 접근 중 해당 레벨까지 도달하는 비율
예시:
- L1 미스율: 5%
- L2 미스율 (Local): 20%
- L3 미스율 (Local): 30%
Global 미스율 계산:
- L2 Global Miss Rate = L1 Miss Rate × L2 Local Miss Rate
= 0.05 × 0.20 = 1%
(전체 접근의 1%가 L3에 도달)
- L3 Global Miss Rate = L2 Global × L3 Local
= 0.01 × 0.30 = 0.3%
(전체 접근의 0.3%가 메모리에 도달)
┌─────────────────────────────────────────────────────────────┐
│ Local vs Global Miss Rate │
├─────────────────────────────────────────────────────────────┤
│ Level │ Local Miss Rate │ Global Miss Rate │
├─────────┼───────────────────┼─────────────────────────────-┤
│ L1 │ 5% │ 5% │
│ L2 │ 20% │ 1% (0.05 × 0.20) │
│ L3 │ 30% │ 0.3% (0.01 × 0.30) │
└─────────┴───────────────────┴──────────────────────────────┘
7. 캐시 최적화 기법¶
7.1 Victim Cache¶
목적: Conflict Miss 감소
구조:
┌─────────────────────────────────────────────────────────────┐
│ │
│ ┌─────────────────────────────────────┐ │
│ │ Main Cache (Direct Mapped) │ │
│ └──────────────────┬──────────────────┘ │
│ │ │
│ 교체된 블록 │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────┐ │
│ │ Victim Cache (Fully Associative) │ │
│ │ 4-8 entries │ │
│ └─────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
동작:
1. Main Cache 미스 발생
2. Victim Cache 검색
3. Victim Cache에 있으면 → 스왑하여 히트
4. 없으면 → 메모리에서 로드, 교체된 블록은 Victim Cache로
효과: 충돌 미스를 Victim Cache 크기만큼 흡수
7.2 프리페칭 (Prefetching)¶
하드웨어 프리페치:
- CPU가 접근 패턴 감지
- 다음에 필요할 블록을 미리 로드
소프트웨어 프리페치:
- 프로그래머/컴파일러가 프리페치 명령 삽입
┌─────────────────────────────────────────────────────────────┐
│ // 소프트웨어 프리페치 예시 │
│ for (int i = 0; i < N; i++) { │
│ __builtin_prefetch(&a[i + 16], 0, 3); // 16개 앞 프리페치│
│ sum += a[i]; │
│ } │
└─────────────────────────────────────────────────────────────┘
프리페치 효과:
┌─────────────────────────────────────────────────────────────┐
│ Without Prefetch: │
│ 요청 ─────┬───── 메모리 지연 ─────┬───── 처리 │
│ │
│ With Prefetch: │
│ 프리페치 ────┬───── 메모리 지연 ─────┬ │
│ │ │ │
│ 요청 ─────┼───── 데이터 도착! ────┼───── 처리 (빠름) │
│ │
│ 프리페치가 메모리 지연을 숨김 │
└─────────────────────────────────────────────────────────────┘
7.3 컴파일러 최적화¶
루프 교환 (Loop Interchange):
// Before: 열 우선 (나쁜 지역성)
for (j = 0; j < N; j++)
for (i = 0; i < N; i++)
a[i][j] = b[i][j] + c[i][j];
// After: 행 우선 (좋은 지역성)
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
a[i][j] = b[i][j] + c[i][j];
루프 융합 (Loop Fusion):
// Before: 두 개의 루프
for (i = 0; i < N; i++) a[i] = b[i] + 1;
for (i = 0; i < N; i++) c[i] = a[i] * 2;
// After: 하나의 루프 (a[i]가 캐시에 있을 때 바로 사용)
for (i = 0; i < N; i++) {
a[i] = b[i] + 1;
c[i] = a[i] * 2;
}
루프 타일링 (Loop Tiling):
// Before
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];
// After (블록 단위 처리로 캐시 재사용)
for (ii = 0; ii < N; ii += BLOCK)
for (jj = 0; jj < N; jj += BLOCK)
for (kk = 0; kk < N; kk += BLOCK)
for (i = ii; i < ii+BLOCK; i++)
for (j = jj; j < jj+BLOCK; j++)
for (k = kk; k < kk+BLOCK; k++)
C[i][j] += A[i][k] * B[k][j];
8. 연습 문제¶
기초 문제¶
-
32KB 직접 사상 캐시, 64바이트 블록일 때 캐시 라인 수는?
-
4-way 집합 연관 캐시에서 특정 메모리 블록이 저장될 수 있는 위치는 몇 개인가?
-
Write-Through와 Write-Back의 차이를 설명하시오.
중급 문제¶
- 다음 주소에서 Tag, Index, Offset을 구하시오:
- 주소: 0x12345678
-
캐시: 16KB, 2-way 집합 연관, 64바이트 라인
-
다음 접근 패턴에서 캐시 미스의 종류를 분류하시오: (4-라인 직접 사상 캐시, 블록 A~D는 같은 인덱스에 매핑)
A, B, C, D, A, E, A -
L1 캐시: 히트시간 2사이클, 미스율 10% L2 캐시: 히트시간 10사이클, 미스율 5% 메모리: 접근시간 100사이클 AMAT를 구하시오.
심화 문제¶
-
다음 코드의 캐시 성능을 분석하시오 (64바이트 캐시 라인, 4바이트 int):
c int a[1024], b[1024], c[1024]; for (int i = 0; i < 1024; i++) c[i] = a[i] + b[i]; -
8-way 집합 연관 캐시에서 LRU 정책을 정확히 구현하려면 각 집합당 몇 비트가 필요한가?
-
Victim Cache가 Conflict Miss를 줄이는 원리를 설명하시오.
정답
1. 캐시 라인 수 = 32KB / 64B = 512 라인 2. 4개 (4-way = 각 집합에 4개 위치) 3. Write-Through: 캐시와 메모리 동시 갱신, 일관성 보장 Write-Back: 캐시만 갱신, 교체 시 메모리 갱신, 성능 우수 4. 주소 분해: - 16KB, 2-way → 128 집합 (16KB / 64B / 2 = 128) - Offset: 6비트 (64B = 2^6) - Index: 7비트 (128 = 2^7) - Tag: 32 - 6 - 7 = 19비트 0x12345678 = 0001 0010 0011 0100 0101 0110 0111 1000 - Offset: 111000 (0x38) - Index: 1011001 (0x59) - Tag: 0001 0010 0011 0100 0101 (0x12345) 5. 미스 분류: - A: Cold Miss (첫 접근) - B: Cold Miss - C: Cold Miss - D: Cold Miss - A: Conflict Miss (D에 의해 교체됨) - E: Conflict Miss + Cold Miss - A: Conflict Miss (E에 의해 교체됨) 6. AMAT = 2 + 0.10 × (10 + 0.05 × 100) = 2 + 0.10 × 15 = 2 + 1.5 = 3.5 사이클 7. 캐시 분석: - 64바이트 라인 = 16개 int - 각 배열 1024개 int = 64 캐시 라인 - 순차 접근 → 16번 접근당 1번 미스 - Cold Miss: 64 × 3 = 192번 (a, b, c 각각) - 히트: (1024 - 64) × 3 = 2880번 - 히트율: 2880 / 3072 = 93.75% 8. 정확한 LRU 구현: - 8개 Way의 순서 표현: 8! = 40320 상태 - 필요 비트: log2(40320) ≈ 16비트 (실제로는 근사 LRU 사용) 9. Victim Cache 원리: - Main Cache에서 교체된 블록을 Victim Cache에 보관 - Conflict로 교체된 블록이 다시 필요할 때 Victim Cache에서 빠르게 찾음 - 작은 완전 연관 캐시로 충돌 미스 흡수다음 단계¶
- 16_Virtual_Memory.md - 가상 주소 공간, 페이지 테이블, TLB
참고 자료¶
- Computer Architecture: A Quantitative Approach (Hennessy & Patterson)
- Cache Memory Visualization
- Intel Optimization Manual - Cache
- What Every Programmer Should Know About Memory (Ulrich Drepper)