[컴퓨터구조#11-1] 캐시 일관성 (Cache Coherence) - MSI, MESI, MOESI 프로토콜

참고: Computer Architecture: A Quantitative Approach (5th edition) - 5.2.

이번 글에서는 캐시 일관성에 대한 개념 소개 및 3가지 프로토콜에 대해서 다루고자 한다.

목차

1. 캐시 일관성 문제
2. MSI 프로토콜
3. MESI 프로토콜
4. MOESI 프로토콜

---

1. 캐시 일관성 문제

소프트웨어는 캐시 일관성에 대해 신경쓰지 않는다. 하드웨어는 여러 캐시나 메인 메모리 내의 같은 주소에 대해 값들을 유지해야 하며, 하나의 공유 메모리 공간에 대한 추상화를 지원해야 한다. 

→ 캐시 일관성이란, 공유 메모리 멀티프로세서에서의 통신 메커니즘을 뜻한다.

• 프로세서는 데이터를 공유하기 위해 로컬 캐시를 읽거나/에 쓴다.
• 캐시 일관성은 여러 프로세서에 공유되는 데이터 값을 제공하는 데 그 책임이 있다.
• 좋은 캐시 일관성 메커니즘은 1) 노드 간 트랜잭션을 가능한 한 줄여야 하며(예를 들면, 로컬 캐시에 유용한 캐시 블록을 가능한 한 오래 갖고 있어야 한다), 2) 생선자에서 소비자로의 빠른 데이터 전송을 가능하게 해야 한다.

그렇다면 일관성 문제가 어떤 상황에서 발생하는지 조금 더 자세하게 알아보자.

A와 B가 메모리에 저장되어 있는 값을 읽어 각 프로세서의 로컬 캐시에 저장했지만, Time 3에서 A가 X의 값을 바꿔 버리면 메모리 및 A의 캐시에 있는 X의 값은 0으로 바뀌지만 B의 캐시는 업데이트되지 못하고 X의 이전 값인 1을 가지고 있게 된다. 이처럼 서로 다른 두 프로세서가 같은 위치에 대해 서로 다른 값을 갖는 상황을 캐시 일관성 문제라고 한다.

하나의 메모리 위치(X)에 대해, A와 B 두 개의 프로세서에서 읽기와 쓰기가 이루어지는 경우 캐시 일관성 문제

이러한 문제를 해결하기 위해서는, 쓰기에 대한 결과를 다른 프로세서에 전파propagate시켜야 한다. 전파 방법에는 업데이트 기반 프로토콜과 비활성화 기반 프로토콜 두 가지 방법이 있다.

Update-based Protocols

• 모든 업데이트는 다른 캐시와 메인 메모리로 보내진다.
• write-through 캐시와 비슷하다.
• 각 명령어에 대해 write을 보내기 때문에 다른 캐시로의 네트워크를 통한 write 트래픽이 막대하다. (대역폭 낭비)
  • 마지막 쓰기만 보여지므로, 쓰기의 시간적 지역성을 활용하지 않는다. 
  • 업데이트된 copy를 갖고 있더라도 해당 코어에서 실제로 그 데이터를 사용하지 않을 수도 있다.
  • 실제 데이터가 전달되어야 하므로 전파에 오랜 시간이 소요된다.
  • 구현상 복잡성이 높다.
• producer-consumer 간 통신을 빠르게 만들 수 있다.

Invalidation-based Protocols

• 블록을 업데이트하려면, 다른 캐시에 먼저 invalidation을 보낸다.
  • 커맨드/주소와 함께 비활성화 메시지만 보내면 되며(데이터가 전송될 필요가 없다). 데이터는 필요한 경우에만 전달된다.
  • 즉, 캐시에 대한 네트워크와 쓰기 트래픽을 절약할 수 있다. 하지만 producer-consumer 간 통신은 느리게 만들 수 있다.
