Multicore, Cache Coherence and Memory Ordering
Clock frequencies stopped rising around 2005 (power density), so CPUs grew more cores instead.
Concept
Clock frequencies stopped rising around 2005 (power density), so CPUs grew more cores instead. Terms:
A complete processor with its own pipeline and L1/L2 caches SMT / Hyper-Threading
One core runs two hardware threads, sharing execution units All cores share memory equally
Memory is attached to sockets; local memory is faster than remote
Performance + efficiency cores (Arm big.LITTLE, Intel hybrid)
Each core caches data privately, so copies of the same line can diverge. A coherence protocol keeps them consistent; the classic one is MESI:
Only this cache has the line, and it is dirty Only this cache has it, clean Several caches may have clean copies Not valid here
A write requires exclusive ownership: other copies are invalidated. Cores snoop a shared bus or consult a directory. Variants: MOESI (AMD), MESIF (Intel).
False sharing: independent variables used by different cores sit in the same 64-byte line, so every write invalidates the other cores' copies — the line "ping-pongs" between caches although no data is actually shared.
Memory Consistency Models Coherence concerns one location; consistency concerns the order in which different locations become visible to other cores.
Sequential consistency (SC): all cores see one interleaving of all operations in program order — intuitive, but slow to implement.
x86 (TSO — total store order): a store may become visible *after* a later load to a different address, because stores wait in a store buffer. Everything else is ordered.
ARM, RISC-V, POWER (weak/relaxed): loads and stores can be reordered much more freely.
Programs restore the order they need with fences/barriers (mfence, dmb, fence) or, in C/C++, atomics with memory orders (seq_cst, acquire, release, relaxed). Correct locks and atomics include these barriers — which is why ordinary code using mutexes works on every architecture.
Why It Matters
Scalability problems (false sharing, contended cache lines), lock-free data structures, device drivers sharing memory with DMA engines, and bugs that appear only on ARM but never on x86 all come from these topics.
Syntax
struct { long value; char pad[56]; } counters[N]; /* one cache line per counter */
_Alignas(64) long hot; /* C11 alignment */
atomic_store_explicit(&flag, 1, memory_order_release); /* publish */
atomic_load_explicit(&flag, memory_order_acquire); /* consume */
atomic_thread_fence(memory_order_seq_cst); /* full barrier */Example
26.1 False sharing 26.2 Memory reordering on x86: the store-buffering test 26.3 MESI state transitions
#include <stdio.h>
#include <pthread.h>
#include <time.h>
enum { THREADS = 4, ITER = 50000000 };
struct { volatile long value; } packed[THREADS]; /* neighbours share a cache line */
struct { volatile long value; char pad[64 - sizeof(long)]; } padded[THREADS] __attribute__((aligned(64))); /* one line each */
static void *bump_packed(void *arg) { long i = (long)arg; for (long n = 0; n < ITER; n++) packed[i].value++; return NULL; }
static void *bump_padded(void *arg) { long i = (long)arg; for (long n = 0; n < ITER; n++) padded[i].value++; return NULL; }
static double run(void *(*fn)(void *))
{
pthread_t t[THREADS];
struct timespec a, b;
clock_gettime(CLOCK_MONOTONIC, &a);
for (long i = 0; i < THREADS; i++) pthread_create(&t[i], NULL, fn, (void *)i);
for (int i = 0; i < THREADS; i++) pthread_join(t[i], NULL);
clock_gettime(CLOCK_MONOTONIC, &b);
return (b.tv_sec - a.tv_sec) * 1e3 + (b.tv_nsec - a.tv_nsec) / 1e6;
}
int main(void)
{
printf("sizeof one packed counter: %zu bytes, one padded counter: %zu bytes\n", sizeof packed[0], sizeof padded[0]);
double t1 = run(bump_packed), t2 = run(bump_padded);
printf("4 thread
…#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>
/* Store-buffering litmus test: thread 1: x = 1; r1 = y thread 2: y = 1; r2 = x
Under sequential consistency at least one thread must see the other's store, so r1 = r2 = 0 is impossible.
x86 lets a load pass an earlier store to a different address (store buffer), so it DOES happen with relaxed accesses. */
atomic_int x, y, r1, r2;
atomic_int go1, go2, done1, done2;
int use_fence;
static void *t1(void *a)
{
for (;;) {
while (!atomic_load(&go1)) ;
atomic_store(&go1, 0);
atomic_store_explicit(&x, 1, memory_order_relaxed);
if (use_fence) atomic_thread_fence(memory_order_seq_cst); /* compiles to mfence on x86 */
atomic_store_explicit(&r1, atomic_load_explicit(&y, memory_order_relaxed), memory_order_relaxed);
atomic_store(&done1, 1);
}
return a;
}
static void *t2(void *a)
{
for (;;) {
while (!atomic_load(&go2)) ;
atomic_store(&go2, 0);
atomic_store_explicit(&y, 1, memory_order_relaxed);
if (use_fence) atomic_thread_fence(memory_order_seq_cst);
atomic_store_explicit(&r2, atomic_load_explicit(&x, memory
…"""MESI cache coherence: states of one cache line in two cores' caches as they read and write it."""
state = {"core0": "I", "core1": "I"}
def access(core, op):
other = "core1" if core == "core0" else "core0"
before = dict(state)
bus = ""
if op == "read":
if state[core] == "I":
if state[other] in ("M", "E", "S"):
bus = "BusRd: other cache supplies the line" + (" (writes back M data)" if state[other] == "M" else "")
state[other] = "S"
state[core] = "S"
else:
bus = "BusRd: loaded from memory, no other copy"
state[core] = "E"
else: # write
if state[core] in ("S", "I"):
bus = "BusRdX/Upgrade: invalidate other copies"
state[other] = "I"
elif state[core] == "E":
bus = "silent E -> M, no bus traffic"
state[core] = "M"
print(f"{core} {op:<5} {before['core0']}{before['core1']} -> {state['core0']}{state['core1']} {bus}")
print("op c0c1 -> c0c1")
for core, op in [("core0", "read"), ("core0", "write"), ("core1", "read"), ("core1", "write"),
("core0", "write"), ("cor
…Expected Result
Each thread only touches its own counter, yet packing the four counters into one cache line made the program about twice as slow: every increment had to take the line away from the other cores. Padding each counter to its own line removed the contention.
Under sequential consistency the outcome r1 = r2 = 0 is impossible, but on this x86 CPU it happened in almost one run in five: each core's store was still in its store buffer when its own load read the other variable. With a seq_cst fence between the store and the load (an mfence instruction on x86) it never happened. (The exact count varies from run to run.)
The first reader gets the line in Exclusive state and can later write it without any bus traffic; a read by another core forces the modified data to be shared; every write invalidates the other copy.
sizeof one packed counter: 8 bytes, one padded counter: 64 bytes
4 threads, private counters in ONE cache line : 163 ms
4 threads, each counter in ITS OWN cache line : 77 ms (2.1x faster)relaxed stores/loads : r1 == r2 == 0 in 183014 of 1000000 runs
with seq_cst fences : r1 == r2 == 0 in 0 of 1000000 runsop c0c1 -> c0c1
core0 read II -> EI BusRd: loaded from memory, no other copy
core0 write EI -> MI silent E -> M, no bus traffic
core1 read MI -> SS BusRd: other cache supplies the line (writes back M data)
core1 write SS -> IM BusRdX/Upgrade: invalidate other copies
core0 write IM -> MI BusRdX/Upgrade: invalidate other copies
core1 read MI -> SS BusRd: other cache supplies the line (writes back M data)Common Mistakes
Per-thread counters or flags packed into one array without padding.
Assuming that because code works on x86 it is correctly synchronized (it may break on ARM).
Using volatile instead of atomics for inter-thread communication.
Adding seq_cst everywhere "to be safe" in hot paths without measuring.
Best Practices
Align and pad frequently written per-thread data to 64 bytes (C++17: std::hardware_destructive_interference_size).
Use mutexes or well-known lock-free structures; use acquire/release for publish/consume patterns.
Test concurrent code on weakly ordered hardware (ARM) and with ThreadSanitizer.
On NUMA machines, keep threads close to their memory.
Interview Relevance
Very high for systems/performance roles: "what is cache coherence?", "explain MESI", "what is false sharing and how do you fix it?", "what is a memory barrier?", "coherence vs consistency?", "acquire vs release semantics?".
Practice Questions
Change 26.1 to use 2 and 8 threads and explain the results.
Replace the fence in 26.2 with memory_order_release stores and memory_order_acquire loads. Does r1 = r2 = 0 still occur? Why?
Extend the MESI simulator to three cores.
Find the cache line size with getconf LEVEL1_DCACHE_LINESIZE.
Quick Quiz
Q1. (Multiple choice) In MESI, which state allows a write without bus traffic? A) Shared B) Invalid C) Exclusive D) None Answer: C (verified: silent E → M).
Q2. (Predict the output) Can r1 = r2 = 0 occur in the store-buffering test on x86 with relaxed atomics?
Answer: Yes (verified: in about 18% of runs); never with a seq_cst fence.
Q3. (True/False) False sharing requires two threads to write the same variable.
Answer: False. Different variables in the same cache line are enough (verified).
Q4. (Find the bug) data = 42; ready = 1; in one thread and while (!ready) {} use(data); in another, with plain int variables.
Answer: Data race: no ordering or visibility guarantee. Make ready an atomic, store it with release and load it with acquire.
Coding Challenge
Publish a value from one thread to another with a release store and an acquire load on an atomic flag, and verify the consumer always sees the published data.
#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>
static int payload;
static atomic_int ready;
static void *producer(void *arg)
{
(void)arg;
payload = 12600; /* ordinary write ... */
atomic_store_explicit(&ready, 1, memory_order_release); /* ... published by the release */
return NULL;
}
static void *consumer(void *arg)
{
while (!atomic_load_explicit(&ready, memory_order_acquire)) ; /* acquire pairs with release */
*(int *)arg = payload; /* guaranteed to see 12600 */
return NULL;
}
int main(void)
{
pthread_t p, c;
int seen = 0;
pthread_create(&c, NULL, consumer, &seen);
pthread_create(&p, NULL, producer, NULL);
pthread_join(p, NULL);
pthread_join(c, NULL);
printf("consumer saw payload %d\n", seen);
return 0;
}