270. 캐시 미스의 원인 (3C: Compulsory, Capacity, Conflict)

핵심 인사이트 (3줄 요약)

본질: 3C (Compulsory, Capacity, Conflict)는 캐시 미스 (Cache Miss)를 "처음이라서", "작아서", "겹쳐서"라는 세 가지 구조적 원인으로 분해하는 분석 틀이다.

가치: 같은 미스율이라도 원인이 다르면 해법도 달라서, 프리페치 (Prefetch), 캐시 용량 증설, 연관도 (Associativity) 조정 중 무엇이 맞는지 3C로 판단해야 한다.

판단 포인트: 실무에서는 평균 메모리 접근 시간(AMAT, Average Memory Access Time)만 보지 말고 어떤 미스가 지배적인지 먼저 구분해야 비용 대비 효과가 맞는다.

Ⅰ. 개요 및 필요성

3C (Compulsory, Capacity, Conflict)는 캐시 미스를 발생 원인 기준으로 나누는 대표 모델이다. 캐시는 빠른 메모리라고 해도 모든 데이터를 항상 담아둘 수 없기 때문에, 미스 자체를 0으로 만들기는 어렵다. 중요한 것은 미스가 "필연적인 첫 접근"인지, "캐시가 작아서 밀려난 것"인지, 아니면 "매핑 규칙 때문에 같은 자리에서 충돌한 것"인지 구분하는 일이다.

이 구분이 필요한 이유는 증상이 같아 보여도 처방이 완전히 다르기 때문이다. 예를 들어 처음 읽는 데이터 때문에 생긴 미스를 캐시 크기만 키워 해결하려 하면 비용만 늘고 효과는 제한적이다. 반대로 충돌 미스를 프리페치로 덮으려 하면 메모리 대역폭만 더 쓰고 근본 원인은 남는다.

즉 3C는 캐시 성능을 설명하는 이론이면서 동시에 설계와 튜닝의 진단표다. 하드웨어 설계자에게는 어떤 캐시 구조를 선택할지의 기준이 되고, 소프트웨어 개발자에게는 데이터 배치와 접근 순서를 어떻게 바꿔야 할지의 출발점이 된다.

📢 섹션 요약 비유: 가게 매출이 떨어졌다고 해도 원인이 손님이 처음 와서 길을 모르는 것인지, 매장이 좁은 것인지, 계산대 줄이 한쪽에만 몰린 것인지 알아야 해결책이 달라지는 것과 같다.

Ⅱ. 아키텍처 및 핵심 원리

3C를 이해하려면 캐시가 주소를 블록 단위로 저장하고, 제한된 공간 안에서 반복 접근을 최대한 흡수하려는 장치라는 점을 먼저 봐야 한다. 캐시 라인 (Cache Line) 하나는 보통 64바이트(Byte) 단위로 움직이고, 주소는 태그 (Tag)·인덱스 (Index)·오프셋 (Offset)으로 나뉘어 특정 세트(Set)와 위치를 정한다. 이 구조 위에서 3C는 아래처럼 발생한다.

미스 유형	발생 조건	구조적 원인	대표 해법
Compulsory Miss	데이터 첫 접근	캐시에 아직 한 번도 적재된 적이 없음	프리페치, 블록 크기 조정
Capacity Miss	다시 쓸 데이터가 이미 축출됨	워킹 셋(Working Set)이 캐시보다 큼	캐시 확대, 타일링, 데이터 분할
Conflict Miss	빈 공간 여지가 있어도 계속 미스	같은 세트로 주소가 몰림	세트 연관 증가, 배치/정렬 변경

아래 그림은 같은 메모리 접근이라도 왜 원인이 다르게 갈리는지를 보여준다.

