캐시 일관성 프로토콜 (Cache Coherence Protocol)

개요

캐시 일관성(Cache Coherence)은 다중 프로세서 시스템에서 여러 프로세서의 캐시 메모리에 동일한 메모리 주소에 대한 복사본이 존재할 때, 각 캐시의 데이터가 일관성을 유지하도록 보장하는 메커니즘이다. 현대의 멀티코어 프로세서는 각 코어가 독립적인 L1/L2 캐시를 보유하고 있으므로, 한 코어에서 수정한 데이터가 다른 코어에서 정확하게 보이도록 하는 일관성 프로토콜이 필수적이다.

캐시 일관성 문제는 공유 메모리 병렬 컴퓨팅에서 가장 중요한 도전 과제 중 하나이며, MESI, MOESI, 디렉터리 기반 등 다양한 프로토콜이 개발되었다. 본 문서에서는 주요 캐시 일관성 프로토콜의 동작 원리와 특징을 분석한다.

핵심 개념

MESI 프로토콜

MESI 프로토콜은 invalidate 기반 캐시 일관성 프로토콜로서, write-back 캐시를 지원하는 가장 일반적인 프로토콜이다. 일리노이 대학교에서 개발되었기 때문에 "일리노이 프로토콜"이라고도 알려져 있다.

네 가지 상태

상태 전이 동작

프로세서 요청 (Processor Requests):
- PrRd: 프로세서가 캐시 블록을 읽으려는 요청
- PrWr: 프로세서가 캐시 블록에 쓰려는 요청

버스 요청 (Bus Transactions):
- BusRd: 다른 프로세서의 읽기 요청을 스누핑
- BusRdX: 캐시에 없는 블록에 대한 쓰기 요청을 스누핑
- BusUpgr: 이미 캐시에 있는 블록에 대한 쓰기 요청을 스누핑
- Flush: 다른 프로세서에 의해 전체 캐시 블록이 주기억장치에 기록됨

대표적인 상태 전이 흐름:
1. Invalid → Exclusive/Shared: 프로세서가 읽기 미스 시 BusRd 발생. 다른 캐시에 유효한 복사본이 있으면 Shared, 없으면 Exclusive로 전이
2. Invalid → Modified: 프로세서가 쓰기 미스 시 BusRdX 발생. 다른 캐시의 복사본은 무효화
3. Exclusive → Modified: 프로세서가 쓰기 히트 시 버스 트랜잭션 없이 바로 전이
4. Shared → Modified: 프로세서가 쓰기 시 BusUpgr 발생하여 다른 캐시의 복사본 무효화

MOESI 프로토콜

MOESI 프로토콜은 MESI 프로토콜을 확장하여 "Owned" 상태를 추가한 다섯 상태 프로토콜이다. 핵심 차이는 더티 데이터를 즉시 주기억장치로 되돌리지 않고도 다른 코어에 전달할 수 있다는 점이며, 이로 인해 코어 간 공유가 잦은 워크로드에서 외부 메모리 트래픽을 줄일 수 있다.

다섯 가지 상태

Owned 상태의 특징

Owned 상태는 수정된 캐시 블록을 주기억장치에 기록하지 않고 다른 프로세서에게 직접 전달할 수 있게 한다. 이는 두 프로세서 간의 통신이 주기억장치보다 상당히 빠른 경우, 예를 들어 코어별 L2 캐시를 가진 멀티코어 CPU에서 이점이 된다.

버스 스누핑 (Bus Snooping)

버스 스누핑은 캐시의 코히런시 컨트롤러(스누퍼)가 버스 트랜잭션을 감시하여 분산 공유 메모리 시스템에서 캐시 일관성을 유지하는 방식이다.

스누핑 프로토콜 유형

쓰기-무효화 (Write-invalidate):
- 프로세서가 공유 캐시 블록에 쓸 때, 다른 캐시의 모든 공유 복사본을 무효화
- MSI, MESI, MOESI, MESIF 프로토콜이 이 범주에 속함
- 가장 일반적으로 사용되는 프로토콜

