Cache Coherence

Write Propagation is the guarantee that a write operation to a shared memory location by one processor will eventually become visible to all other processors. This is the fundamental requirement that prevents different cores from operating on stale data. Without this property, a processor could compute using an outdated value, leading to incorrect results.

• Mechanism: Achieved through protocols that broadcast write notifications (snooping) or track ownership (directory-based).
• Eventual Consistency: The write may not be instantly visible globally, but the system guarantees it will propagate, typically on the next coherence transaction for that address.

Write Serialization ensures that all processors observe writes to the same memory location in the same sequential order. This property is critical for establishing a global timeline of modifications, which is necessary for implementing synchronization primitives like locks and barriers.

• Global Order: If two processors, P1 and P2, write to address X, all other processors must agree on whether P1's write happened before P2's or vice-versa.
• Foundation for Synchronization: This atomic ordering is what allows a test-and-set or compare-and-swap instruction to function correctly across multiple caches.

Cache lines are tracked using finite coherence states that define permissions and data freshness. The most common protocol is MESI (Modified, Exclusive, Shared, Invalid). An extension is MOESI, which adds an Owned state.

• Modified (M): The cache line is dirty (modified) and is the only valid copy; must write back to memory before eviction.
• Exclusive (E): The cache line is clean and is the only cached copy.
• Shared (S): The cache line is clean and may be present in other caches.
• Invalid (I): The cache line data is stale and cannot be used.
• Owned (O) in MOESI: The cache line is dirty and responsible for supplying data to other caches, but does not have to write back immediately.

These are the two primary architectural approaches to implementing coherence.

• Snooping (Bus-Based): All caches monitor (snoop) a shared broadcast interconnect (bus or network) for transactions. When a write is seen, caches invalidate or update their local copies. Simple but does not scale well to many cores due to broadcast traffic.
• Directory-Based: A centralized or distributed directory tracks which caches hold copies of each memory block. On a write, only the caches listed in the directory are notified. This is scalable for large multi-processor systems (e.g., 64+ cores) as it uses point-to-point messages instead of broadcasts.

These are distinct but related concepts often conflated.

• Cache Coherence: Defines the behavior of reads and writes to a single memory location. It answers: "When will a write by one core be seen by a read from another core for the same address?"
• Memory Consistency: Defines the legal ordering of reads and writes to different memory locations across multiple processors. It answers: "Can a read of location Y see a new value before a read of location X sees its new value, even if X was written first?"
• Relationship: Coherence is a necessary precondition for most useful consistency models (like Sequential Consistency). A system can be coherent but have a weak (relaxed) consistency model.

Maintaining coherence between a host CPU and a dedicated accelerator like an NPU presents unique challenges. The goal is to allow both processors to work on the same data without explicit, software-managed cache flushes.

• Hardware-Managed Coherence: Modern interconnects like CXL (Compute Express Link) and some proprietary NPU links support hardware cache coherence between the device and the CPU. The NPU's caches participate in the system's coherence domain.
• Software-Managed Coherence: In many systems, the NPU operates in a separate, non-coherent memory space. The programmer must use explicit DMA transfers or CPU cache management instructions (e.g., flush, invalidate) to move data, which adds complexity and latency.
• Unified Virtual Memory: Frameworks like CUDA provide a unified address space, but true hardware coherence is often limited to specific GPU architectures and memory types.

In a system with multiple processing cores, each with its own cache, a fundamental problem arises: multiple copies of the same data can exist. If Core A writes a new value to its local cache, Core B may still be reading the old, stale value from its own cache. Cache coherence protocols are the hardware mechanisms that solve this by ensuring all caches see a single, up-to-date view of memory. Without it, parallel programs would produce non-deterministic and incorrect results.

These are the standard hardware protocols that track cache line states to manage coherence traffic efficiently.

• MESI: Defines four states: Modified (dirty, exclusive), Exclusive (clean, exclusive), Shared (clean, possibly in other caches), Invalid. It's the foundation for most CPU coherence.
• MOESI: Adds an Owned state to MESI. A cache line in Owned state is responsible for supplying data to other caches, reducing write-back traffic to main memory. This is common in AMD processors and many accelerator interconnects.

These protocols work by broadcasting snoop requests or using directory-based schemes to track which caches have copies of data.

AI accelerators (NPUs, GPUs) introduce unique coherence challenges:

• Heterogeneous Systems: The NPU is a separate device with its own memory hierarchy, often connected via a bus (e.g., PCIe, CXL). Maintaining coherence between the host CPU's caches and the NPU's caches is complex.
• Massive Parallelism: Thousands of simple cores accessing memory simultaneously generate enormous potential for coherence traffic, which can become a performance bottleneck.
• Scratchpad vs. Cache: Many NPUs use software-managed scratchpad memory (SRAM) instead of hardware caches. While this avoids coherence issues for that local memory, data moved between scratchpad and globally shared DRAM still requires coherence management.

These are the two primary architectural approaches to implementing coherence.

• Snooping (Broadcast): Every cache controller monitors (snoops) a shared bus for transactions. If a transaction is for an address it holds, it takes appropriate action (e.g., invalidates its copy). Simple but doesn't scale well to many cores due to bus bandwidth limits.
• Directory-Based: A central directory keeps track of which caches have copies of each memory block. On a write, only the caches listed in the directory are sent invalidation messages. This scales better for large many-core and heterogeneous systems (like CPU+NPU) but adds latency for directory lookups.

