Cache Coherence & MESI

1. Overview

캐시 일관성과 MESI 프로토콜(Cache Coherence & MESI, CCM)은 멀티코어 환경에서 각 코어(Core)가 개인 캐시(L1/L2)에 데이터를 보관하고 수정하면서 발생할 수 있는 데이터 불일치(Incoherence)를 하드웨어 레벨에서 맞추는 통신 규약입니다.

학습자는 스누핑(Snooping) 기술을 통해 버스(Bus) 위로 지나가는 다른 코어의 메모리 읽기/쓰기 시도를 관찰하고 내 캐시 라인을 무효화(Invalidate)하는 일관성 프로토콜의 구조를 살펴봅니다. 나아가 M(수정), E(독점), S(공유), I(무효)라는 4가지 상태 머신(FSM)을 통해 메모리 대역폭 낭비를 줄이고 데이터의 유일한 진실(Single Source of Truth)을 보장하는 MESI 프로토콜의 상태 전이 역학을 분석하여, 멀티스레드 소프트웨어가 왜 캐시 라인 단위에서 병목을 일으키는지 하드웨어적 기원을 이해합니다.

2. Scope & Boundaries

In-Scope

• 일관성 불일치 모델링 (Incoherence Problem): 멀티코어 캐시 불일치, Write-Back 캐시의 무결성 불일치 시나리오.
• 스누핑 역학 (Snooping Mechanics): 공유 버스(Shared Bus), 브로드캐스트(Broadcast), 무효화(Invalidation) 기반 일관성 vs 업데이트(Update) 기반 일관성.
• MESI 상태 기계 (MESI FSM): Modified(M), Exclusive(E), Shared(S), Invalid(I)의 각 상태 정의 및 읽기/쓰기에 따른 하드웨어 핀(Pin) 상태 전이도.
• 디렉토리 기반 일관성 (Directory-based Protocol): 수백 개의 코어에서 버스 대역폭을 많이 쓰는 스누핑의 한계를 극복하는 디렉토리 매핑 모델(NUMA 연계).

Out-of-Scope

• 소프트웨어 메모리 장벽(Memory Barriers): volatile이나 std::atomic을 통한 컴파일러 및 파이프라인 레벨의 순서(Ordering) 보장 $\rightarrow$ 02-02-03. Memory Barriers & Consistency 영역.
• OS 스레드 동기화 기법: 뮤텍스(Mutex), 세마포어(Semaphore) 알고리즘 구현 $\rightarrow$ 03-02. Process & Concurrency 영역.

Boundaries

• CCM vs. Memory Consistency (02-02-03): 일관성(CCM)이 "동일한 주소 X를 여러 코어가 덮어쓸 때, 가장 최신 값이 무엇인가"를 맞추는 '동일 주소의 최신화 물리학'이라면, 일관성 모델(02-02-03)은 "주소 X와 주소 Y를 각각 썼을 때, 다른 코어의 눈에 X가 먼저 바뀐 것으로 보이는가 Y가 먼저 바뀐 것으로 보이는가"를 따지는 '이종 주소 간의 시간적 순서 물리학'입니다.

3. Counterexample

• 동기화 없는 읽기/쓰기 가정 (Cache Visibility Fallacy): 멀티스레드를 작성하면서 "전역 변수 int flag = 0;을 선언해놓고 스레드1이 1로 바꾸면, 스레드2가 즉시(Instant) 1을 읽고 루프를 탈출하겠지"라고 가정하는 상황입니다. 코어1의 L1 캐시에만 flag=1(M 상태)이 남아 있고 메모리에는 0이 남아있는 상태에서, 동기화 강제 명령(Atomic/Fence) 없이 읽으면 코어2는 자신의 캐시나 메모리에서 계속 0을 읽어 데드락(Deadlock)에 빠질 수 있습니다.
• 거짓 공유에 의한 핑퐁 병목 (False Sharing Ping-Pong): 64바이트 캐시 라인 하나에 들어있는 배열 A[0]은 코어1이 쓰고 A[1]은 코어2가 쓰도록 스레드별로 역할을 나눴다고 가정하는 상황입니다. 하드웨어 MESI는 64바이트 전체를 하나의 상태 단위로 관리하므로, 코어1이 A[0]을 쓰면 코어2의 64바이트 라인 전체가 무효화(I)되고, 코어2가 A[1]을 쓰면 다시 코어1의 라인이 무효화되는 '무효화 핑퐁(Invalidation Storm)'이 발생해 CPU 캐시 버스가 포화될 수 있습니다.