쓰기-업데이트 (Write-update):
- 프로세서가 공유 캐시 블록에 쓸 때, 다른 캐시의 모든 공유 복사본을 업데이트
- 쓰기 데이터를 버스를 통해 모든 캐시로 브로드캐스트
- 더 많은 버스 트래픽을 유발하여 일반적이지 않음

디렉터리 기반 일관성 (Directory-based Coherence)

디렉터리 기반 캐시 일관성은 버스 스누핑을 대체하여 디렉터리를 사용하여 캐시를 관리하는 메커니즘이다. 대규모 멀티프로세서 시스템에서 확장성을 제공한다.

디렉터리 형식 유형

비교/분석

MESI vs MOESI 비교표

버스 스누핑 vs 디렉터리 기반 비교

동작 원리

MESI 프로토콜 동작 흐름

[프로세서 요청] → [캐시 태그 조회]
                      ↓
              [히트/미스 판별]
                      ↓
        [히트] → [상태에 따라 처리]
        [미스] → [버스 트랜잭션 발생]
                      ↓
              [스누핑 응답 처리]
                      ↓
              [상태 전이 수행]

상태 전이 상세

읽기 미스 (Read Miss) 시나리오

1. 프로세서가 유효하지 않은 블록을 읽으려 함
2. BusRd 트랜잭션이 버스에 발생
3. 다른 캐시 스누퍼가 BusRd를 감지
4. 다른 캐시에 유효한 복사본이 있는 경우:
   - Modified 상태라면 Flush 발생 후 Shared로 전이
   - Exclusive/Shared 상태라면 Shared로 전이
5. 다른 캐시에 유효한 복사본이 없으면 Exclusive로 전이

쓰기 미스 (Write Miss) 시나리오

1. 프로세서가 유효하지 않은 블록에 쓰려 함
2. BusRdX 트랜잭션이 버스에 발생
3. 다른 캐시의 복사본은 모두 Invalid로 무효화
4. 요청 캐시는 Modified 상태로 전이

쓰기 히트 (Write Hit) 시나리오

1. 프로세서가 Shared 상태의 블록에 쓰려 함
2. BusUpgr 트랜잭션이 버스에 발생
3. 다른 캐시의 복사본은 모두 Invalid로 무효화
4. 요청 캐시는 Modified로 전이

디렉터리 기반 동작 원리

1. 프로세서가 캐시 블록에 접근
2. 로컬 디렉터리 컨트롤러에 쿼리 전송
3. 디렉터리가 해당 블록의 상태와 보유 캐시 목록 확인
4. 필요시 다른 캐시에 일관성 메시지 전송
5. 응답에 따라 상태 전이 수행

장단점

MESI 프로토콜

장점:
- 구현이 상대적으로 단순
- Exclusive 상태로 불필요한 BusUpgr 트랜잭션 방지
- 소규모 멀티코어 시스템에서 높은 성능
- Intel 프로세서에서 입증된 안정성

단점:
- Shared 상태에서 쓰기 소유권을 얻기 위해 반복적인 invalidation이 발생할 수 있음
- 구현에 따라 여러 스누퍼의 응답 조정 로직이 복잡해질 수 있음
- 대규모 시스템으로 확장 시 버스 대역폭 병목

MOESI 프로토콜

장점:
- Owned 상태로 캐시 간 직접 데이터 전송 가능
- 주기억장치 기록 빈도 감소
- 코어 간 통신이 빠른 멀티코어 시스템에서 높은 효율
- 버스 대역폭 절약

단점:
- MESI보다 구현 복잡도 증가
- Owned 상태 관리에 따른 하드웨어 오버헤드
- Intel 프로세서에서는 채택되지 않음

버스 스누핑

장점:
- 구현이 단순하고 하드웨어 비용이 낮음
- 지연 시간이 짧음
- 소규모 시스템에서 높은 성능

