에듀테크 프로젝트 대시보드
캐시 메모리 매핑 (Cache Mapping)
CPU 캐시는 메인 메모리보다 수십~수백 배 빠르지만 훨씬 작다. 그래서 "메모리의 이 블록을 캐시의 어느 칸에 넣을까?"를 정하는 규칙이 필요하다. 이 규칙이 직접 사상 · 집합 연관 · 완전 연관이고, 잘못 고르면 충돌 미스(conflict miss)로 캐시가 있으나 마나가 된다.
캐시는 바이트 하나가 아니라 연속된 블록(=라인, 보통 32~64B) 단위로 메모리를 복사해 온다. 배열을 순서대로 훑을 때 빠른 이유가 이것 — 한 번 미스가 나면 옆 데이터까지 통째로 딸려 온다(공간 지역성).
메모리 주소를 캐시 관점에서 세 조각으로 자른다:
2^bB면 아래 b비트.2^s개면 그다음 s비트.| 방식 | 블록이 갈 수 있는 자리 | 장점 | 단점 |
|---|---|---|---|
| 직접 사상 Direct-Mapped |
딱 한 곳. 세트 = 블록번호 mod 세트수 |
비교기 1개, 가장 빠르고 싸다 | 같은 세트로 몰리면 서로 계속 쫓아냄 → 충돌 미스 폭발 |
| 집합 연관 N-way Set Associative |
한 세트 안의 N칸 중 아무 데나 | 충돌을 N배까지 흡수, 현실 CPU의 기본값(4~16-way) | N개 태그 동시 비교, 교체 정책(LRU 등) 필요 |
| 완전 연관 Fully Associative |
캐시 어디든 (세트 1개) | 충돌 미스 0, 자리 낭비 없음 | 모든 라인의 태그를 병렬 비교 → 하드웨어 비싸 TLB처럼 작은 캐시에만 |
총 8줄짜리 캐시에 접근 순서(주소열)를 흘려 보낸다. 아래에서 연관도를 바꿔 가며 같은 주소열이 어떻게 히트율이 달라지는지 보자. 교체 정책은 LRU(가장 오래 안 쓴 것 축출).
2차원 배열을 열 방향으로 훑거나, 구조체 배열을 큰 간격으로 건너뛰면 접근 주소들의 인덱스 비트가 똑같아져 한 세트로 몰린다. 캐시가 8MB라도 실제로는 한 세트(수 KB)만 쓰는 꼴 — 배열 폭에 +1 패딩을 주는 고전 최적화가 이걸 깬다.
// 느림: 열 우선 순회 — 매 접근이 4096바이트 점프 = 같은 세트 for (j=0; j<N; j++) for (i=0; i<N; i++) sum += a[i][j]; // 빠름: 행 우선 — 한 블록 안 데이터를 알뜰히 소비 for (i=0; i<N; i++) for (j=0; j<N; j++) sum += a[i][j];