Lec 17 part 2 · snooping protocol(VI·MI·MSI·MESI) 과 directory-based coherence

1.1cache coherence 의 극단적 해법 3가지에서 출발해 write-through 기반 write-update·valid-invalid protocol 을 state machine 으로 정리.

1.2write-back 기반 Modified-Invalid → multiple copies 를 위한 I/S/M/E state, MSI 를 P1·P2 예시로 한 단계씩 구성.

1.3MESI(Illinois) 의 Exclusive 로 read-then-write 의 bus transaction 절감, snoopy 구현 비용(tag port, inclusive L2, bus 확장성, transient state).

1.4확장성을 위한 directory protocol: centralized vs distributed(home node), bit vector vs pointer, 2/4/3-hop read. p44~48 은 다음 강의.

상황·문제감기로 camera off 공지 후 복습. 단일 physical memory space 를 모든 CPU 가 공유하는 system 이 전제.

원인shared variable 값이 바뀌면 private cache 의 copy 가 old value 로 남을 수 있다.

해결cache coherence protocol 이 coherence state 와 processor·bus request 에 따른 transition 을 정의해 up-to-date 값을 보장.

상황·문제coherence 를 보장하는 가장 단순한 방법들부터 검토.

원인#1 shared variable 을 cache 안 함 → 성능 나쁨. #2 모든 copy 를 항상 같은 값으로 → store 마다 bus message, store 는 빈번.

해결#3 위치당 copy 하나 → bus traffic 은 적지만 shared read-only 변수도 여러 cache 에 못 둠(매번 invalidate 후 전달).

상황·문제강사가 mute 된 상태로 약 2분 진행되어 음성 없음. 428초에 p7 부터 다시 설명.

상황·문제#2 방식: line 은 Valid/Invalid, write-through + write-no-allocate. write 마다 memory 로 write transaction.

원인bus 는 모든 processor 가 snoop 가능 → 남의 write transaction 이 자기 cached line 과 맞으면 처리. evict 시 write-back 불필요.

해결대가: bus traffic 과 tag bandwidth 폭증(write 마다 tag check). snoop 한 write 를 (1) overwrite → write-update, (2) invalidate → valid-invalid protocol.

상황·문제P1·P2 가 A 를 Valid 로 cache(값 0), memory 도 0.

원인P1 Store A=1 → BusWr A=1 이 bus 로 전달되고 memory 가 1 로 update.

해결write-update: P2 copy 도 1 로 update. valid-invalid: P2 copy 는 invalidate. 둘 다 line 별 간단한 state machine 으로 구현.

상황·문제VI protocol 을 Valid/Invalid 두 state 의 transition diagram 으로 정리.

원인Load miss 는 BusRd 후 Valid, data 는 memory 또는 다른 cache 에서(cache 가 DRAM 보다 빠름). Valid 에서 Load 는 bus message 없음, Store 는 BusWr.

해결남의 BusWr 관찰 시 Invalid. Invalid 에서 Store 는 write-no-allocate 라 BusWr 만 보내고 Invalid 유지. overhead 는 기존 valid bit 1개뿐.

상황·문제VI 는 모든 write 를 broadcast 해 bus traffic 과 memory access 가 과다.

원인write-back cache 로 update 를 자기 cache 에 보관, read·write miss 에만 read transaction, evict 때만 memory 로 write-back. line 은 Modified/Invalid.

해결남의 read transaction snoop 시 자기 값으로 응답하고 Invalid(또는 retry 요청 후 memory 에 write-back). 퀴즈: 남의 write-back 은 snoop 불필요 — 그 line 을 안 가지고 있으므로.

상황·문제#3 을 state diagram 으로: Modified 또는 Invalid.

원인Invalid 에서 Load·Store → BusRd, 응답 받고 Modified. Modified 에서 Load·Store 는 bus message 없음(write-back).

