cache coherence protocol mesi

**Cache Coherence Protocols** are **the hardware mechanisms that maintain a consistent view of shared memory across multiple processor cores with private caches — ensuring that when one core modifies a cache line, all other copies are either invalidated or updated so that no core reads stale data**. **MESI Protocol:** - **Modified (M)**: cache line is dirty (modified) and exclusively owned — only this cache has the current valid copy; must write back to memory before another cache can read it - **Exclusive (E)**: cache line is clean but exclusively owned — no other cache has a copy; can transition to Modified on write without bus transaction - **Shared (S)**: cache line is clean and potentially held by multiple caches — write requires invalidation of all other copies (transition to M) via bus broadcast or directory notification - **Invalid (I)**: cache line is not valid — read miss triggers cache fill from memory or another cache; write miss triggers cache fill and invalidation of other copies **Snooping vs. Directory Protocols:** - **Snooping (Bus-Based)**: all caches monitor a shared bus for coherence transactions — each cache controller snoops address bus and responds if it holds a matching line; scales to 4-16 cores but limited by bus bandwidth - **Directory-Based**: centralized or distributed directory tracks which caches hold each line — point-to-point messages replace broadcast; scales to hundreds of cores but adds directory storage overhead (1-2 bits per cache line per core) - **Hybrid Protocols**: snooping within a cluster (4-8 cores sharing L3) and directory between clusters — combines low-latency local coherence with scalable inter-cluster protocol - **MOESI Extension**: adds Owned (O) state where one cache holds dirty data shared with other clean copies — avoids write-back to memory when sharing modified data, reducing memory controller load **Performance Implications:** - **False Sharing**: when two cores access different variables that reside on the same cache line — writes by one core invalidate the other's copy, causing repeated cache misses despite no true data sharing; solutions include padding structures to cache line boundaries - **Coherence Traffic**: heavy sharing creates invalidation storms — hot locks, counters, and shared queues generate disproportionate coherence traffic; per-core private counters with periodic aggregation reduces traffic - **Coherence Latency**: local cache hit: 1-4 cycles; L3 hit: 10-30 cycles; remote cache (snoop): 50-100 cycles; memory (directory miss): 100-300 cycles — coherence miss penalty dominates performance of sharing-intensive applications - **Protocol Overhead**: directory storage for 1024-core system with 64-byte lines and 32 MB L3 per core requires 128 KB of directory per core — full bit-vector directories become prohibitive at extreme scale, requiring coarse-grain or limited-pointer directories **Cache coherence protocols represent the invisible hardware infrastructure that makes shared-memory parallel programming possible — without coherence, every shared variable access would require explicit message passing, making multi-threaded programming as complex as distributed systems programming.**