Multicore processors, cache coherence and memory consistency

When single-core performance stopped growing quickly in the mid-2000s, the industry turned to putting several cores on one chip. A multicore processor offers more throughput for the same power, provided software can split its work into threads that run in parallel. That proviso hides most of the difficulty. The cores share memory, and each has its own caches, so the hardware must make sure every core sees a sensible view of shared data, and programmers must understand exactly what that view guarantees. This lesson covers the hardware that keeps caches coherent, the rules that define memory consistency, and the performance traps that appear when threads share data.

Dana's aggregation servers have 32 cores each, and the nightly job that tallies vehicle counts by class and hour was rewritten last year to use one thread per core. It runs only about nine times faster than the old single-threaded version instead of the hoped-for thirty. Jonah is asked to find out why, and the answer turns out to be in the cache coherence protocol. Meanwhile Maren is weighing whether the NS-5 should use a dual-core cluster, with one core for radio and networking and one for the classifier.

Thread-level parallelism and its limits

Multicore processors exploit thread-level parallelism: independent instruction streams, each with its own program counter and registers, running at the same time. Amdahl's law from lesson 1 applies with a vengeance. If a fraction P of the work can run in parallel on N cores and the rest is serial, the speedup is at most 1 / ((1 − P) + P / N). With 95 percent parallel work, 32 cores give at most about 12.5 times; the serial 5 percent dominates. Real programs also pay for communication and synchronization between threads, and for contention when threads compete for shared caches, memory bandwidth or locks, so measured speedups usually fall short of the Amdahl bound.

Gustafson's observation offers a more hopeful view for some workloads: when more cores are available, people often process larger problems in the same time, and the parallel part grows with the problem while the serial part stays fixed. Dana's job has this character, since a larger fleet means more records but the same handful of serial steps, so adding cores will keep helping as Northway grows, provided the parallel part scales cleanly.

Multithreading within a core

Threads can also share a single core. Fine-grained multithreading switches between threads every cycle, hiding stalls of one thread behind instructions from others; it suits throughput-oriented processors with many simple cores. Simultaneous multithreading, SMT, lets a wide out-of-order core issue instructions from two or more threads in the same cycle, filling issue slots that one thread's dependences would leave empty. SMT typically adds tens of percent of throughput for a small increase in area, though threads on the same core compete for its caches and predictors, which can slow each one and, as noted in lesson 4, can leak information between them.

The cache coherence problem

Suppose core 0 and core 1 both read a variable x into their private caches, and then core 0 writes x. If nothing else happens, core 1 continues to read its stale copy. A memory system is coherent if every read returns the most recent write to that location, in an order all cores agree on. More precisely, coherence requires that writes to the same location are serialized, so all cores see them in the same order, and that a write eventually becomes visible to every core. Coherence is about a single location; ordering among different locations is the separate subject of consistency.

Hardware maintains coherence by tracking the state of each cached block. In a snooping protocol, every cache watches, or snoops, a shared bus or broadcast network on which all misses and invalidations appear. In a directory protocol, a directory, usually distributed alongside the last-level cache or memory, records which caches hold each block and sends messages only to those caches. Snooping is simple and fast for a few cores; directories scale to dozens or hundreds of cores because they avoid broadcasting every request.

The MESI protocol

Most coherence protocols are write-invalidate: before a core writes a block, it obtains exclusive ownership by invalidating every other copy. The widely used MESI protocol gives each cached block one of four states. Modified means this cache holds the only copy and it is dirty, differing from memory. Exclusive means this cache holds the only copy and it is clean. Shared means this and possibly other caches hold clean copies. Invalid means the block is not present. A read miss fetches the block in Exclusive if no other cache has it, or Shared if another does; if another cache holds it Modified, that cache supplies the data and both end in Shared. A write to a Shared block broadcasts an upgrade that invalidates other copies, and a write to an Exclusive block becomes Modified silently, without any bus traffic, which is the point of the Exclusive state: private data that is read and then written costs only one bus transaction.

False sharing

Coherence works on whole blocks, not on individual words. If two cores repeatedly write different variables that happen to lie in the same cache block, each write invalidates the other core's copy, and the block bounces between the caches even though the cores never touch the same data. This false sharing produces a stream of coherence misses that looks, in performance counters, like heavy communication. The fix is to separate the variables by padding or alignment so that each lives in its own block, or to restructure the code so each thread accumulates in a private variable and combines results at the end.

Dana's tally job keeps one counter per thread in an array, each 4 bytes, so sixteen threads' counters share each 64-byte block. Jonah models two cores incrementing their own counters a thousand times each, once with the counters adjacent and once padded to separate blocks.