• writer의 copy는 수정된 dirty state이며, 나머지 copy들은 비활성화된 상태이다.
• 만약 다른 캐시가 비활성화된 주소에 접근하려고 하면, 캐시 미스를 일으키게 되며 writer 혹은 메모리가 데이터를 제공해야 한다.
• 대부분의 상업용 멀티프로세서에서 사용되는 방식이다.

이 중 Invalidation-based 프로토콜에 대해서 자세히 알아보자.

캐시 일관성 프로토콜에서는, 각 캐시 블록의 copy는 공유되는 state를 갖게 된다. (이 state는 valid, dirty와 같이 다른 곳에서도 보여지는 값을 의미한다.) 일관성 프로토콜은 각 캐시 혹은 메모리가 해당 공유 state에 기반하여 어떻게 행동할지, 그리고 다음은 어떤 state로 바뀌게 될지를 정의한다. 이 state는 어떤 캐시가 주어진 주소에 대한 copy를 갖고 있는지를 알려준다. state를 어떻게 트래킹하는지에 따라 스눕 기반/디렉토리 기반 프로토콜로 나뉜다.

• Snoop-based protocols: state를 공유하는 중앙화된 저장소가 존재하지 않음. 모든 요청은 모든 노드로 broadcast된다(어떤 캐시가 copy를 갖고 있을지 모르기 때문). 작거나 중간 크기의 shared memory 멀티프로세서에서 흔함. 효율적인 broadcasting이 어렵기 때문에 크기를 키우기는 어렵다.
  • 스눕 기반 프로토콜의 동작과정! (모든 캐시가 snooping에 참여한다.)
    1. 모든 캐시 미스 요청은 bus에 전달되어야 한다.
    2. 모든 캐시와 메모리는 버스 요청을 관찰한다.
    3. 모든 캐시는 요청을 snoop하고(읽고), 캐시 태그를 확인한다.
    4. 각 캐시는 요청에 따라 응답한다.
       • state를 단순히 공유 (필요한 copy를 갖고 있는 경우)
       • 데이터를 전달 (수정된 copy를 갖고 있어 메모리나 다른 캐시에 보내야 하는 경우)
• Directory-based protocols: state를 공유하는 디렉토리라는 논리적으로 중앙화된 저장소가 존재함. 모든 메모리 블록에 대한 디렉토리 entry가 필요. 비활성화 요청은 디렉토리에 먼저 들어가고, 해당 데이터를 가진 sharer에게만 포워딩됨. 소수의 상업용 멀티프로세서에서만 사용됨.

.이 중 오늘 알아볼 프로토콜들은 스눕 기반의 캐시 일관성 프로토콜을 사용한다.

앞서 일관성 문제를 살펴보았던 예시에서, 스눕 기반 & 비활성화 기반 캐시 일관성 프로토콜을 사용한다고 생각해보자.

• A,B가 X를 읽은 후,
• A가 X에 write하려고 할 때 A는 다른 캐시에 먼저 비활성화 메시지를 보낸다. 이는 bus를 통해 이루어진다. 이후 A가 X에 1의 값을 쓰고, 쓰여진 값은 A의 캐시에만 존재하며 메모리에는 아직 이전 값이 유지된다.
• 이후 B가 X를 읽으려고 할 때, X에 대해 캐시 미스가 발생하며(비활성화 메시지가 보내져 있는 상태이므로), 이후 A의 캐시에 있던 값이 메인 메모리로 저장되고, 메인 메모리에서 값을 읽어와 B의 캐시에도 1의 값을 가져올 수 있는 것이다.

Snoopy 프로토콜을 위한 아키텍처

