캐시 메모리와 MESI 프로토콜: 멀티코어 성능을 좌우하는 원리

메모리 지연을 숨기는 캐시의 전제

CPU가 필요한 데이터와 명령어를 매번 주기억장치에서 가져오면 접근 지연이 누적된다. 캐시는 CPU와 주기억장치 사이에 자주 쓰이는 데이터와 명령어를 임시로 두는 고속 버퍼이며, 이 속도 차이, 즉 Memory Wall을 완화하는 역할을 맡는다.

캐시가 성립하는 근거는 프로그램의 접근 패턴에 있다. 최근 사용한 값은 다시 읽힐 가능성이 높고, 한 주소 주변의 데이터나 명령어도 이어서 접근되는 경향이 있다.

지역성	의미	예시
시간적 지역성(Temporal)	최근 접근한 데이터가 다시 접근될 가능성이 높다	루프 카운터, 지역 변수
공간적 지역성(Spatial)	인접한 메모리 주소의 데이터가 함께 접근될 가능성이 높다	배열 순차 접근, 명령어 시퀀스
순차적 지역성(Sequential)	프로그램이 순서대로 실행되는 경향이 있다	명령어 스트림

⤢✕

캐시 라인 단위로 움직이는 데이터

캐시 라인은 캐시와 주기억장치가 데이터를 주고받는 최소 단위다. 일반적으로 크기는 32바이트에서 128바이트이며, 현대 프로세서는 대부분 64바이트 캐시 라인을 사용한다.

주소는 태그, 인덱스, 오프셋으로 나뉜다. 인덱스는 캐시 세트를 고르고, 오프셋은 캐시 라인 안의 바이트를 가리키며, 태그는 해당 라인이 요청한 메모리 블록인지 판별하는 데 쓰인다.

⤢✕

라인을 크게 잡으면 공간적 지역성을 더 활용하고, 메모리 대역폭을 효율적으로 사용할 수 있다. 태그 저장 오버헤드도 줄어든다. 반면 실제로 필요하지 않은 데이터까지 옮겨 캐시 오염(Cache Pollution)을 유발할 수 있고, False Sharing도 악화될 수 있다.

매핑 방식이 만드는 충돌의 차이

직접 매핑(Direct Mapped)은 각 메모리 블록이 캐시의 특정 위치에만 놓일 수 있다. 하드웨어 구현과 검색은 단순하고 빠르지만, 같은 위치를 두고 경합하는 블록이 많으면 충돌 미스(Conflict Miss)가 빈발한다.

완전 연관(Fully Associative)은 어떤 블록이든 캐시의 어느 위치에나 저장할 수 있다. 충돌 미스는 최소화하지만, 하드웨어가 복잡해지고 검색도 느려진다.

집합 연관(Set Associative)은 두 방식 사이의 선택지다. 캐시는 N개의 way를 가진 세트로 나뉘고, 주소 인덱스로 세트를 선택한 뒤 해당 세트의 way에서 태그를 비교한다.

⤢✕

히트율만으로는 부족한 미스 분석

요청한 데이터가 캐시에 있으면 캐시 히트(Cache Hit)이고, 없어서 주기억장치를 다시 접근해야 하면 캐시 미스(Cache Miss)다. 히트율은 캐시 히트 수를 전체 메모리 접근 수로 나눈 값이다.

미스는 원인에 따라 구분해야 대응 방법도 달라진다.

미스 유형	원인	대응 방향
강제 미스(Compulsory)	최초 접근에서 불가피하게 발생	프리페칭(Prefetching)
용량 미스(Capacity)	캐시 크기가 부족	캐시 용량 증가
충돌 미스(Conflict)	동일 세트에서 여러 블록이 경합	연관도 증가

평균 메모리 접근 시간(AMAT)은 히트 시간에 미스가 초래하는 비용을 더해 계산한다.

AMAT = 히트 시간 + (미스율 × 미스 페널티)

히트 시간이 1ns, 미스율이 5%, 미스 페널티가 100ns인 경우는 다음과 같다.

AMAT = 1 + (0.05 × 100) = 6ns

여러 코어의 복사본이 충돌할 때

각 코어가 독립적인 캐시를 가진 멀티코어 시스템에서는 같은 메모리 주소가 여러 캐시에 복제될 수 있다. 한 코어가 값을 바꾸면 다른 코어가 보유한 복사본은 더 이상 같은 값을 가리키지 않을 수 있다. 캐시 일관성은 이 불일치를 다루는 문제다.