4. Prerequisites

• 캐시 아키텍처와 Write-Back (Basic): 멀티코어 이슈는 각 코어가 메인 메모리를 바로 갱신하지 않고 캐시에 먼저 보관하는 Write-Back 정책 때문에 발생하므로, 캐시 교체와 쓰기 정책을 먼저 이해해야 합니다. (02-02-01 CDL)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 캐시 불일치와 멀티코어 가시성 (The Incoherence Problem)

• Why to Learn: 코어 개수를 늘리면 렌더링이 2배 빨라질 것처럼 보이지만 오히려 속도가 떨어질 수 있는 원인, 즉 '각 코어의 독립된 L1 캐시'가 만들어내는 데이터 가시성 차이를 이해하기 위함입니다.
• What to Learn:
  • Concepts: 일관성(Coherence), 더티 캐시 라인(Dirty Cache Line), 진실의 유일성(Single Point of Truth).
  • Skills: Write-Back 환경에서의 데이터 갱신 불일치 다이어그램 그리기.
  • Tools: 스레드 디버깅 로직 시뮬레이션.
  • Trade-offs: 모든 캐시를 없애고 코어들이 L3 캐시나 메모리에만 직접 접근하게 만들어 일관성 문제를 단순화하는 방식 vs L1 캐시를 유지해 속도를 높이는 대신, 칩 면적과 설계 복잡도를 일관성 프로토콜 회로에 투자해야 하는 하드웨어 비용.
• How to Learn:
  • 1단계: 코어A가 주소 X를 읽어 L1 캐시에 0을 저장하고, 코어B도 읽어서 0을 저장한 뒤, 코어A가 X를 1로 덮어쓰고(더티) 코어B가 다시 X를 읽을 때 발생하는 불일치를 시각화합니다.
  • 2단계: 코어A가 X에 1을 쓴 즉시(Write-Through) 메인 메모리를 갱신한다고 하더라도, 코어B의 캐시 안에는 여전히 0이 남아있기 때문에 단순 Write-Through 정책만으로는 불일치 문제를 해결할 수 없다는 논리를 분석합니다.
• Implement: 두 개의 가상 코어(A, B) 객체가 각자의 L1 캐시 배열을 갖고 있을 때, 한쪽이 값을 덮어써도 다른 쪽 배열은 이전 값을 반환하는 코드를 파이썬으로 작성하고, 이를 방지하려면 캐시 객체 간 통신 채널이 필요함을 입증하는 데모 작성.

Recommended

Core Topic 02: 버스 스누핑과 무효화 역학 (Bus Snooping & Invalidation)

• Why to Learn: 데이터를 캐시에 쓸 때마다 다른 코어들에게 전화를 걸어 "이 주소 내 캐시엔 이런 값이 있어!"라고 동기화시키는 하드웨어 전파 체계를 이해하기 위함입니다.
• What to Learn:
  • Concepts: 스누핑(Snooping), 무효화(Invalidation), 스누핑 필터(Snoop Filter).
  • Skills: 버스 브로드캐스트(Broadcast), 상태 태그 변경.
  • Tools: Shared Bus Architecture.
  • Trade-offs: 내가 값을 쓸 때마다 다른 코어 캐시에 그 값을 업데이트(Update)하는 방식의 직관성(하지만 버스 대역폭 사용량이 큼) vs "내가 쓸 것이므로 다른 캐시의 해당 라인을 유효하지 않음(Invalid)으로 표시하라"는 무효화(Invalidation) 신호만 보내는 방식의 대역폭 절약(현재 x86/ARM 표준).
