Cache Coherence Protocols

Cache Coherence Protocols

• There are two main cache coherence protocols: write invalidate and write update.
• Write invalidate protocol acts on cache blocks, while write update protocol acts on individual words.
• In write invalidate protocol, only the first write of any word within a block needs to generate an invalidation, and it tends to generate less traffic in the memory bus.

Write Invalidate Protocol

• It requires a block invalidation when a word is written in a cache block.
• The block invalidation is done by sending the block address through the bus, and the other processors snoop on the bus to invalidate the block.
• It relies on serialized writes, which are forced by the need to get access to the bus as an exclusive resource.
• In write through cache, all written data are always sent to the memory, ensuring the most recent value of a data item can always be fetched from memory.
• In write back cache, if a block is clean (shared), the protocol acts like the write through approach.

Write Invalidate Protocol Example

• A processor reads a memory location, causing a cache miss, and the data block is cached.
• Another processor reads the same memory location, also causing a cache miss, and the data is cached.
• When a processor writes to the memory location, the new data goes only to its cache, and an invalidation is communicated through the bus.
• When the other processor reads the memory location again, it notices the invalidation, and the data block is fetched from the first processor's cache instead of memory.

Write Update Protocol

• It updates all cached copies of a data item when that item is written.
• It must broadcast all writes to shared cache lines, which consumes more bandwidth than the write invalidate protocol.
• Most recent multiprocessors have opted to implement a write invalidate protocol.

Cache Coherence Protocol States

• A cache block can be in one of three states: invalid, shared, or modified (exclusive).
• The state changes from invalid to shared when the block is first read, and to exclusive when the block is first written.
• The state transitions are triggered by requests from the CPU or the bus.
• A finite-state machine controller is implemented in each core to manage the state transitions.

Multiple Instruction, Multiple Data (MIMD) Systems

• MIMD architecture is related to multiprocessors, where different instructions can work on different data in parallel.
• Multiprocessors are computers consisting of tightly coupled processors controlled by a single operating system, sharing memory through a shared address space.

Memory Organization

• Multiple processors can share:
  • Cache memory, main memory, and I/O system
  • Main memory and I/O system
  • I/O system
  • Nothing, communicating through networks
• Feasibility of options depends on project requirements and avoiding bottlenecks in architecture.

Symmetric (Shared-Memory) Multiprocessors - SMP

• SMP are centralized shared-memory multiprocessors with 32 cores or less, sharing a single centralized memory.
• Each processor has equal access to memory, with a uniform access time (UMA) to all memory.
• SMP can use large caches and many buses to avoid memory and bus bottlenecks.

Distributed Shared Memory - DSM

• DSM has a larger processor number (e.g., 16 to 64 cores), using distributed memory to increase bandwidth and reduce access latency.
• Communication among processors is more complex than SMP, requiring more effort in software to take advantage of increased memory bandwidth.
• DSM has nonuniform memory access (NUMA), with access time depending on the location of a data word in memory.

Distributed Shared Memory (DSM) Architecture

• Each processing node can be a multicore with its own memory and I/O system in a multiprocessor chip.
• A directory keeps the state of every block that may be cached, including which caches have copies, whether it is dirty, and the block status.
• The directory is distributed along with the memory, with each directory responsible for tracking caches that share memory addresses.

Cache Coherence in DSM

• The directory-based protocol uses message passing between nodes, rather than snooping on the bus.
• The protocol needs to know which node has the block to make the invalidation, keeping information on which processors have each memory block.

Multicomputers

• Multicomputers are processors with independent memories and address spaces, with no cache coherence problem.
• However, cache coherence problems still exist within each computer.

Thread-Level Parallelism

• Multithreading is increasingly used to exploit explicit parallelism, with threads controlled by the programmer.
• This is in contrast to Instruction-Level Parallelism (ILP), which is already well-explored and limited.