Introduction

Your laptop almost certainly has four or more CPU cores. Each core has its own private cache — a tiny, blazing-fast memory that holds copies of recently used data. Without caches, cores would stall waiting for main memory hundreds of times per second, and the chip would be far slower.

But that speed comes with a hidden problem. If Core 0 reads a variable xx into its cache and Core 1 also reads xx into its own cache, both are holding a copy. Now Core 0 writes a new value to xx. Core 1 still sees the old value. The two caches disagree — and programs that depend on shared data will compute wrong answers.

This is the cache coherence problem: how do you keep every core's cached copy of shared memory consistent, without destroying the performance advantage caches provide in the first place?

The dominant answer, used in virtually every x86 and ARM chip shipped in the last four decades, is the MESI protocol — a state machine named after its four states: Modified, Exclusive, Shared, and Invalid.

Try It: Watch the Cache Line Bounce

The demo below simulates two cores sharing a single memory address. Each core has its own cache slot. Use the buttons to issue Read and Write operations from either core, and watch the MESI state of each cache slot update in real time.

<!-- MESI cache-coherence demo — two cores, one shared address -->
<div class="scene">
  <div class="core-box" id="core0">
    <div class="core-label">Core 0</div>
    <div class="cache-slot" id="slot0">
      <div class="slot-label">Cache</div>
      <div class="slot-state" id="state0">I</div>
      <div class="slot-value" id="val0">—</div>
    </div>
    <div class="btn-row">
      <button id="r0" type="button">Read</button>
      <button id="w0" type="button">Write</button>
    </div>
  </div>

  <div class="bus-area">
    <div class="bus-label">Interconnect Bus</div>
    <div class="bus-line">
      <div class="bus-msg" id="busmsg"></div>
    </div>
    <div class="mem-box">
      <div class="mem-label">Main Memory</div>
      <div class="mem-val" id="memval">0</div>
    </div>
  </div>

  <div class="core-box" id="core1">
    <div class="core-label">Core 1</div>
    <div class="cache-slot" id="slot1">
      <div class="slot-label">Cache</div>
      <div class="slot-state" id="state1">I</div>
      <div class="slot-value" id="val1">—</div>
    </div>
    <div class="btn-row">
      <button id="r1" type="button">Read</button>
      <button id="w1" type="button">Write</button>
    </div>
  </div>
</div>

<div class="log-area">
  <div class="log-hdr">Event Log</div>
  <div id="log"></div>
</div>
<div class="btns-bottom">
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>