• How to Learn:
  • 1단계: 모든 코어의 캐시 컨트롤러가 공유 버스(Shared Bus)를 스누핑(Snoop)하다가, 누군가가 "나 주소 X 쓴다(Write)"라는 신호를 보내면 자기 캐시 속 주소 X의 유효 비트(Valid Bit)를 0으로 바꾸는 과정을 분석합니다.
  • 2단계: 무효화를 받은 코어가 나중에 다시 주소 X를 읽으려 할 때 캐시 미스(Miss)가 발생하고, 메모리로 가려고 버스에 신호를 보내면 최신 값(더티)을 가진 코어가 캐시-투-캐시 전송(Cache-to-Cache Transfer)으로 응답하는 흐름을 살펴봅니다.
• Implement: 4개의 딕셔너리(캐시)가 하나의 리스트(버스)를 감시하는 Observer 패턴을 파이썬으로 구현. 코어1이 딕셔너리에 값을 Update할 때 버스에 Invalidate(Key) 이벤트를 보내고, 다른 코어들이 이벤트를 수신하면 자신의 딕셔너리에서 해당 키를 제거하는(pop) 소프트웨어 스누핑 모델 작성.

Practical

Core Topic 03: MESI 프로토콜 상태 기계 (MESI State Machine)

• Why to Learn: 멀티스레드 코드를 작성할 때 캐시 간섭(False Sharing)이 발생하면 왜 성능이 1/100 수준으로 떨어질 수 있는지, M-E-S-I 4가지 꼬리표가 바뀌는 하드웨어 오버헤드를 이해하기 위해서입니다.
• What to Learn:
  • Concepts: Modified(더티+독점), Exclusive(클린+독점), Shared(클린+공유), Invalid(무효).
  • Skills: 읽기 미스(Read Miss), 쓰기 미스(Write Miss), 무효화(Invalidate)에 따른 상태 전이도(FSM) 추적.
  • Tools: 캐시 라인 2비트 상태 플래그.
  • Trade-offs: 초기 MSI(3상태) 프로토콜에서 내가 혼자만 읽고 있는 값에 쓰기를 할 때조차 무효화 브로드캐스트를 보내야 하는 비효율 vs "이 데이터는 내 캐시에만 존재한다"는 Exclusive(E) 상태를 추가하여 버스 신호 없이 즉시 Modified(M)로 전이하는 최적화 타협.
• How to Learn:
  • 1단계: 어떤 코어가 주소 X를 최초로 읽으면 M이 아니라 E(Exclusive) 상태가 되고, 나중에 다른 코어가 같은 주소를 읽으려 할 때 버스를 스누핑하던 원래 코어가 응답하여 둘 다 S(Shared) 상태로 내려가는 읽기 동기화를 분석합니다.
  • 2단계: S 상태(다 같이 읽는 중)에서 누군가 쓰기(Write)를 시도하면, 독점권(Ownership)을 얻기 위해 나머지 모든 코어의 S를 I(Invalid)로 바꾸고 자신만 M(Modified)으로 전이하는 배타성(Exclusivity)을 살펴봅니다.
• Implement: 콘솔 기반 MESI 시뮬레이터를 작성하여, 3개의 코어 인스턴스가 존재할 때 Core1.read(X), Core2.read(X), Core1.write(X) 명령어 배열을 순차적으로 입력하면 캐시 라인의 상태가 I -> E -> S -> M (Core1) / I (Core2)로 바뀌는 텍스트 FSM 전이 로그를 출력.

Advanced

Core Topic 04: 디렉토리 기반 캐시 일관성과 스케일링 (Directory-based Protocol)

