Cache Coherence Protocols in Parallel Processors

Each core has private cache -> need protocol to keep copies of same block coherent.

Classification

1. Snoopy vs Directory

   • Snoopy (bus-based): All caches snoop bus. Good for small UMA (<=32 cores).
   • Directory: Memory holds directory of sharers. Point-to-point messages, scalable to many cores (NUMA).

2. Write-Invalidate vs Write-Update

   • Invalidate: Write invalidates other copies (traffic low, widely used).
   • Update: Write broadcasts new value (high traffic, rarely used).

Main Invalidate Protocols (FSM per cache line)

a) MSI (Modified-Shared-Invalid) - 3 state

• M: Dirty, exclusive
• S: Clean, may be shared
• I: Invalid
  Actions: Read miss -> BusRd, Write hit on S -> BusUpgr/Invalidate, Write miss -> BusRdX.

b) MESI (Illinois/MESI) - 4 state - Most common (Intel)
Adds E (Exclusive-clean): Only copy, clean -> write without bus transaction.
States: M(Modified dirty), E(Exclusive), S(Shared), I.
Benefit: Reduces bus traffic for private data.
Transitions: Read miss - if no other cache -> E else S; Write on E -> M silently; Write on S -> invalidate others -> M.

c) MOESI (AMD Opteron) - 5 state
Adds O (Owned): Dirty but shared - Owner supplies data on miss, memory stale. Allows sharing of dirty block without writeback.
States: M-O-E-S-I. Reduces memory writebacks.

d) MESIF (Intel Nehalem) - 5 state
Adds F (Forward): Designated sharer to respond to misses, instead of broadcast from all S. Reduces snoop response contention.

e) Dragon (Write-update) and Firefly

How it works - Example MESI

P1 reads x (miss) -> BusRd, memory supplies -> E in P1
P2 reads x -> P1 snoops BusRd, both move E->S, memory still clean
P1 writes x -> issues Invalidate, S->M in P1, I in P2, P1 modifies locally
P2 reads again -> P1 intercepts (Cache-to-Cache transfer), P1 M->O/S and writes back.

Directory Protocol (for large scale)

Memory entry: | State | Sharer bit-vector |
Read miss -> directory adds requester to set; Write miss -> sends Invalidate to sharers via point-to-point, waits for ACK, then grants exclusive.

Tradeoffs: Snoopy simple but bus is bottleneck; Directory scalable but 2-3 hop latency + storage overhead.