┌──────────────────────────────────────────────────────────────────────┐
│                 3C가 발생하는 위치와 이유                           │
├──────────────────────────────────────────────────────────────────────┤
│  메모리 접근 흐름                                                   │
│  CPU (Central Processing Unit)                                      │
│    │                                                                │
│    ├─▶ [처음 보는 블록] ───────────────▶ Compulsory Miss            │
│    │        │                                                       │
│    │        └─ 아직 캐시에 흔적이 없음                              │
│    │                                                                │
│    ├─▶ [워킹 셋 > 캐시 크기] ────────▶ Capacity Miss                │
│    │        │                                                       │
│    │        └─ 필요한 블록이 용량 한계로 이미 축출됨                │
│    │                                                                │
│    └─▶ [같은 인덱스에 주소 집중] ────▶ Conflict Miss                │
│             │                                                       │
│             └─ 다른 세트는 비어도 특정 세트 안에서만 계속 교체      │
└──────────────────────────────────────────────────────────────────────┘

Compulsory Miss는 처음 읽는 순간에는 피할 수 없는 미스다. 프로그램 시작 직후, 큰 배열을 처음 순회할 때, 혹은 함수가 처음 호출되어 관련 코드와 데이터가 처음 캐시에 올라올 때 나타난다. 이 경우 핵심은 "처음 읽는 비용을 어떻게 숨길 것인가"이며, 하드웨어 프리페처나 소프트웨어 프리페치가 주된 대응책이다.

Capacity Miss는 시간적 지역성 (Temporal Locality)이 있어도 캐시가 그 지역성을 끝까지 유지할 만큼 크지 못할 때 생긴다. 예를 들어 32킬로바이트(KB) L1 (Level 1) 캐시에 128KB짜리 반복 데이터가 계속 들어오면, 조금 전까지 쓰던 블록도 다시 필요해지기 전에 쫓겨난다. 이때는 캐시 용량을 키우거나, 루프 타일링 (Loop Tiling)처럼 처리 범위를 잘게 쪼개 워킹 셋을 캐시 안으로 집어넣는 방식이 맞다.

Conflict Miss는 총 용량만 보면 충분해 보여도 주소 매핑 규칙 때문에 특정 세트에 요청이 몰릴 때 발생한다. 직접 사상 (Direct Mapping)이나 낮은 연관도 캐시에서 특히 두드러지며, 배열 두 개가 우연히 같은 인덱스 비트를 공유하면 다른 세트가 놀고 있어도 서로를 반복적으로 밀어낸다. 그래서 충돌 미스는 "용량 부족"이 아니라 "배치 규칙의 비효율"이라는 점이 중요하다.

📢 섹션 요약 비유: 처음 오는 손님은 안내가 필요하고, 창고가 작으면 물건을 못 쌓고, 진열대 번호가 나쁘면 한 칸 앞에서만 서로 부딪히는 것처럼 3C는 모두 다른 병목이다.

Ⅲ. 비교 및 연결

3C의 실전적 힘은 세 미스를 서로 비교할 때 더 분명해진다. Compulsory Miss는 "언젠가 한 번은 반드시 치르는 입장료"에 가깝다. 반면 Capacity Miss와 Conflict Miss는 설계와 코드 구조를 바꾸면 꽤 줄일 수 있는 미스다. 따라서 미스 분석에서 먼저 해야 할 일은 피할 수 없는 것과 줄일 수 있는 것을 분리하는 것이다.

비교 축	Compulsory Miss	Capacity Miss	Conflict Miss
재발 가능성	같은 블록 첫 접근 때만 큼	워킹 셋이 크면 반복 발생	특정 주소 패턴이면 반복 발생
캐시 크기 증가 효과	제한적	큼	경우에 따라 미미
연관도 증가 효과	거의 없음	보조적	매우 큼
소프트웨어 최적화	프리페치, 순차 접근	블로킹, 분할, 데이터 축소	정렬, 패딩, 주소 분산