• 태그를 통한 캐시 state 확장: 캐시 태그는 일관성 state(단일 프로세서 캐시 state에서 Valid bit와 Dirty bit 확장)를 유지해야 한다.
• broadcast 매체 (=버스): 다른 캐시에 비활성화를 포함한 모든 요청을 보내야 함. 논리적으로는 모든 노드와 메모리를 연결하는 wire의 집합을 뜻함.
• 버스를 통한 serialization: 오직 하나의 프로세서만 비활성화 메시지를 보낼 수 있음. 메모리 요청의 전반적인 순서를 결정.
• 버스 트랜잭션 snooping
  • 모든 캐시는 버스를 통한 모든 트랜잭션을 볼 수 있어야 함.
  • 각 트랜잭션에 대해, 캐시들은 어떤 액션이 필요한지 확인하기 위해 태그를 확인해야 함.
  • 필요하다면, 스눕은 state transition과 새로운 버스 트랜잭션을 일으킬 수 있음.
    • 캐시 컨트롤러: 다음 state 결정
    • state 변화의 두 가지 soure: CPU(명령어 LD/ST) / Snoop(다른 프로세서에서 온 요청)
    • 스눕 태그 lookup: 버스의 모든 요청을 snoop. CPU요청용/다른 스눕용으로 2개의 동일한 태그를 가짐.

 

2. MSI 프로토콜

3개의 state를 갖는 단순한 프로토콜이다.

M (Modified)	- valid & dirty - 전체 시스템에서, 각 블록 주소에 대해 하나의 M state copy만 존재할 수 있다. (이 경우 해당 주소에 대한 나머지 캐시는 모두 I 상태여야 함.) - 다른 캐시를 비활성화하지 않고도 존재할 수 있다. - eivct 시 메모리로 write back되어야 한다.
S (Shared)	- valid & clean - 다른 캐시도 copies를 가질 수 있다. - 업데이트 불가
I (Invalid)	- invalid

State 전환에 필요한 CPU 및 bus 요청은 다음과 같다.

CPU Requests	Bus requests (snoop)
- PrRd : load 명령어 - PrWr : store 명령어 -> bus request를 생성한다.	- Bus Read (BusRd) : 일반적인 읽기 - Bus Read For Ownership (BusRFO) : 캐시 write 전 먼저 읽기. 비활성화 메시지에 해당한다. - Bus Upgrade (BusUp) : S->M. (읽기는 포함하지 않음) - Bus Writeback (BusWB)

MSI state 변화 - CPU 요청

• 더 높은 level의 state로 변화한다. (I -> S -> M)
• I에서 처음 M이나 S로 변할 때는 캐시미스가 발생한다.

출처: 위키피디아

MSI state 변화 - Snoop 요청

• 더 낮은 level의 state로 변화한다. (M -> S -> I)

출처: 위키피디아

 

예시

step	P1		P2		P3		Bus		Mem
	state	value	state	value	state	value	Action	Proc	Value
	I		I		I				10
P1 read A	S	10	I		I		BusRd	P1	10
P2 read A	S	10	S	10	I		BusRd	P2	10
P2 write A (20)	I		M	20	I		BusUp	P2	10
P3 read A	I		S	20	S	20	BusRd	P3	20
P1 write A (30)	M	30	I		I		BusRFO	P1	20

이때 마지막 단계에서, 아직 P1 cache가 write back되지 않았으므로 캐시에는 갓 wirte 한 값인 30이, 메모리에는 이전 값인 20이 남아있게 된다.

캐시 일관성 지원: 쓰기 전파, 쓰기 직렬화

• 일관성: 하나의 메모리 위치가 다른 여러 프로세서에 의해 어떻게 보여지는지를 다룬다. 여러 메모리 위치 간 순서를 정함으로써 consistency를 유지하게 된다. 이는 반드시 쓰기 전파wirte propagation와 쓰기 직렬화write serialization를 지원해야 한다.
• 쓰기 전파: 쓰기는 다른 프로세서에도 visible해야 한다.
• 쓰기 직렬화: 한 장소에 대한 모든 쓰기는 모든 프로세서에 동일한 순서로 보여야 한다. 예를 들어, A에 대한 w1, w2 두 개의 쓰기가 있는 경우, 한 프로세서가 w1 전에 w2를 보았다면 다른 모든 프로세서도 반드시 w1 전에 w2를 보아야 한다.