⤢✕

스누핑(Snooping) 프로토콜에서는 모든 캐시가 공유 버스를 감시하고, 다른 캐시의 트랜잭션을 관찰해 일관성을 유지한다. 이 방식은 버스 대역폭이 확장성을 제한한다.

디렉토리(Directory) 프로토콜은 중앙 디렉토리가 캐시 라인 상태를 추적한다. 대규모 시스템에 적합하며 NUMA 시스템에서 주로 사용된다.

MESI가 캐시 라인을 관리하는 방법

MESI는 스누핑 기반 캐시 일관성 프로토콜이다. Illinois 프로토콜이라고도 하며, 캐시 라인마다 Modified, Exclusive, Shared, Invalid 상태를 둔다.

상태	약자	의미
Modified	M	이 캐시만 유효 복사본을 보유하며 수정된 상태
Exclusive	E	이 캐시만 유효 복사본을 보유하지만 수정되지 않은 상태
Shared	S	여러 캐시가 유효 복사본을 보유한 상태
Invalid	I	캐시 라인이 무효화된 상태

⤢✕

주소 X를 코어 1만 읽는 경우에는 캐시 미스 뒤 메모리에서 데이터를 가져오고, 다른 캐시에 X가 없으면 Exclusive 상태가 된다. 이어 코어 2가 X를 읽으면 코어 1은 스누핑으로 이를 감지해 E에서 S로 전이하고, 코어 2도 S 상태의 복사본을 얻는다.

공유 상태에서 코어 1이 X에 쓰면 코어 2의 캐시 라인은 S에서 I로 무효화되고, 코어 1의 라인은 S에서 M으로 전이한 뒤 데이터가 수정된다.

MESI를 확장한 프로토콜도 있다.

프로토콜	추가 상태	설명
MOESI	O(Owned)	수정된 공유 상태 추가
MESIF	F(Forward)	스누핑 응답 최적화
MERSI	R(Recent)	최근 접근 추적

논리적으로 분리된 값이 같은 라인을 공유할 때

False Sharing은 서로 다른 코어가 하나의 캐시 라인 안에 있는 서로 다른 데이터를 접근할 때 생기는 성능 저하다. 데이터는 논리적으로 공유되지 않지만 물리적으로 같은 라인에 있어, 한쪽의 쓰기가 다른 쪽에 불필요한 캐시 무효화를 일으킨다.

⤢✕

패딩(Padding)은 변수 사이에 더미 데이터를 넣어 캐시 라인을 나누는 방법이다.

struct AlignedData {
    int counter;
    char padding[60];  // 64바이트 정렬
};

또 다른 방법은 컴파일러 지시자나 메모리 할당 함수를 이용해 캐시 라인 경계에 데이터를 정렬하는 것이다.

__attribute__((aligned(64))) int counter1;
__attribute__((aligned(64))) int counter2;

접근 패턴에 맞춘 캐시 활용

프리페칭(Prefetching)은 데이터가 필요해지기 전에 캐시로 가져오는 기법이다. 하드웨어 프리페칭은 CPU가 접근 패턴을 분석해 자동으로 수행하고, 소프트웨어 프리페칭은 프로그래머가 명시적으로 힌트를 제공한다.

루프 타일링(Loop Tiling)은 큰 배열을 캐시에 맞는 작은 블록으로 나눠 처리한다. 데이터 구조도 접근 패턴에 맞춰 배치해야 하며, Array of Structures와 Structure of Arrays의 선택 역시 이 문제와 맞닿아 있다.

캐시 계층별로 병목을 보는 지점도 다르다.

캐시 레벨	크기	지연 시간	최적화 포인트
L1	32-64KB	1-4 사이클	핫 데이터 배치
L2	256KB-1MB	10-20 사이클	워킹 세트 관리
L3	8-64MB	30-50 사이클	스레드 간 공유

캐시 라인 단위의 데이터 배치, 히트율과 미스 원인, 멀티코어의 일관성 관리가 함께 맞물린다. 시스템 프로그래밍에서는 히트율을 높이고 False Sharing을 피하며 캐시 친화적인 알고리즘을 설계하는 일이 전체 시스템 성능에 직접 연결된다.