Parallel Programming 6

Cache Coherence

• Write-through : CPU가 데이터를 사용하면 캐시에 저장되게 되는데, 데이터가 캐시 됨과 동시에 memory의 데이터도 업데이트하는 구조
  • Data consistency 유지하기 쉬움
  • 성능이 떨어짐
• Write back : 캐시 내에 일시적으로 저장된 후에 블록 단위의 캐시로부터 해제되는 때에만 memory에 기록
  • write-through 보다 속도가 빠름
  • cache와 memory 간에 데이터가 다른 경우가 발생

Cache Coherence 가 발생하는 이유 : 각 Processor가 각각의 Cache공간을 가지고 있을 때

Shared cache

• One single cache shared by all processors

But shared cache becomes bottleneck

 

Private cache

Add per-core caches

• Reduces latency
• Increases throughput
• Decrease energy

발생 가능한 문제점

A 값을 Shared Cache에서 찾으면 제대로 update가 되어있지 않다

Hardware-based solutions

• Directory-based coherence implementations
• Snooping-based coherence implementations

 

MI(VI) coherence protocol

Simplest form is a two-state “valid/invalid” protocol

If a core wants a copy, must find and “invalidate” it

현재 프로세서에서 invalid한 값을 읽거나 쓰려고 할 때 : valid로 변경됨

현재 프로세서에서 invalid할 때는 다른 프로세서에서 read/write miss가 발생해도 해줄 수 있는게 없음

현재 프로세서에서 valid할때 다른 프로세서에서 값을 read/write하면 현재 상태를 invalid로 바꾸고 send data

On a cache miss, how is the valid copy found?

• Snooping : broadcast to all, whoever has it responds
• Directory : track shares with separate structure

 

MSI coherence protocol

Modified, Shared, Invalid

현재 프로세서가 invalid한 상태에서 읽으려고 할 때 : 다른 프로세서에서 값을 가져와서 공유 상태가 됨

현재 프로세서가 invalid한 상태에서 쓰려고 할 때 : Modified 상태로 변경

 

MESI coherence protocol

MSI protocol에서는 load를 할 때 load miss가 발생하고 다시 동일한 값을 변경하려고 할 때 모든 프로세서에게 broadcast가 되는데, 다른 프로세서에서 가지고 있지 않아도 발생한다.

현재 프로세서가 invalid한 상태에서 읽으려고 할 때 : 공유하고 있다면 Shared, 아니라면 Exclusive

현재 프로세서에서 write miss, write hit가 발생하면 Modified상태로 바뀌는 이유 : 나중에 writeback을 해주기 위해

 

• Snooping/broadcast-based cache coherence : 적은 수의 프로세서에서 사용하기에 적합함. 작은 latency, 하지만 directory 방식에 비해 traffic이 크다
  • No explicit state
  • 2 hops (P0->memory->P0)
• Directory-based cache coherence
  • Track sharers of blocks
  • 3 hops (P0->momory->P1->P0)