해결남의 BusRd 관찰 시 data 보내고 Invalid. overhead 1bit. 단 one reader·one writer 라 read-only data 에 성능 저하.

상황·문제write-through 없이 read-only data 의 multiple copies 를 허용하고 싶다.

원인mutually exclusive(owner 가 유일 copy, 자유롭게 update) 와 shared(여러 reader, write 하려면 ownership 필요) 를 구분. read miss 시 owner 찾기, evict 시 memory update 필요.

해결bus snooping + intervention(남 대신 응답, retry 요청). line 마다 I/S/M/E 기록. 퀴즈: E→M 은 message 없이, S→M 은 invalidation 필요.

상황·문제MSI 와 MESI 는 이름대로 허용 state 가 다르고, MESI 는 E 를 추가로 지원.

원인single-writer/multi-reader 에 효율적: read-only copy 여러 개(S), writable copy 하나(E 또는 M). write-through 계열보다 bus transaction 크게 감소.

해결read miss → read transaction, write miss → read-with-intent-to-modify, S 에 write hit → invalidate transaction. E evict 는 조치 없음, M evict 는 dirty 값 write-back.

상황·문제MSI: Invalid, Shared(read-only·clean), Modified(dirty·유일). processor action 3개(Load, Store, Evict), bus message 5개(BusRd, BusRdX, BusInv, BusWB, BusReply).

원인P1 Load → BusRd·BusReply 로 S. P2 Load 시 S 인 cache 가 [BusReply](한 곳만 응답). P2 Evict 는 clean 이라 조치 없음. P2 Store(I) → BusRdX, P1 은 I.

해결P1 Load 시 M 인 P2 가 BusReply 후 S(memory 도 1). P1 Store(S) → BusInv 로 upgrade. P2 Store(I) → BusRdX, P1 M→I. P2 Evict(M) → BusWB. CPU/bus signal 별 diagram 두 개로 분리 가능.

상황·문제MSI 는 read 후 write(예: A[i]++ 의 load→add→store)가 잦을 때 BusRd(→S) 후 BusInv/BusRdX/BusUpgr(S→M) 두 transaction.

원인혼자만 쓰는 data 여도 ack 를 기다려 latency 증가, 불필요한 message. uniprocessor 에는 없는 multiprocessor 고유 overhead.

해결Exclusive(유일·clean) 추가: reply 가 memory 에서 오면 E, 다른 cache 에서 오면 S. E 에서 store 는 조용히 M. E 는 BusRd→S, BusRdX→I(BusReply), evict 는 write-back 없음.

상황·문제bus snoop 마다 cache tag lookup → 추가 tag port(응답용 data port 도) 필요, cache 비용 증가.

원인inclusive L2 면 L2 만 snoop 하면 됨(exclusive 면 L1 도 port 필요). bus 는 긴 wire 로 clock 이 느려지고 processor 가 늘면 bandwidth 분할.

해결MSI/MESI transition 은 atomic 아님: S→M 은 BusInv 후 ack 대기 transient state(SM), I→M 도 IM 거침. 대기 중 남의 BusRdX 가 오면 포기 또는 NACK → state 추가, 검증 복잡. consistency 와도 얽힘.

상황·문제bus 는 bandwidth 가 부족하고, point-to-point 로 바꿔도 모든 message 를 broadcast 하면 확장 불가(예: 100 processor 에 매번 100 message).

원인대부분의 snoop 은 아무 action 도 없다 → broadcast 자체가 낭비.

해결(I) bus 를 point-to-point network 로 교체 (II) directory 가 line 마다 owner(M/E) 또는 sharer(S, processor 당 1bit) 를 기록, message 는 directory 로 보내고 필요한 processor 에만 전달.

상황·문제directory 구현 방식: centralized vs distributed.

원인centralized 는 단일 serialization point 라 ordering(memory consistency) 확보가 쉽다.

