Parallel Processors and Cache Coherency in Shared Memory Systems

Parallel processors execute multiple instructions concurrently by using multiple processing elements (e.g., cores, CPUs, or specialized accelerators). In shared memory systems, all processors access a logically common address space, but each processor typically has private caches for performance. The tension is that caches can hold stale or conflicting copies of the same memory block, so the system must enforce cache coherency: a consistent rule for what value reads should observe after writes. This is the core of the cache coherency problem in shared memory multiprocessors.

A useful mental model is: processors may run in parallel, but memory appears “as if” operations are properly ordered according to the memory model, which the hardware must approximate using protocols and interconnect behavior.

Key concepts you’ll use repeatedly:

• parallel processor
• shared memory
• cache coherence
• cache line
• memory model

Why coherency is hard: consider two cores that both cache the same cache line. If core 1 writes to its cached copy without informing core 2 (or without the protocol ensuring invalidation/update), core 2 may later read an outdated value from its own cache—leading to incorrect behavior even though both cores “see” the same shared address space.

Important distinction: Cache coherence is about values and visibility across caches; correctness still also depends on the system’s memory model and how software uses synchronization.

Parallel processors: how they differ (and why coherency shows up)

Parallel processing can be organized at multiple levels:

1. Instruction/data parallelism (vector/SIMD): a single instruction stream operates on many data elements. Coherency issues are usually less about multiple writers to the same address and more about memory bandwidth and alignment.
2. Multiple-instruction, multiple-data (MIMD): different cores run different instruction streams on different data. Coherency becomes central when cores can read/write overlapping memory regions in shared memory.
3. Shared-memory MIMD multiprocessors: each core has caches; all cores communicate via shared interconnect and memory. Coherency protocols coordinate cache states and interconnect transactions.

Common shared-memory hardware mechanisms:

• Snooping (bus-based): caches “snoop” transactions on a broadcast interconnect; when a write occurs, other caches can invalidate/update their copies.
• Directory-based coherence: a centralized (or distributed) directory tracks which caches hold copies of each cache line and directs invalidations/updates.

Key terms:

• snooping
• directory-based coherence
• invalidation
• update protocol
• shared cache state

The cache coherency problem in more detail

Assume:

• Each cache contains a copy of some cache lines.
• A cache line can be in one of several coherence states (exact set depends on protocol).
• Reads/writes are served by caches when possible.
• Without coordination, multiple caches may diverge.

A canonical scenario (no coherence):

1. Core 1 reads address $X$ → loads cache line containing $X$ into its cache.
2. Core 2 reads address $X$ → also loads the same cache line into its cache.
3. Core 1 writes to $X$ (modifies its cached line).
4. Core 2 later reads $X$ → still has the old cached line, returns stale value.

Coherence protocols prevent this by enforcing invariants such as:

• Before a core reads a line, the protocol ensures it has a valid copy according to the protocol rules.
• Before a core writes a line, the protocol ensures no other cache has a conflicting usable copy (or updates them).

Cost model: coherency requires extra control traffic (invalidation/update messages), possible stalls, and serialization effects on the interconnect.

Coherence protocols and states (MESI family overview)

Many practical systems use state-machine protocols (e.g., MSI/MESI/MOESI). They treat each cache line as being in a state that describes:

• whether the line is valid,
• whether it is shared with others,
• whether it is owned exclusively and can be modified,
• and (in some protocols) whether another cache may have a copy.

In an MESI-like family:

• Modified (M): cache line is dirty (changed) and unique to that cache.
• Exclusive (E): cache line is clean and unique (not shared) to that cache.
• Shared (S): cache line may exist in multiple caches and matches memory.
• Invalid (I): cache line is not valid for use.

These states exist because “what actions are allowed” depends on whether other caches may also hold the line.

Key terms:

• MESI
• cache line invalid
• dirty cache line
• downgrade