특히 Capacity Miss와 Conflict Miss는 겉으로 보면 둘 다 "재사용하려 했는데 캐시에 없다"는 점에서 헷갈리기 쉽다. 하지만 Capacity Miss는 완전 연관 (Fully Associative) 가정으로 바꿔도 남는 미스이고, Conflict Miss는 완전 연관이라면 사라질 미스다. 이 차이는 캐시 설계에서 매우 크다. 전자는 용량과 계층 구조가 핵심이고, 후자는 세트 연관 사상(Set Associative Mapping)과 데이터 배치가 핵심이기 때문이다.

멀티코어 환경으로 가면 여기에 일관성 미스(Coherence Miss)까지 붙어 4C로 확장해 설명하기도 한다. 그러나 3C를 먼저 정확히 이해해야 그 위에 캐시 일관성(Cache Coherence) 문제를 얹을 수 있다. 즉 3C는 단일 코어 캐시 분석의 바닥 개념이고, 이후 평균 메모리 접근 시간, 프리페치 정책, 교체 정책(Replacement Policy) 같은 주제와 자연스럽게 연결된다.

📢 섹션 요약 비유: 3C는 결석 사유서를 분류하는 일과 비슷하다. 처음이라 길을 못 찾은 건 Compulsory, 교실이 너무 좁아 못 들어간 건 Capacity, 반은 비었는데 출입문 하나에만 몰린 건 Conflict다.

Ⅳ. 실무 적용 및 기술사 판단

실무에서는 미스율 숫자 하나만 보고 결론 내리면 자주 실패한다. 예를 들어 행렬 곱셈(Matrix Multiplication)처럼 대용량 배열을 다루는 코드는 Capacity Miss가 지배적일 가능성이 높고, 해시 테이블이나 고정 간격 스트라이드(Stride) 접근은 Conflict Miss를 강하게 만들 수 있다. 따라서 프로파일링 도구로 현상을 본 뒤, 3C 관점으로 재해석해야 한다.

판단 체크리스트

첫 순회 이후에도 미스가 계속 높은가? 그렇다면 Compulsory보다 Capacity 또는 Conflict 비중이 크다.
캐시를 키웠을 때 미스가 유의미하게 줄어드는가? 줄어든다면 Capacity 가능성이 높다.
연관도 증가나 데이터 정렬 변경에 민감한가? 그렇다면 Conflict 가능성이 높다.
프리페치가 효과가 있는가? 순차 접근 기반 Compulsory 완화에는 유효하지만, 충돌 구조 자체는 잘 못 고친다.

대표 시나리오

Capacity Miss 중심 사례: 64KB L1 데이터 캐시에 512KB 타일을 반복 투입하는 영상 처리 루프는 이전에 사용한 픽셀 블록이 다시 쓰이기 전에 계속 밀려난다. 이 경우 타일 크기를 32KB~48KB 수준으로 줄이면 캐시 재사용 구간이 살아나며 평균 메모리 접근 시간이 크게 내려간다.
Conflict Miss 중심 사례: 두 개의 큰 배열을 4KB 간격으로 교차 접근하는 코드는 특정 인덱스 비트가 겹치며 같은 세트에 몰릴 수 있다. 구조체 패딩, 배열 시작 주소 이동, alignas 같은 정렬 제어로 세트 분산을 유도하면 미스가 급감한다.
Compulsory Miss 중심 사례: 스트리밍 데이터 처리에서 한 번 읽고 거의 다시 보지 않는 로그 블록은 첫 접근 미스가 대부분이다. 이때는 캐시 확대보다 프리페치와 비차단 캐시(Non-blocking Cache) 같은 지연 은닉 전략이 더 맞다.

안티패턴

캐시 미스가 높다고 무조건 상위 등급 중앙 처리 장치(CPU, Central Processing Unit)로 교체하는 판단
충돌 문제를 데이터 구조 개선 없이 하드웨어 용량만으로 덮으려는 시도
워킹 셋 분석 없이 루프 타일 크기를 감으로 정하는 튜닝

기술사 답안이나 설계 면접에서는 "어떤 미스가 지배적이며 왜 그 해법을 선택하는가"를 말해야 한다. 단순히 캐시를 크게 하면 좋아진다는 식의 답변은 3C 모델을 모른다는 뜻에 가깝다.