일반적으로, load -> store의 시퀀스가 흔하게 발생한다. 즉 read only copy(S state)를 먼저 install하고 이후에 수정을 위한 업그레이드 단계(M state)가 따로 필요한 것이다. 하지만, 다른 캐시가 해당 copy를 갖지 않을 가능성이 매우 높다. 잘 병렬화된 프로그램에서는 private data가 흔하고, 공유된 데이터이더라도 제한된 캐시 용량으로 인해 다른 캐시에 존재하지 않을 수 있기 때문이다. 즉 이후의 store는 M 단계로 업그레이드 시 write miss가 발생하여 불필요한 일관성 트랜잭션이 발생하게 된다. 이를 해결하기 위한 것이 MESI 프로토콜이다.

 

3. MESI 프로토콜

MSI 프로토콜에 Exclusive 단계가 추가된 프로토콜이다.

E(Exclusive): valid & clean. 다른 캐시가 해당 블록의 copy를 갖고 있지 않는 경우.

MESI 프로토콜에서는, 새 블록을 install할 때 sharing state를 먼저 확인해야 한다.

• BusRd 트랜잭션에 대해, 모든 노드는 snoop hit이나 snoop miss 중 하나의 응답을 하게 된다.
• 만약 다른 캐시가 복사본을 갖고 있는 경우(snoop hit), 새 블록은 S state로
• 만약 복사본을 갖고 있는 다른 캐시가 없는 경우(모두 snoop miss), 새 블록은 E state로 install된다.

E->M 변화는 버스 트랜잭션 없이 free하게 일어난다. 즉, store에 대해서 E에서 M으로의 업그레이드는 비활성화 메시지를 보내지 않고 일어나게 된다.

MESI state 변화 - 검정: CPU / 빨강: Snoop

출처: 위키피디아

예시

step	P1		P2		P3		Bus		Mem
	state	value	state	value	state	value	Action	Proc	Value
	I		I		I				10
P1 read A	E	10	I		I		BusRd	P1	10
P1 write A (15)	M	15	I		I		None		10
P2 read A	S	15	S	15	I		BusRd	P2	15
P2 write A (20)	I		M	20	I		BusUp	P2	15
P3 read A	I		S	20	S	20	BusRd	P3	20
P1 write A (30)	M	30	I		I		BusRFO	P1

 

3. MOESI 프로토콜

MESI 프로토콜에서, M -> S로의 downgrade에는 다음과 같은 문제가 있다.

• 다른 캐시에서의 read에 의해 발생함
• 수정된 블록은 메모리로 write back되어야 함
• 적어도 2개의 캐시가 해당 블록에 대한 복사본을 갖고 있으므로, 굳이 메모리에 한번 write back했다가 다시 읽어오는 대신(redundant) 곧바로 캐시에서 캐시로 데이터를 보내주자!

O (Owner) : valid & dirty. 다른 캐시가 copy를 갖고 있을 수 있음(exclusive copy 아님). evict 시 메모리로 write back되어야 함. 다른 캐시에 dirty block을 보내주어야 함.

BusSnd: 데이터를 메모리가 아닌 다른 프로세서로 보내주는 버스 명령어.

MOESI state 변화 - CPU

MOESI state 변화 - snoop

*위 그림에서, O에서 BusRFO/---, BusUp/--- 시 I state로 전환되는 화살표가 추가되어야 한다.

예시

step	P1		P2		P3		Bus		Mem
	state	value	state	value	state	value	Action	Proc	Value
	I		I		I				10
P1 read A	E	10	I		I		BusRd	P1	10
P1 write A (15)	M	15	I		I		None		10
P2 read A	O	15	S	15	I		BusRd	P2	15
P1 evict A	I		S	15	I		BusWB	P1	15
P2 write A (20)	I		M	20	I		BusUp	P2	15
P3 read A	I		O	20	S	20	BusRd	P3	15
P1 write A (30)	M	30	I		I		BusRFO	P1	15