해결대신 1000 node 의 message 가 한 곳에 몰려 bottleneck, 크기도 커짐. 예: Node#1 Read A → A: Shared,#1 → Fill A. Node#2 ReadExclusive A → Node#1 Invalidate, Inv Ack 후 Fill A, A: Mod.,#2.

상황·문제node 마다 processor·cache·directory·memory·controller. 주소 영역별 home node 가 그 line 의 directory 정보를 관리.

원인확장성은 좋지만 모든 address 의 access 를 serialize 할 수 없어 ordering 보장이 CPU interface 책임. 1000 CPU 면 bit vector 가 line 마다 1000bit → overhead 막대.

해결bit vector 는 소규모(예 8 CPU) 에 적합. 대규모는 pointer 기반: sharer ID 만 기록(예 CPU 9, 6). 슬롯 초과 시(CPU 3 추가) 기존 copy 하나 invalidate → 추가 message.

상황·문제L(transaction 시작), H(address 의 memory·directory 보유), R(참여하는 그 밖의 node).

원인home memory 에 있으면 L→H Read Req, H→L Read Reply, sharer=L, state S (강사: 초기 state 는 S 가 아니라 Invalid 여야 함). R 이 M 이면 H 가 R 에 Recall → 4 hop, latency 큼.

해결3-hop: H 가 R 에 read 를 forward, R 이 L 에 data 직접 전달 + H 에 Fwd'd Read Ack. 결과 state S, sharer L·R.

상황·문제다음 강의에서 이어감. 채팅으로 출석 확인, 질문 없어 종료(화면은 p44).

write 를 bus 로 보내 다른 cache 의 copy 와 memory 를 모두 새 값으로 update. write-through 기반.

snoop 한 write 가 자기 cached line 이면 copy 를 invalidate. read 는 여러 copy, write 는 불가.

write miss 때 line 을 가져오지 않고 memory 에만 write. VI 에서 Invalid 의 Store 가 Invalid 유지.

모든 cache 가 broadcast medium 인 bus 의 transaction 을 관찰해 자기 line state 를 갱신.

write-back 기반 one copy protocol. 남의 BusRd 에 data 주고 Invalid. one reader·one writer.

Modified·Shared·Invalid 3 state. S 는 read-only 여러 copy, M 은 dirty 유일 copy.

유일·clean copy. E→M 은 message 없이, evict 시 write-back 불필요.

MSI + E. read reply 가 memory 에서 오면 E, cache 에서 오면 S.

write miss 시 data 요청 + 다른 copy invalidate 를 함께 요구하는 message.

S 에서 store 할 때 다른 sharer 를 invalidate 하고 S→M.

message 보낸 뒤 ack·reply 를 기다리는 중간 state(SM, IM 등). transition 이 atomic 이 아니라 필요.

L2 가 L1 을 포함하면 bus snoop 은 L2 만 확인해 L1 bandwidth 와 경쟁 안 함.

line 마다 owner·sharer 를 기록한 directory 를 거쳐 필요한 node 에만 message. broadcast 제거.

distributed directory 에서 그 address 의 memory 와 directory entry 를 가진 node.

bit vector 는 N CPU 에 N bit, pointer 는 sharer ID 만 기록(개수 제한).

remote M copy 읽기: H 가 recall 하면 4 hop, R 로 forward 하면 R→L 직접 전달로 3 hop.

4.1write-update 와 valid-invalid protocol 은 snoop 한 write 를 어떻게 처리하나?

4.2Modified-Invalid protocol 에서 남의 write-back transaction 을 snoop 할 필요가 없는 이유는?

4.3S→M 과 E→M transition 의 차이는?

4.4MSI 에서 M 상태의 P2 가 P1 의 BusRd 를 보면?

4.5MESI 에서 Invalid 의 read miss 후 E 와 S 는 어떻게 가르나?

4.6snooping 을 directory 로 바꾸는 이유와 대가는?

4.74-hop read 를 3-hop 으로 줄이는 방법은?