• Why to Learn: 인텔 Xeon이나 AMD EPYC 같은 64코어, 128코어 서버에서는 버스 스누핑(모두에게 브로드캐스트)을 그대로 쓰면 버스 대역폭이 빠르게 포화되므로, NUMA 아키텍처에서 일관성을 어떻게 스케일링하는지 이해하기 위함입니다.
• What to Learn:
  • Concepts: 디렉토리(Directory), 중앙 집중식/분산 디렉토리 제어, Home Node.
  • Skills: 존재 비트 벡터(Presence Bit Vector), 점대점 통신(Point-to-Point Messaging).
  • Tools: NUMA 아키텍처 모델.
  • Trade-offs: 스누핑 방식처럼 모두가 듣는 빠르고 단순한 버스를 쓰는 것(소규모 듀얼/쿼드 코어에 적합) vs 메모리 컨트롤러 옆에 "누가 주소 X를 가져갔는지" 적어두는 장부(디렉토리)를 두고, 대상 코어에게만 1<1> 메시지(Message)를 보내 수백 개의 코어를 엮는 확장성(대신 디렉토리 조회 지연 발생).
• How to Learn:
  • 1단계: 코어 100개가 연결된 링(Ring) 버스나 메시(Mesh) 네트워크에서 브로드캐스트 스누핑을 사용하면 $O(N^2)$ 트래픽이 발생할 수 있으므로, 메인 메모리의 디렉토리(장부)에 "코어 5번과 92번이 주소 X를 Shared 상태로 들고 있음"을 비트맵으로 기록하는 설계의 필요성을 분석합니다.
  • 2단계: 코어 3번이 쓰기(Write)를 시도할 때 디렉토리를 조회하여, 장부에 적힌 코어 5번과 92번에게만 Invalidate 메시지를 보내 네트워크 트래픽을 $O(1)$ 또는 $O(K)$로 제한하는 물리를 살펴봅니다.
• Implement: 64비트 정수를 비트마스크(디렉토리 Presence Vector)로 취급하여, 메모리 객체가 각 주소 블록마다 어느 코어(0~63번)가 복사본을 보유하는지 기록하고, 특정 코어의 Write 요청이 들어오면 비트가 1로 세팅된 코어 번호만 색인하여(Bitwise AND 연산) "Target Invalidate Message" 리스트를 콘솔에 정확하게 반환하는 디렉토리 라우터 로직.

7. Terminology

8. References

Primary

• [P1] CS2023 - AR/Multiprocessing and Alternative Architectures — Coherence requirements.
• [P2] SWEBOK v4.0 - Computing Foundations / Shared Memory — Consistency standards.

Secondary

• [Shared Memory Consistency Models: A Tutorial] Adve & Gharachorloo — Fundamental understanding of the bridge between hardware and software.
• [A Primer on Memory Consistency and Cache Coherence] Sorin et al. — The modern textbook for CCM.

Industry

• [Intel Hyper-Threading Technology Architecture and Microarchitecture] — Coherence in real silicon.
• [AMD64 Architecture Programmer's Manual - Memory System] — Practical implementation details.

9. Final Checklist

Primary

• MESI 프로토콜에서 특정 코어가 'Shared(S)' 상태의 라인을 쓰기(Write) 하려 할 때, 버스에 어떤 신호를 보내고 타 코어의 상태를 어떻게 바꾸는지 서술 가능한가? (P1)
• 사설 캐시를 가진 2개 이상의 코어가 동일 주소의 데이터를 읽기만 할 때(Read-only), MESI 상태가 왜 'Shared'로 유지되는 것이 물리적으로 이득인지 설명할 수 있는가? (P1)

Secondary

• 'Cache Invalidation' 트래픽이 너무 많아져 버스가 포화되었을 때, 전체 시스템 클록 속도보다 메모리 동기화 지연이 커지는 현상을 수학적으로 분석할 수 있는가?
• MESI에서 파생된 MOESI나 MESIF 프로토콜이 공유 데이터 전송 효율을 위해 물리적으로 어떤 상태를 추가했는지 그 필요성을 입증 가능한가?

Industry

• 고성능 대규모 병렬 처리용 라이브러리(예: LMAX Disruptor) 설계 시, 'False Sharing'을 방지하기 위해 캐시 라인 패딩 전략을 어떻게 수립할지 제안할 수 있는가? (SFIA)
• 멀티코어 환경에서 원자적 명령어(Atomic Instructions)가 수행될 때, 하드웨어가 해당 캐시 라인을 어떻게 'Locking' 하거나 'Exclusive' 하게 점유하는지 물리적 과정을 분석할 수 있는가?