MESI Protocol

Module 2 · Chapter 2.2 · Coherency Protocol Foundations

Project thread — MSI (2.1) enforced single-writer-or-multiple-readers with three states. MESI adds Exclusive to make the common private read-modify-write cheap. MOESI (2.3) will add Owned for direct cache-to-cache dirty transfer.

1. Learning Outcomes

By the end of this chapter you should be able to:

• Explain the wasted upgrade traffic MSI pays on a private read-then-write.
• Distinguish the four MESI states, and Exclusive (clean, sole owner) from Modified (dirty, sole owner).
• Trace the silent E→M store and the sole-vs-shared decision on a read miss.
• Identify the sole-ownership signal the fabric or Home Node must supply for Exclusive to be safe.
• Implement a representative MESI tracker in SystemVerilog, Verilog-2001, and VHDL.
• Verify that a store from Exclusive issues no invalidation, and that leaving Exclusive never writes back.

2. Why Should I Learn This?

The read-then-write pattern is everywhere: a lock acquire, a counter bump, a struct field update. In MSI that costs two fabric transactions — a read to get the line Shared, then an upgrade to invalidate peers before the store — even when the core is the only holder and the invalidate finds nothing to invalidate.

MESI's Exclusive state removes the second transaction for private data. It is the smallest change that makes coherency cheap for the common case, and every richer protocol (MOESI, MESIF, and CHI's own states) keeps Exclusive. Understand it once and the rest are refinements.

3. Key Terms

4. Previous Chapter Connection

Chapter 2.1 built the three-state MSI machine and the SWMR invariant: a line is either Modified in one cache, or Shared in many, never a writer beside a copy. It also showed that a store from Shared is an upgrade — it must invalidate peers first.

MSI's blind spot: a cache in Shared cannot tell "others also hold this" from "I am the only holder." So it treats every store from S as an upgrade and broadcasts an invalidate — wasteful when it was alone. MESI fixes exactly this by remembering, at read time, whether the copy was sole.

5. Core Concept — four states, one clean sole-owner

MESI keeps MSI's M, S, I and inserts E between "I have a private clean copy" and "I own a dirty copy":

The read miss now has two outcomes:

• No other cache holds the line → grant E (clean, sole owner).
• Some cache holds it → grant S (shared).

And the payoff transition:

E → M is silent. A store while Exclusive just flips to Modified. No invalidate, no bus request — the core is already the only holder.

SWMR is untouched: E and M are both exclusive (single holder); S is shared. Exclusive is simply a reader that is allowed to become a writer without announcing it, because there is no other copy to conflict with.

6. Engineering Mental Model — the "confirmed-private" copy

Extend the token model from MSI:

• S — you hold a read-only photocopy; others may hold identical photocopies.
• E — you hold the only photocopy, and the fabric has confirmed nobody else has one. It is still just a photocopy (clean), but because you are provably alone you may promote it to the master original (M) without telling anyone.
• M — you hold the editable master original.

The whole value of E is the word confirmed. The fabric — a bus "shared" line in classic MESI, the Home Node's directory in CHI — must certify sole ownership at read time. If that certification is wrong, the silent E→M becomes a second writer.

7. Engineering Diagram — the MESI state machine

The two edges out of I carry the whole idea: identical local action (a read miss), different result depending on whether the fabric reports the line as already shared.

8. Worked Example — private vs shared read-modify-write

Two cores, line A, memory holds A = 5. Compare the cost of a read-then-write under MSI and MESI.

Case 1 — CPU0 is the sole holder (private data).

MESI does the private read-modify-write in one transaction; MSI needs two. The invalidate MSI sends finds no copies — pure waste.

Case 2 — CPU1 already shares A.

When the line really is shared, MESI behaves exactly like MSI — the upgrade is necessary. MESI only skips work when the copy was provably sole.

9. Transaction Walkthrough — the read miss that grants Exclusive

The E-vs-S decision is made by the fabric, not the requester. Here is CPU0's read miss on a line no one else holds, mapped onto the CHI cast from Module 1. Representative behavioral flow, not a byte-level trace.

