Lec 20 · Cache Coherence: snoopy MSI·MESI·MOESI, false sharing, directory

1.1ca_L13 p1~44: multiprocessor memory hierarchy(SMP·NUMA)와 bus, coherence 정의(SWMR·Data-Value invariant)

1.2snoopy cache 와 MSI protocol 예제, inclusive L2 snooping, MESI(Exclusive)·MOESI(Owned)로 bus traffic·write back 절감

1.3coherence miss(4C), false vs true sharing 예제, 상용 workload 성능 데이터

1.4snoopy 의 scalability 한계와 directory protocol(home·local·remote node, cache·directory state, read/write miss 흐름). p45~52 는 시간 부족으로 다음 강의로

상황·문제coherence 는 processor 가 여럿일 때만 생기는 문제. multiprocessor memory hierarchy 를 어떻게 구성하는가

원인processor 마다 전용 cache 를 두면 같은 data 의 복사본이 여러 cache 에 생긴다

해결SMP 는 bus/interconnect 뒤 단일 memory(모두 같은 latency), NUMA(distributed shared memory)는 node 별 local memory. 어느 쪽이든 cache 들이 최신 복사본을 보도록 통신이 필요

상황·문제cache 간 통신의 가장 단순한 수단인 bus 를 snoopy protocol 의 전제로 둔다

원인bus 는 공유 wire 묶음이라 한 번에 한 master 만 구동할 수 있다

해결master 가 controller(arbiter)에 request, grant 받으면 전송. slave 는 address 를 decode 해 응답 여부 결정. bus 로 cache·memory·I/O 를 연결

상황·문제coherence 가 무엇인지 정의가 필요하다

원인같은 location 에 여러 core 가 read/write 하면 어떤 값을 봐야 하는지 불명확

해결A Primer on Memory Consistency and Cache Coherence 의 두 invariant 로 정의. 구현 요건은 write propagation 과 write serialization

상황·문제coherence 구현 방식은 크게 둘, 먼저 snooping

원인각 cache 가 다른 cache 의 bus transaction 을 알아야 올바르게 반응할 수 있다

해결참여하는 모든 cache 가 bus 의 모든 transaction 을 관찰하고 line state 에 따라 '올바른 일' 수행. processor 접근과 snoop 을 동시에 하려고 tag 를 dual-ported 로

상황·문제cache block 마다 어떤 state 를 두어 SWMR 을 지킬 것인가

원인write-back cache 에서 M 인 line 이 있으면 memory 는 stale data 를 가진다

해결I(복사본 없음)·S(read-only, clean, 다른 cache 에도 있을 수 있음)·M(writable, dirty, 유일한 복사본) 을 tag 의 2 bit 로. dirty 복사본을 가진 cache 가 BusRd 에 intervention 해 응답

상황·문제MSI 가 실제 access 순서에서 어떤 message 와 전이를 만드는지 단계별로 본다

원인state 에 따라 필요한 bus message 가 다르다 (S hit 는 message 없음, S→M 은 invalidate 필요)

해결load miss 는 BusRd, I 에서 store 는 BusRdX, S 에서 store 는 BusInv, M 이 BusRd 받으면 BusReply 후 S 가 되고 memory 갱신, M evict 는 BusWB

상황·문제snoop 이 L1 까지 매번 확인하면 processor 의 L1 접근을 방해한다

원인multi-level cache 에서 bus message 마다 어느 level 에 line 이 있는지 알아야 함

해결L2 를 L1 의 inclusive 로 두면 L2 tag 만 snoop: L2 miss 면 L1 에도 없음, L2 invalidation hit 일 때만 L1 probe·invalidate

상황·문제read 후 write(예: 메모리 값 increment)가 흔한데 MSI 는 S 로 가져온 뒤 BusInv 를 또 보낸다

원인MSI 는 자기만 복사본을 가진 private block 인지 알 수 없어 쓸모없는 invalidation 을 broadcast. uniprocessor 에는 없는 overhead

해결E(유일한 clean 복사본) 추가. BusRd 응답이 memory 에서 오면 E, cache 에서 오면 S. E 에서 write 는 message 없이 M 으로 silent upgrade

상황·문제MSI·MESI 에서 M→S 로 공유하면 dirty data 를 memory 에 write back 해야 한다

원인S 는 clean 을 보장해야 하는데, 곧 다른 cache 가 다시 수정할 수도 있어 비싼 memory update 가 낭비

해결O(owned) 추가: 최신·read-only 지만 dirty. 다른 cache 는 S 로 공유, BusRd 에는 owner 가 data 공급, owner 가 evict 할 때만 memory 에 write back

상황·문제Owned 추가 후 cache 쌍마다 어떤 state 조합이 가능하고 어떻게 전이하는가

원인M·E 는 유일한 복사본, O 는 S 들과만 공존해야 한다