단점:
- 확장성 제한 (시스템 커질수록 버스 대역폭 증가 필요)
- 빈번한 스누핑으로 인한 접근 시간 증가 및 전력 소비 증가
- 모든 트랜잭션이 모든 노드로 브로드캐스트되어야 함

디렉터리 기반

장점:
- 높은 확장성
- 불필요한 스누핑 최소화
- 대규모 시스템에서 효율적 대역폭 사용

단점:
- 디렉터리 저장 오버헤드
- 지연 시간 증가
- 하드웨어 복잡도 증가

관련 기술

현대 프로세서 구현

관련 문서

• CPU 마이크로아키텍처 기초: 파이프라인, 캐시 계층, IPC 관점에서 캐시 일관성이 왜 필요한지 연결해서 볼 수 있다.
• Out-of-Order 실행: load/store queue와 speculative execution이 coherence 트래픽과 어떻게 맞물리는지 이해할 때 도움이 된다.
• 메모리 일관성 모델: coherence가 "같은 주소의 최신 값"을 맞추는 문제라면, consistency는 "관측 순서"를 정의하는 문제라는 점을 비교할 수 있다.

성능 최적화 기법

스눕 필터 (Snoop Filter):
- 불필요한 스누핑을 줄이기 위한 메커니즘
- 소스 필터: 캐시 측면에서 일관성 트래픽 필터링
- 디스티네이션 필터: 수신자 캐시에서 불필요한 태그 조회 방지

Inclusive/Exclusive 캐시 정책:
- Inclusive Cache: 상위 레벨이 하위 레벨의 모든 블록을 포함. snoop 필터 설계와 invalidation 전파가 단순해짐
- Exclusive Cache: 상위/하위 레벨이 동일 블록을 보유하지 않음. 전체 용량 효과적 활용

메모리 배리어:
- 스토어 배리어: 스토어 버퍼를 플러시하여 모든 쓰기가 캐시에 적용되도록 보장
- 리드 배리어: invalidate 큐를 비워 다른 CPU의 쓰기가 현재 CPU에 관측되도록 보장

참고 논문

1. Papamarcos & Patel (1984): MESI 프로토콜 원래 논문
2. Ravishankar & Goodman (1983): 버스 스누핑 도입
3. Culler et al. (1997): Parallel Computer Architecture
4. Laudon & Lenoski (1997): SGI Origin의 디렉터리 기반 일관성
5. Chaiken et al. (1990): 대규모 멀티프로세서에서의 디렉터리 기반 캐시 일관성

관련 표준

• x86-64 아키텍처 (Intel, AMD)
• ARM 아키텍처 (ARM Holdings)
• IEEE 표준 (인터커넥트 표준에서의 일관성 메커니즘)

핵심 교재

• Hennessy & Patterson: "Computer Architecture: A Quantitative Approach"
• Culler et al.: "Parallel Computer Architecture"
• Sorin et al.: "A Primer on Memory Consistency and Cache Coherence"

핵심 정리

1. MESI 프로토콜은 Modified, Exclusive, Shared, Invalid 네 가지 상태를 사용하여 invalidate 기반 캐시 일관성을 구현하며, Intel 프로세서에서 널리 사용된다.

2. MOESI 프로토콜은 MESI에 Owned 상태를 추가하여 캐시 간 직접 데이터 전송이 가능하게 하며, AMD 프로세서에서 주로 사용된다.

3. 버스 스누핑은 소규모 시스템에서 높은 성능을 제공하지만, 확장성의 한계로 인해 대규모 시스템에서는 디렉터리 기반 프로토콜이 선호된다.

4. 현대 프로세서들은 스눕 필터, Inclusive/Exclusive 캐시 정책, 메모리 배리어와 같은 최적화 기법을 활용하여 성능을 극대화한다.

5. 캐시 일관성 프로토콜의 선택은 시스템 크기, 성능 요구사항, 하드웨어 복잡도에 따라 결정되며, 실제 시스템에서는 여러 프로토콜이 혼합되어 사용될 수 있다.