1. CPU0 pipeline → RN0. A load misses (state I). Sender: core. Purpose: fetch a readable copy.
2. RN0 → Home Node (request channel). RN0 issues a read for A. The HN owns A's address range and is the serialization point.
3. HN directory lookup. Stored info: the sharer list for A. It finds no other holder. This is the fact that decides E vs S.
4. HN → SN (or memory): fetch data if the HN does not have it. The data returned is clean.
5. HN → RN0 (response): data + "unique/not-shared". The HN certifies CPU0 is the sole owner, so RN0 installs the line as Exclusive, not Shared. Directory records CPU0 as the single (clean) holder.
6. Later store, no messages. CPU0 stores A. Because the line is Exclusive, RN0 performs the silent E→M — no request leaves the core. The HN's directory still shows CPU0 as sole owner; only its clean/dirty status changed, which the HN learns later if it must snoop.

10. RTL / Hardware View — a per-line MESI tracker

A representative single-line MESI tracker. It extends the MSI tracker of 2.1 with the E state and a shared_in input — the fabric's sole-ownership verdict, sampled on a read miss. Behavioral and simplified: one event per cycle, one line, no data path.

// Representative single-line MESI coherence tracker (educational, not CHI RTL).
// State: I=00 (no copy), S=01 (shared clean), E=10 (exclusive clean), M=11 (dirty).
module mesi_line_tracker (
  input  logic       clk,
  input  logic       rst_n,
  input  logic       req_load,     // local read
  input  logic       req_store,    // local write
  input  logic       snoop_read,   // a peer wants a shared (read) copy
  input  logic       snoop_inval,  // a peer wants to write / read-exclusive
  input  logic       shared_in,    // fabric verdict on a read miss: 1 = peers hold the line
  output logic [1:0] state,
  output logic       do_busread,   // fetch a copy from the Home Node
  output logic       do_invalidate,// ask the HN to invalidate peer copies
  output logic       do_writeback, // return dirty data before losing M
  output logic       can_read,
  output logic       can_write
);
  localparam logic [1:0] I = 2'b00, S = 2'b01, E = 2'b10, M = 2'b11;
  logic [1:0] next;
 
  always_comb begin
    next          = state;
    do_busread    = 1'b0;
    do_invalidate = 1'b0;
    do_writeback  = 1'b0;
    if (snoop_inval) begin
      if (state == M) do_writeback = 1'b1; // only M is dirty; E/S are clean
      next = I;
    end
    else if (snoop_read) begin
      if (state == M) begin
        do_writeback = 1'b1;               // supply newest data, then downgrade
        next         = S;
      end else if (state == E) begin
        next = S;                          // clean downgrade — NO writeback
      end
    end
    else if (req_store) begin
      unique case (state)
        M:       next = M;                                     // write hit
        E:       next = M;                                     // SILENT upgrade
        S:       begin do_invalidate = 1'b1; next = M; end     // shared upgrade
        default: begin do_busread = 1'b1; do_invalidate = 1'b1; next = M; end // I: write miss
      endcase
    end
    else if (req_load) begin
      if (state == I) begin
        do_busread = 1'b1;
        next = shared_in ? S : E;          // sole copy -> Exclusive
      end
    end
  end
 
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) state <= I;
    else        state <= next;
 
  assign can_read  = (state != I);
  assign can_write = (state == M);
endmodule

The same behavior in Verilog-2001:

// Representative single-line MESI tracker (Verilog-2001).
module mesi_line_tracker (
  input            clk,
  input            rst_n,
  input            req_load,
  input            req_store,
  input            snoop_read,
  input            snoop_inval,
  input            shared_in,
  output reg [1:0] state,
  output reg       do_busread,
  output reg       do_invalidate,
  output reg       do_writeback,
  output           can_read,
  output           can_write
);
  localparam I = 2'b00, S = 2'b01, E = 2'b10, M = 2'b11;
  reg [1:0] next;
 
  always @(*) begin
    next = state; do_busread = 1'b0; do_invalidate = 1'b0; do_writeback = 1'b0;
    if (snoop_inval) begin
      if (state == M) do_writeback = 1'b1;
      next = I;
    end else if (snoop_read) begin
      if (state == M) begin do_writeback = 1'b1; next = S; end
      else if (state == E) next = S;
    end else if (req_store) begin
      case (state)
        M:       next = M;
        E:       next = M;                                   // silent upgrade
        S:       begin do_invalidate = 1'b1; next = M; end
        default: begin do_busread = 1'b1; do_invalidate = 1'b1; next = M; end
      endcase
    end else if (req_load) begin
      if (state == I) begin
        do_busread = 1'b1;
        next = shared_in ? S : E;
      end
    end
  end
 
  always @(posedge clk or negedge rst_n)
    if (!rst_n) state <= I; else state <= next;
 
  assign can_read  = (state != I);
  assign can_write = (state == M);