해결compatibility matrix 로 조합 정리, processor action 만으로는 O 로 가지 않고 M 이 다른 cache 의 BusRd(probe read hit)를 받을 때 O 로 전이. valid·dirty·shared 3 bit 로 표현

상황·문제coherence protocol 이 invalidate 한 line 을 다시 접근하면 새 유형의 miss 가 생긴다

원인coherence 가 word 가 아닌 cache line 단위라, 다른 word 를 쓰는 processor 끼리도 line 이 ping-pong

해결compulsory·capacity·conflict 에 coherence miss 를 더해 4C. 실제 data 통신 때문인 true sharing 과 구분

상황·문제MSI, x1·x2 같은 line, P1·P2 모두 S 상태에서 5 개 access 의 miss 종류를 판정

원인판정 기준: 다른 processor 가 다른 word 에 접근하지 않았어도 이 miss 가 났을까

해결1 Write x1 true(S→M invalidate 는 피할 수 없음), 2 Read x2 false, 3 Write x1 false, 4 Write x2 true, 5 Read x2 true

상황·문제coherence miss 가 실제 workload(OLTP, decision support, search engine)에서 얼마나 중요한가

원인coherence miss 는 다른 processor 의 활동 때문에 생겨 cache size 에 거의 영향 받지 않는다

해결4-processor 에서 L3 1→8 MiB 로 키우면 uniprocessor miss 는 줄지만 true/false sharing 은 거의 그대로. 2 MiB 고정에 CPU 1→8 개면 sharing miss 증가

상황·문제snoopy 는 4개, 늘려도 8개 정도 processor 에서만 잘 동작. 64·1024 개면 비용이 너무 크다

원인모든 miss 가 broadcast 되어 bus bandwidth 와 tag snoop bandwidth 가 병목, 대부분 snoop 은 match 가 없음

해결interleaved bus·tag bank 는 부분 해결일 뿐. directory 가 line 별 복사본 위치·state 를 추적해 관련 node 에만 message, 대신 scalable network 필요

상황·문제directory 기반에서 miss 를 어떻게 처리하는가

원인주소마다 담당 directory controller(home)가 있고, 실제 복사본은 다른 node 에 있을 수 있다. 전이 중간 상태가 생긴다

해결miss 는 주소의 home directory 로 요청 → sharer bit vector 보고 필요한 node 에만 message. read miss 는 ShReq/ShRep, write miss 는 ExReq → sharer 에 InvReq → InvRep 모두 받으면 ExRep

node 마다 local memory, remote memory 는 거리만큼 latency 가 김

한 시점·한 location 에 writer 하나(읽기도 가능) 또는 reader 여럿만

epoch 시작 값 = 마지막 read-write epoch 끝의 값

같은 location 에 대한 write 들을 모든 processor 가 같은 순서로 본다

모든 cache 가 bus transaction 을 관찰하고 state 에 따라 반응, tag 는 dual-ported

dirty 복사본을 가진 cache 가 memory 대신 BusRd 에 응답해 stale data 를 막음

Invalid·Shared(clean, read-only)·Modified(dirty, 유일) 3 state

L1 항목이 모두 L2 에 있음 → L2 만 snoop, L2 miss 면 L1 에도 없음

유일한 clean 복사본, write 시 message 없이 M 으로 silent upgrade

최신·read-only·dirty, 다른 cache 는 S, owner 가 BusRd 응답과 evict 시 write back 책임

다른 processor 의 invalidation 때문에 생기는 miss, communication miss 라고도 함

같은 line 의 다른 word 를 쓰는 processor 끼리 line 이 ping-pong 하며 생기는 miss

processor 간 실제 data 통신 때문의 miss, line 이 1 word 여도 발생

line 별 state 와 sharer bit vector 를 두어 broadcast 대신 관련 node 에만 message

home 은 주소를 담당하는 memory·directory, local 은 요청자, remote 는 복사본 보유 node

요청을 보내고 응답을 기다리는 중간 state, 많을수록 protocol 구현·검증이 어려움

4.1SMP 와 NUMA 에서 memory latency 는 어떻게 다른가?

4.2snoopy cache 의 tag 가 dual-ported 여야 하는 이유는?

4.3MSI 에서 M 인 line 에 다른 cache 가 BusRd 를 보내면 무슨 일이 일어나는가?

4.4MESI 에서 BusRd 후 E 와 S 중 어디로 갈지 어떻게 정하나?

4.5Owned state 가 줄여 주는 비용은?

4.6MOESI 에서 어떤 state 가 valid·dirty·shared bit 를 모두 1 로 갖는가?

4.7false sharing miss 와 true sharing miss 를 가르는 기준은?

4.8snoopy 가 수십~수천 processor 로 확장되지 않는 두 병목은?

4.9directory 에서 shared line 에 write miss 가 나면 message 흐름은?