Modern interconnects are designed with accelerator coherence in mind.

• Compute Express Link (CXL): An open standard that maintains memory coherence between the CPU and devices like NPUs, GPUs, and memory expanders over a PCIe physical layer. CXL.io provides I/O semantics, CXL.cache allows the device to cache host memory coherently, and CXL.mem allows the host to access device memory.
• CCIX: A similar cache-coherent interconnect standard for accelerators. These protocols allow the NPU to access the CPU's memory directly and coherently, simplifying programming by enabling a unified memory address space without explicit software-managed data synchronization.

Understanding hardware coherence is essential for writing efficient code.

• False Sharing: A major performance pitfall. Occurs when unrelated variables used by different cores reside on the same cache line. Writes by one core cause the entire line to be invalidated for others, generating useless coherence traffic. Mitigated by memory alignment and padding.
• Memory Barriers/Fences: Instructions that enforce ordering of memory operations. Crucial when coherence and consistency are managed separately. They ensure that results of writes are visible to other cores in the required order.
• Explicit Synchronization: Using atomic operations (like compare-and-swap) or locks, which rely on the underlying coherence protocol to ensure safe concurrent access to shared data.

A memory consistency model defines the legal ordering of memory operations (loads and stores) in a parallel system, specifying the possible values a read can return. It provides the formal rules that hardware guarantees to software. Cache coherence is a necessary but insufficient condition for strong consistency; a coherent system can still exhibit relaxed consistency behaviors (e.g., weak ordering).

• Sequential Consistency: The intuitive model where all operations appear to execute in a single total order.
• Release/Acquire Consistency: A weaker model that provides synchronization only at specific fence operations.
• Importance: The chosen model dictates the complexity of hardware and the burden on programmers to insert explicit memory barriers.

A memory barrier (or memory fence) is a type of CPU/accelerator instruction that enforces ordering constraints on memory operations issued before and after the barrier. It is the primary software mechanism to control visibility and enforce a specific memory consistency model in a cache-coherent system.

• Function: Prevents the compiler and hardware from reordering loads/stores across the barrier point.
• Use Case: Crucial for implementing locks, semaphores, and other synchronization primitives. On an NPU, barriers ensure that tensor data produced by one kernel is fully visible to a subsequent kernel before it begins execution.
• Types: Include read barriers, write barriers, and full barriers, each controlling specific types of reordering.

False sharing is a performance degradation issue in cache-coherent multi-core systems. It occurs when threads on different processors frequently write to different variables that happen to reside on the same cache line. The coherence protocol, operating at cache-line granularity, cannot distinguish the independent variables and treats each write as a modification of the shared line, triggering unnecessary invalidation and coherence traffic.

• Impact: Severe performance penalty due to cache line 'ping-ponging' between cores, even though no logical data is actually shared.
• Mitigation: Data structure padding, thread-local storage, or careful alignment to ensure independently accessed variables reside on separate cache lines.

Non-Uniform Memory Access (NUMA) is a multiprocessor architecture where memory access time depends on the memory location's proximity to the requesting processor. Each processor has a local memory bank with low latency; accessing remote memory (attached to another processor) incurs higher latency. Cache coherence protocols in NUMA systems (e.g., AMD's Infinity Fabric, Intel's QPI) must manage this physical non-uniformity.

• Contrast with UMA: In Uniform Memory Access, all processors share a central memory bus with equal latency.
• NPU Context: Large-scale AI systems with multiple NPU sockets or NPUs connected via CXL/interposer often exhibit NUMA characteristics. Optimizing data placement is critical for performance.

An atomic operation is an instruction or sequence that executes as a single, indivisible unit relative to other operations on the same memory location. In a cache-coherent system, the hardware (often the cache controller) guarantees that no other processor can observe an intermediate state of an atomic read-modify-write (e.g., compare-and-swap, fetch-and-add).

• Foundation for Locks: Atomic operations are the building blocks for high-level synchronization primitives like mutexes and spinlocks.
• Hardware Support: Modern NPUs and CPUs provide a set of atomic intrinsics (e.g., for 32-bit or 64-bit integers) that leverage the coherence protocol to ensure serialization across cores.
• Contrast with Non-Atomic: A non-atomic multi-step update (like a 128-bit write on a 64-bit bus) could be torn, allowing other threads to see a partially updated, inconsistent value.

These are the two primary architectural approaches to implementing a cache coherence protocol.

• Snooping Protocol: Every cache controller 'snoops' (monitors) a shared broadcast bus for transactions from other processors. If it sees a request for a line it holds, it responds accordingly. Simpler but less scalable due to bus bandwidth limits.
• Directory-Based Protocol: A centralized or distributed directory tracks which caches hold copies of each memory line. On a request, the directory is consulted and only the relevant caches are contacted. More scalable for many-core processors and NPU clusters, as it uses point-to-point messages instead of broadcast.
• NPU Relevance: High-core-count NPUs and multi-NPU systems almost exclusively use directory-based protocols (e.g., with a directory in the last-level cache or memory controller) to manage coherence traffic efficiently.