📢 섹션 요약 비유: 같은 교통 체증이라도 초행길 때문인지, 도로가 좁아서인지, 신호 체계가 한쪽 차선만 막아서인지 구분해야 내비게이션·도로 확장·신호 조정을 각각 맞게 고를 수 있다.

Ⅴ. 기대효과 및 결론

3C 관점으로 캐시를 보면 미스가 단순한 불운이 아니라 구조적 현상으로 보인다. 그 결과 설계자는 블록 크기, 연관도, 캐시 계층 크기를 더 합리적으로 정할 수 있고, 개발자는 데이터 구조와 접근 패턴을 바꿔 실제 성능을 끌어올릴 수 있다. 즉 3C는 하드웨어와 소프트웨어가 같은 언어로 메모리 병목을 논의하게 해 준다.

물론 3C가 모든 것을 설명하는 것은 아니다. 멀티코어에서는 일관성 트래픽, 실제 시스템에서는 번역 색인 버퍼(TLB, Translation Lookaside Buffer) 미스와 페이지 폴트(Page Fault), 메모리 대역폭 포화까지 함께 본다. 그럼에도 3C는 "캐시 미스의 1차 진단"으로서 가장 강력한 출발점이며, 다른 병목을 논하기 전 반드시 통과해야 하는 기본 렌즈다.

결론적으로 3C는 캐시를 외우는 개념이 아니라 캐시를 읽어내는 관점이다. 처음이라 어쩔 수 없는 미스, 공간이 부족해 생긴 미스, 규칙이 나빠 생긴 미스를 구분할 수 있어야 진짜 최적화가 시작된다.

📢 섹션 요약 비유: 좋은 의사는 열이 난다는 결과만 보지 않고 감기인지 과로인지 염증인지부터 가려낸다. 3C는 캐시 성능을 진단하는 그 첫 분류표다.

📌 관련 개념 맵

개념	연결 포인트
캐시 히트/미스 (Cache Hit/Miss)	3C는 미스가 왜 났는지 원인을 분해하는 기준이다.
세트 연관 사상 (Set Associative Mapping)	Conflict Miss를 줄이기 위한 대표 구조다.
평균 메모리 접근 시간 (AMAT, Average Memory Access Time)	3C로 분해된 미스가 최종 접근 지연에 어떻게 반영되는지 보여준다.
프리페치 (Prefetch)	Compulsory Miss 완화에 특히 효과적이다.
루프 타일링 (Loop Tiling)	워킹 셋을 줄여 Capacity Miss를 완화하는 전형적 기법이다.

📈 관련 키워드 및 발전 흐름도

지역성 (Locality) 이해
    │
    ▼
캐시 히트/미스 (Cache Hit/Miss)
    │
    ▼
3C (Compulsory, Capacity, Conflict)
    │
    ├─▶ 프리페치 (Prefetch)          ─▶ Compulsory Miss 완화
    ├─▶ 캐시 용량·타일링             ─▶ Capacity Miss 완화
    └─▶ 세트 연관·데이터 재배치      ─▶ Conflict Miss 완화
    │
    ▼
AMAT (Average Memory Access Time) 최적화
    │
    ▼
멀티코어 확장: 4C · Coherence Miss

이 흐름은 "지역성 이해 → 원인 분해 → 원인별 대응 → 시스템 전체 최적화"로 이어지는 학습 경로를 보여준다.

👶 어린이를 위한 3줄 비유 설명

장난감을 찾을 때 처음 꺼내는 장난감은 당연히 서랍에 없어서 한 번은 찾으러 가야 해요.
서랍이 너무 작으면 아까 넣어 둔 장난감도 금방 밖으로 밀려나서 또 찾으러 가야 해요.
서랍은 넓은데도 같은 칸에만 장난감이 몰리면 서로 자리 싸움을 해서 못 찾게 되는데, 그게 바로 3C예요.