endmodule

And in VHDL:

-- Representative single-line MESI tracker (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity mesi_line_tracker is
  port (
    clk, rst_n              : in  std_logic;
    req_load, req_store     : in  std_logic;
    snoop_read, snoop_inval : in  std_logic;
    shared_in               : in  std_logic;
    state                   : out std_logic_vector(1 downto 0);
    do_busread              : out std_logic;
    do_invalidate           : out std_logic;
    do_writeback            : out std_logic;
    can_read, can_write     : out std_logic
  );
end entity;
 
architecture rtl of mesi_line_tracker is
  constant I : std_logic_vector(1 downto 0) := "00";
  constant S : std_logic_vector(1 downto 0) := "01";
  constant E : std_logic_vector(1 downto 0) := "10";
  constant M : std_logic_vector(1 downto 0) := "11";
  signal cur, nxt : std_logic_vector(1 downto 0);
begin
  comb : process(cur, req_load, req_store, snoop_read, snoop_inval, shared_in)
  begin
    nxt <= cur; do_busread <= '0'; do_invalidate <= '0'; do_writeback <= '0';
    if snoop_inval = '1' then
      if cur = M then do_writeback <= '1'; end if;
      nxt <= I;
    elsif snoop_read = '1' then
      if cur = M then do_writeback <= '1'; nxt <= S;
      elsif cur = E then nxt <= S; end if;
    elsif req_store = '1' then
      if cur = M then nxt <= M;
      elsif cur = E then nxt <= M;                 -- silent upgrade
      elsif cur = S then do_invalidate <= '1'; nxt <= M;
      else do_busread <= '1'; do_invalidate <= '1'; nxt <= M; end if;
    elsif req_load = '1' then
      if cur = I then
        do_busread <= '1';
        if shared_in = '1' then nxt <= S; else nxt <= E; end if;
      end if;
    end if;
  end process;
 
  seq : process(clk, rst_n)
  begin
    if rst_n = '0' then cur <= I;
    elsif rising_edge(clk) then cur <= nxt; end if;
  end process;
 
  state     <= cur;
  can_read  <= '0' when cur = I else '1';
  can_write <= '1' when cur = M else '0';
end architecture;

All three model the identical machine: sole-vs-shared read grant, silent E→M, and writeback only from M.

11. Timing View — the silent upgrade

CPU0's private read-modify-write. Watch the store at t3 issue no bus transaction. Timing is representative — real CHI latencies are not fixed cycle counts.

Under MSI the same store would drive an upgrade transaction on the bus at t3. Exclusive is exactly the state that lets the renderer of coherency traffic stay quiet.

12. Verification View — the silent upgrade must stay silent

Three properties pin the E state down.

// Bind to mesi_line_tracker.
// 1. Write permission exists only in Modified.
property p_write_only_in_M;
  @(posedge clk) disable iff (!rst_n) can_write |-> (state == 2'b11);
endproperty
assert property (p_write_only_in_M);
 
// 2. A store from Exclusive is SILENT — no invalidate, no bus request.
property p_silent_upgrade;
  @(posedge clk) disable iff (!rst_n)
    (state == 2'b10) && req_store |-> (!do_invalidate && !do_busread);
endproperty
assert property (p_silent_upgrade);
 
// 3. Exclusive is clean — leaving E never writes data back.
property p_exclusive_clean;
  @(posedge clk) disable iff (!rst_n) (state == 2'b10) |-> !do_writeback;
endproperty
assert property (p_exclusive_clean);

The system invariant is still SWMR from 2.1, now with E folded into "exclusive": for each line, mCount + eCount <= 1 and not ((mCount + eCount == 1) and sCount > 0) — at most one exclusive holder (E or M), never beside a sharer. A scoreboard or directory model checks it.

• What it proves: the silent upgrade is safe (only ever fired from a provably sole state) and E is treated as clean.
• What it does not prove: that the fabric's shared_in verdict was correct. If the directory miscounts, E is granted wrongly and Property 2 still passes while SWMR breaks — the check must live where sole ownership is decided.
• Bug signature when it fails: do_invalidate on an E store (lost the MESI benefit), or mCount + eCount == 2 after a wrong shared_in (two writers).

13. Testbench — drive the read grant and the silent store

Deterministic stimulus; actions sampled while inputs are asserted (pre-edge), state checked after the edge — no sampling race.

module tb_mesi_line_tracker;
  logic clk = 0, rst_n;
  logic req_load, req_store, snoop_read, snoop_inval, shared_in;
  logic [1:0] state;
  logic do_busread, do_invalidate, do_writeback, can_read, can_write;
  int errors = 0;
 
  mesi_line_tracker dut (.*);
  always #5 clk = ~clk;
 
  // Apply one event; check pre-edge actions, then post-edge state.
  task automatic ev(input logic ld, st, sr, si, sh,
                    input logic [1:0] exp_state,
                    input logic exp_br, exp_iv, exp_wb,
                    input string tag);
    logic br, iv, wb;
    req_load = ld; req_store = st; snoop_read = sr; snoop_inval = si; shared_in = sh;
    #1;
    br = do_busread; iv = do_invalidate; wb = do_writeback;
    if (br !== exp_br || iv !== exp_iv || wb !== exp_wb) begin
      errors++;
      $display("FAIL [%s] actions br/iv/wb = %b/%b/%b (exp %b/%b/%b)",
               tag, br, iv, wb, exp_br, exp_iv, exp_wb);
    end
    @(posedge clk); #1;
    req_load = 0; req_store = 0; snoop_read = 0; snoop_inval = 0; shared_in = 0;
    if (state !== exp_state) begin
      errors++;
      $display("FAIL [%s] state=%0d exp=%0d", tag, state, exp_state);
    end else
      $display("PASS [%s] state=%0d actions br/iv/wb=%b/%b/%b", tag, exp_state, br, iv, wb);
  endtask
 
  initial begin
    rst_n = 0; ev(0,0,0,0,0, 2'b00, 0,0,0, "reset");
    rst_n = 1;
    // Private read-modify-write: I -> E (sole) -> M (silent)
    ev(1,0,0,0,0, 2'b10, 1,0,0, "load sole: I->E");
    if (can_write) begin errors++; $display("FAIL: writable in Exclusive"); end
    ev(0,1,0,0,0, 2'b11, 0,0,0, "store: E->M SILENT (no inval, no bus)");
    if (!can_write) begin errors++; $display("FAIL: not writable in Modified"); end
    // Peer store on M writes back and invalidates.
    ev(0,0,0,1,0, 2'b00, 0,0,1, "peer store: M->I (writeback)");
    // Shared read-modify-write: I -> S (shared) -> M (upgrade)
    ev(1,0,0,0,1, 2'b01, 1,0,0, "load shared: I->S");
    ev(0,1,0,0,0, 2'b11, 0,1,0, "store: S->M (upgrade, invalidate)");
    // Peer read on M downgrades with writeback.
    ev(0,0,1,0,0, 2'b01, 0,0,1, "peer read: M->S (writeback)");
    // Exclusive is clean: a peer read downgrades E->S with NO writeback.
    ev(0,0,0,1,0, 2'b00, 0,0,0, "peer store: S->I");
    ev(1,0,0,0,0, 2'b10, 1,0,0, "load sole: I->E");
    ev(0,0,1,0,0, 2'b01, 0,0,0, "peer read: E->S (clean, no wb)");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS [reset] state=0 actions br/iv/wb=0/0/0
PASS [load sole: I->E] state=2 actions br/iv/wb=1/0/0
PASS [store: E->M SILENT (no inval, no bus)] state=3 actions br/iv/wb=0/0/0
PASS [peer store: M->I (writeback)] state=0 actions br/iv/wb=0/0/1
PASS [load shared: I->S] state=1 actions br/iv/wb=1/0/0
PASS [store: S->M (upgrade, invalidate)] state=3 actions br/iv/wb=0/1/0
PASS [peer read: M->S (writeback)] state=1 actions br/iv/wb=0/0/1
PASS [peer store: S->I] state=0 actions br/iv/wb=0/0/0
PASS [load sole: I->E] state=2 actions br/iv/wb=1/0/0
PASS [peer read: E->S (clean, no wb)] state=1 actions br/iv/wb=0/0/0
ALL TESTS PASSED

14. DebugLab — Exclusive granted without confirmed sole ownership

cyc  core  event      state->next  shared_in  busread inval  wb
 2   CPU0  load miss   I -> E          0         1      0     0   <-- E granted, but CPU1 holds S
 2   CPU1  (S copy still valid)
 6   CPU0  store       E -> M          -         0      0     0   <-- SILENT upgrade, no invalidate

15. Common Mistakes

• Granting Exclusive without confirmed sole ownership. Assumption: an uncontended read means private. Bug: a wrong shared_in yields a bad E, and the silent upgrade makes two writers (the DebugLab). Prevention: E only on a proven-unique response; otherwise S.
• Writing back a clean Exclusive line. Assumption: losing a line means flushing it. Bug: needless writeback bandwidth on E→S / E→I. Prevention: writeback only from M; E and S are clean.
• Confusing Exclusive with Modified. Assumption: sole owner means dirty. Bug: memory is treated as stale for E when it is current. Prevention: E is clean and equals memory; only M is dirty.
• Forgetting the silent E→M. Assumption: every store to a writable-intent line needs an upgrade. Bug: an invalidate on E throws away MESI's whole point, back to MSI cost. Prevention: a store from E issues no traffic.
• Treating MESI as the CHI state set. Assumption: these four states are the specification. Bug: confusion when CHI's Unique/Shared/Clean/Dirty states appear. Prevention: MESI is the concept; the CHI states and directory are later modules.

16. Engineering Checklist

• A read miss grants E only when the fabric proves no other holder; otherwise S.
• A store from E is silent — no invalidate, no bus request.
• A store from S still performs a visible upgrade (invalidate peers).
• Leaving E (peer read/store) issues no writeback; only M writes back.
• can_write is asserted only in M; a scoreboard enforces one exclusive holder (E or M).
• The shared_in / sole-ownership source is verified where it is produced, not just consumed.

17. Key Takeaways

• MESI adds one state, Exclusive — a clean line held by exactly one cache, equal to memory.
• The read miss splits by sole ownership: unique → E, shared → S.
• E → M is silent — the private read-modify-write costs one transaction, not two.
• Exclusive is clean: leaving it needs no writeback; only M is dirty.
• The silent upgrade is safe only because E certifies sole ownership — verify that certification.
• MESI here is representative — the base that MOESI, MESIF, and CHI's own states extend.

18. Quick Revision

MESI = MSI + Exclusive. Four states: M (dirty, sole, writable), E (clean, sole, silently writable), S (clean, shared, read-only), I (none). Read miss: unique → E, shared → S. E→M silent (no bus). Store from S → M (upgrade, invalidate). Leaving E → no writeback (clean); leaving M → writeback (dirty). SWMR with E folded into exclusive: one of E/M (exclusive) or many S. Safety of the silent upgrade depends on a correct sole-ownership verdict. Representative model, not the CHI spec state set.

Coming Next

Chapter 2.3 — MOESI Protocol. MESI still forces a cache that holds dirty data to write back to memory before another core can read it. MOESI adds the Owned state, letting a dirty line be shared directly cache-to-cache — the owner keeps responsibility for the writeback while other cores read the current value — cutting memory traffic on shared-dirty lines.