# MESI snooping coherence for two cores, counting bus transactions
def run(trace, block=64):
    state = [{}, {}]                     # per core: block -> 'M', 'E', 'S' (absent = I)
    bus = {"read": 0, "read-exclusive": 0, "upgrade": 0, "writeback": 0}
    for core, op, addr in trace:
        b, me, other = addr // block, state[core], state[1 - core]
        s = me.get(b, "I")
        if op == "R":
            if s == "I":
                bus["read"] += 1
                if other.get(b) == "M": bus["writeback"] += 1
                shared = b in other
                if shared: other[b] = "S"
                me[b] = "S" if shared else "E"
        else:  # write
            if s in ("M", "E"):
                me[b] = "M"                          # silent: no bus traffic
            else:
                if s == "S": bus["upgrade"] += 1
                else:
                    bus["read-exclusive"] += 1
                    if other.get(b) == "M": bus["writeback"] += 1
                other.pop(b, None); me[b] = "M"      # invalidate the other copy
    return bus

# Two cores each increment their own counter 1000 times (load then store)
def counters(addr0, addr1, n=1000):
    t = []
    for _ in range(n):
        for core, a in ((0, addr0), (1, addr1)):
            t += [(core, "R", a), (core, "W", a)]
    return t

for name, a1 in (("adjacent counters (same block)", 0x1004), ("padded counters (own blocks)", 0x1040)):
    b = run(counters(0x1000, a1))
    print(f"{name:32s} {sum(b.values()):5d} bus transactions {b}")

adjacent counters (same block)    5998 bus transactions {'read': 2000, 'read-exclusive': 0, 'upgrade': 1999, 'writeback': 1999}
padded counters (own blocks)         2 bus transactions {'read': 2, 'read-exclusive': 0, 'upgrade': 0, 'writeback': 0}

With the counters adjacent, almost every access causes bus traffic: each core's read misses because the other just invalidated the block, the other cache must write its modified copy back or supply it, and the write then needs an upgrade. Two thousand increments generate about 6,000 bus transactions. With the counters padded to separate 64-byte blocks, each core misses once and then keeps its block in Modified state for good: two transactions in total. After Jonah pads the server's counters to 64 bytes each, the tally job's speedup on 32 cores rises from about 9 to about 21, close to the Amdahl limit for its serial fraction.

Memory consistency

Coherence says what happens at one address. A consistency model says in what order memory operations to different addresses may appear to other cores. Programmers usually assume sequential consistency: the result of any execution is as if all cores' operations were interleaved in some single order, with each core's operations in program order. Under sequential consistency, if core 0 writes data and then sets a flag, any core that sees the flag set will also see the data.

Sequential consistency forbids many hardware optimizations, such as write buffers that let a later load bypass an earlier store, or out-of-order completion of loads. Real processors therefore implement weaker models. Total store order, used by one widely deployed desktop architecture, allows a load to be performed before an earlier store to a different address, but otherwise keeps order. RISC-V's default model, RVWMO, is weaker still: it permits most reorderings of operations to different addresses, while preserving dependencies and a few other orderings. Programs that need order say so explicitly with fence instructions, which order preceding and following memory operations, and with atomic operations that carry acquire and release annotations.

In practice programmers rarely write fences directly. Languages such as C, C++ and Rust define their own memory models with atomic types and orderings, and compilers translate them into the right instructions and fences for each processor. The guarantee programmers rely on is that a data-race-free program, one in which every access to shared data is ordered by synchronization, behaves as if sequentially consistent. Code with data races on weakly ordered hardware can see reorderings that look impossible, which is why the rule to protect shared data with locks or atomics matters so much.

Synchronization hardware

Locks, barriers and lock-free data structures need atomic read-modify-write operations that no other core can interrupt. RISC-V's A extension provides two kinds. Load-reserved and store-conditional, LR and SC, form a pair: LR reads a word and sets a reservation on its address; SC writes only if no other core has written that address since, and reports success or failure, so software retries on failure. Atomic memory operations, AMOs, such as amoadd and amoswap, perform an operation on memory in one instruction, which hardware can carry out near the cache or even at the memory controller. Both kinds carry acquire and release bits that give them the ordering of a fence, so a lock acquire and release need no separate fence instructions.

# Spin lock using amoswap (RVWMO); a0 holds the lock address
acquire:
    li        t0, 1
retry:
    amoswap.w.aq t1, t0, (a0)    # atomically swap 1 into the lock, with acquire ordering
    bnez      t1, retry          # old value 1 means another core holds the lock
    ret
release:
    amoswap.w.rl x0, x0, (a0)    # store 0 with release ordering
    ret

Spinning on an atomic swap generates coherence traffic on every attempt, because each swap needs the block in Modified state. Better locks first spin by reading the lock, which keeps a Shared copy and generates no traffic until the holder releases it, and only then try the swap. Highly contended locks become serialization points and appear as the serial fraction in Amdahl's law, so scalable software minimizes sharing in the first place.

A second core for the NS-5?

For the NS-5, a dual-core cluster would let the radio and network stack run on one core while the classifier runs undisturbed on the other, simplifying real-time scheduling. The costs are area, leakage power from a second core even when idle, and the coherence and synchronization machinery. Maren notes that the two tasks share little data, only a queue of classification results, so a small coherent shared memory or even a hardware message queue would suffice. She adds it to the trade study as an option rather than a requirement.