/* Layout and color for the MESI cache-coherence demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #1a2233; background: #f6f8fb; }
.scene { display: flex; align-items: flex-start; gap: 10px; justify-content: center; padding: 14px 8px 6px; flex-wrap: wrap; }
.core-box { background: #fff; border: 1.5px solid #c5d3e0; border-radius: 12px; padding: 10px 12px; min-width: 130px; display: flex; flex-direction: column; align-items: center; gap: 8px; }
.core-label { font-weight: 700; font-size: .85rem; color: #1d3557; }
.cache-slot { background: #edf2f7; border: 1.5px solid #b0c4d8; border-radius: 8px; padding: 6px 14px; text-align: center; min-width: 100px; }
.slot-label { font-size: .7rem; color: #5a7088; text-transform: uppercase; letter-spacing: .05em; margin-bottom: 2px; }
.slot-state { font-size: 1.5rem; font-weight: 900; letter-spacing: .05em; transition: color .3s; }
.slot-value { font-size: 1rem; font-weight: 600; color: #2d6a4f; min-height: 1.4em; }
.state-M { color: #e63946; }
.state-E { color: #0077b6; }
.state-S { color: #2a9d8f; }
.state-I { color: #adb5bd; }
.btn-row { display: flex; gap: 6px; }
button { font: 600 13px system-ui; padding: .38rem .75rem; border: 1.5px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; transition: background .15s; }
button:hover { background: #2a4a7f; }
button.ghost { background: #fff; color: #1d3557; }
button.ghost:hover { background: #e8eef4; }
.bus-area { display: flex; flex-direction: column; align-items: center; gap: 6px; padding-top: 28px; min-width: 100px; }
.bus-label { font-size: .7rem; color: #5a7088; text-transform: uppercase; letter-spacing: .05em; }
.bus-line { width: 4px; height: 70px; background: #b0c4d8; border-radius: 2px; position: relative; }
.bus-msg { position: absolute; left: 50%; transform: translateX(-50%); top: 50%; background: #e63946; color: #fff; font-size: .65rem; font-weight: 700; padding: 2px 5px; border-radius: 4px; white-space: nowrap; opacity: 0; transition: opacity .3s; }
.bus-msg.visible { opacity: 1; }
.mem-box { background: #fff; border: 1.5px solid #a8c4de; border-radius: 8px; padding: 5px 14px; text-align: center; }
.mem-label { font-size: .7rem; color: #5a7088; text-transform: uppercase; letter-spacing: .05em; }
.mem-val { font-size: 1.1rem; font-weight: 700; color: #1d3557; }
.log-area { margin: 4px 10px 0; background: #fff; border: 1px solid #d1dce8; border-radius: 8px; max-height: 120px; overflow-y: auto; padding: 6px 10px; }
.log-hdr { font-size: .72rem; color: #5a7088; text-transform: uppercase; letter-spacing: .05em; margin-bottom: 4px; }
#log { font-size: .8rem; line-height: 1.6; color: #1a2233; }
.log-entry { padding: 1px 0; border-bottom: 1px solid #f0f4f8; }
.log-entry:last-child { border-bottom: none; }
.btns-bottom { display: flex; justify-content: center; padding: 8px; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// MESI protocol: each cache line is in one of four states per core.
// States: M=Modified (dirty, exclusive), E=Exclusive (clean, exclusive),
// S=Shared (clean, multiple readers), I=Invalid (no data). Transitions on read/write.

// MESI state machine for two cores sharing one address
let mem = 0;
let writeCounter = 0;
// cache[i] = { state: 'M'|'E'|'S'|'I', value: number|null }
const cache = [
  { state: 'I', value: null },
  { state: 'I', value: null }
];

// Map state letter to CSS class for color coding
const stateClass = { M: 'state-M', E: 'state-E', S: 'state-S', I: 'state-I' };

function render() {
  // Update DOM to reflect current cache and memory state
  for (let i = 0; i < 2; i++) {
    const s = document.getElementById('state' + i);
    const v = document.getElementById('val' + i);
    s.textContent = cache[i].state;
    s.className = 'slot-state ' + stateClass[cache[i].state];
    v.textContent = cache[i].state === 'I' ? '—' : cache[i].value;
  }
  document.getElementById('memval').textContent = mem;
}

function flashBus(msg) {
  // Show a bus message briefly to illustrate interconnect traffic
  const el = document.getElementById('busmsg');
  el.textContent = msg;
  el.classList.add('visible');
  setTimeout(() => el.classList.remove('visible'), 900);
}

function addLog(text) {
  const log = document.getElementById('log');
  const d = document.createElement('div');
  d.className = 'log-entry';
  d.textContent = text;
  log.prepend(d);
  // Keep log bounded so the UI stays tidy
  while (log.children.length > 30) log.removeChild(log.lastChild);
}

// doRead(core): simulate a cache-read from this core under MESI
function doRead(core) {
  const other = 1 - core;
  const prev = cache[core].state;
  if (prev !== 'I') {
    // Hit — no bus traffic needed
    addLog(i18nFmt('Core %core%: Read hit (state=%state%, val=%val%) — no bus traffic.', { core, state: prev, val: cache[core].value }));
    return;
  }
  // cache miss: fetch from other core (if M) or from memory
  if (cache[other].state === 'M') {
    // Other core holds Modified copy — must write back before sharing
    mem = cache[other].value;
    flashBus(i18nFmt('WB ← Core %core%', { core: other }));
    addLog(i18nFmt('Core %other%: Write-back to memory (val=%mem%) — now Shared.', { other, mem }));
    cache[other].state = 'S';
    cache[other].value = mem;
  } else if (cache[other].state === 'E') {
    cache[other].state = 'S';
  }
  // now load from memory
  cache[core].state = (cache[other].state === 'S') ? 'S' : 'E';
  cache[core].value = mem;
  if (cache[other].state !== 'S') {
    flashBus(i18nFmt('RD → Core %core%', { core }));
  }
  addLog(i18nFmt('Core %core%: Read miss → state=%state%, loaded val=%val%.', { core, state: cache[core].state, val: mem }));
  render();
}

// doWrite(core): simulate a cache-write, invalidating all other copies
function doWrite(core) {
  const other = 1 - core;
  writeCounter++;
  const newVal = writeCounter;

  if (cache[other].state === 'M') {
    // Other core has Modified data — write back first, then invalidate
    mem = cache[other].value;
    cache[other].state = 'I';
    cache[other].value = null;
    flashBus(i18nFmt('INV → Core %core%', { core: other }));
    addLog(i18nFmt('Core %other%: Write-back to memory (val=%mem%) before invalidation.', { other, mem }));
  } else if (cache[other].state === 'E' || cache[other].state === 'S') {
    // Send invalidation message on bus to all sharers
    cache[other].state = 'I';
    cache[other].value = null;
    flashBus(i18nFmt('INV → Core %core%', { core: other }));
    addLog(i18nFmt('Core %other%: Invalidated (was Shared/Exclusive).', { other }));
  }

  cache[core].state = 'M';
  cache[core].value = newVal;
  // Memory is stale while this core holds Modified; it will be updated on eviction or another read
  addLog(i18nFmt('Core %core%: Write → Modified, val=%val%. All other copies invalidated.', { core, val: newVal }));
  render();
}

document.getElementById('r0').addEventListener('click', () => doRead(0));
document.getElementById('w0').addEventListener('click', () => doWrite(0));
document.getElementById('r1').addEventListener('click', () => doRead(1));
document.getElementById('w1').addEventListener('click', () => doWrite(1));
document.getElementById('resetBtn').addEventListener('click', () => {
  mem = 0; writeCounter = 0;
  cache[0] = { state: 'I', value: null };
  cache[1] = { state: 'I', value: null };
  document.getElementById('log').innerHTML = '';
  document.getElementById('busmsg').classList.remove('visible');
  render();
  addLog('Reset. Both caches Invalid. Memory = 0.');
});

render();
addLog('Initial state: both caches Invalid. Memory = 0.');
Result
Console

Notice what happens when one core writes while the other holds a Shared copy: the writing core's cache transitions to Modified and the other core's copy is immediately Invalidated — it must fetch the new value before its next read. This ping-pong between cores is called cache-line bouncing, and it is the hidden performance cost every parallel programmer must respect.

The Real Complexity

The MESI protocol assigns one of four states to every cache line on every core:

  • Modified (M) — this core has the only valid copy, and it has been written. Main memory is stale. Before another core can read this line, the modified core must write back the value.
  • Exclusive (E) — this core has the only copy, and it matches main memory. No write-back needed yet; a local write promotes it to M cheaply.
  • Shared (S) — two or more cores hold a read-only copy that matches main memory. Any write from any core will invalidate all other copies.
  • Invalid (I) — this cache slot holds no useful data. The next access is a cache miss.

The transitions are the heart of the protocol. A write from Core 0 sends an invalidation message on the interconnect bus (or directory) to every core holding an S copy, forcing them to I. The next time those cores read the address, they take a cache miss and fetch the fresh value — from Core 0's cache or from main memory after Core 0 has written back.

The performance trap: false sharing. Two cores can thrash the protocol even when they are writing different variables, if those variables happen to sit in the same 64-byte cache line. Core 0's write invalidates Core 1's copy of the whole line, even though Core 1's variable was never touched. This is false sharing, and it can make a parallel program slower than its single-threaded counterpart.

The cost grows with core count. On a chip with nn cores all writing to the same line, the bus traffic is O(n)O(n) invalidations per write — exactly the kind of contention that prevents linear scaling even on embarrassingly parallel workloads.

Where It Matters

Cache coherence is invisible when it works — and brutally visible when it doesn't:

  • Parallel programming: false sharing is a classic performance bug. The fix — padding data structures so hot variables land on different cache lines — can yield 10× speedups without changing any algorithm.
  • Lock-free data structures: algorithms that avoid mutexes still depend on coherence to see each other's writes in a timely way. Memory barriers (fence instructions) tell the CPU not to reorder stores across critical points.
  • Weak memory models: ARM and RISC-V processors implement relaxed coherence — cores may observe each other's writes in different orders unless explicit barriers are used. Writing correct lock-free code requires understanding the underlying memory model.
  • GPU computing: GPUs have thousands of cores but weaker coherence guarantees. Shared memory within a thread-block is coherent; across blocks, explicit synchronization is required.
  • Non-Uniform Memory Access (NUMA): in multi-socket servers, coherence traffic crossing between sockets is especially expensive; data placement strategies aim to minimize cross-socket invalidations.

Understanding cache coherence connects directly to topics like load balancing and non-convex optimization: any parallel algorithm that shares writable state must budget for coherence overhead or it will not scale.

Conclusion

The MESI protocol is one of the quiet triumphs of computer architecture: a four-state machine, running in hardware at billions of events per second, that makes every shared-memory parallel program correct by default. You never call a function to keep caches in sync — the hardware does it for you.

But the protocol has a price. Every write to a shared cache line sends invalidation messages across the chip. False sharing punishes programmers who don't think about data layout. And at high core counts, coherence traffic becomes a bottleneck as real as any algorithm's asymptotic complexity.

Knowing this, you can make better decisions: pad your data structures, avoid unnecessary sharing, choose the right memory ordering. The four letters M-E-S-I are small, but what they guard is the difference between a parallel program that scales and one that doesn't.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/cache-coherence/Content licensed under CC BY-NC 4.0.