MSI Protocol

Module 2 · Chapter 2.1 · Coherency Protocol Foundations

Project thread — Module 1 named the contract (write propagation, write serialization, value/coherence). Module 2 opens by building the first machine that keeps it: a per-line coherence state machine. MSI is the base; MESI, MOESI, and MESIF refine it in the next chapters.

1. Learning Outcomes

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

• Explain why every cached line needs a per-line coherence state, not just a valid bit.
• Distinguish the three MSI states and the single-writer-or-multiple-readers (SWMR) invariant they enforce.
• Trace the MSI transitions driven by a local load, a local store, and a remote snoop.
• Identify which agent — the requesting cache, the Home Node, or a peer cache — drives each transition and each action.
• Implement a representative per-line MSI tracker in SystemVerilog, Verilog-2001, and VHDL.
• Verify the SWMR invariant and the write-permission rule with an assertion and a scoreboard check.

2. Why Should I Learn This?

Module 1 told you what must be true. It did not tell you how any hardware makes it true. MSI is the smallest complete answer: a three-state machine, one instance per cached line per cache, that turns "we must keep the invariants" into concrete read and write permissions plus the messages a cache must send.

Every richer protocol you will meet — MESI, MOESI, MESIF, and the CHI coherence states themselves — is MSI plus extra states that remove specific inefficiencies. Learn MSI precisely and the rest are small deltas. Miss it, and later state tables look like arbitrary trivia.

3. Key Terms

4. Previous Chapter Connection

Chapter 1.9 named the three invariants and previewed the CHI cast — Requester Node (RN), Home Node (HN), Subordinate Node (SN), snoop, and directory. It showed that only a single serialization point (the HN) can guarantee write serialization.

That chapter stopped at the contract. It did not say what a cache stores to know its rights, or what it does when a peer wants the line. MSI fills exactly that gap: it is the per-line bookkeeping — one state field and one transition table — that makes a cache a correct coherency participant. The HN still orders requests; MSI is what each cache does around that ordering.

5. Core Concept — three states, two permissions

MSI gives every cached line one of three states:

The whole protocol exists to hold one invariant:

Single-Writer-OR-Multiple-Readers (SWMR): at any instant a line is either in M in exactly one cache (one writer, no other copies), or in S in zero or more caches (many readers, no writer). Never a writer beside another copy.

A plain valid bit cannot express this — it says "I have a copy" but not "am I allowed to write it" or "must I tell anyone before I do." MSI's states carry exactly that missing information.

6. Engineering Mental Model — a permission token

Think of one line as a token passed around the SoC:

• I — you do not hold the token. You may not touch the data.
• S — you hold a read-only photocopy. Others may hold identical photocopies. Nobody may edit.
• M — you hold the single master original, and you may edit it. To hold it, every photocopy elsewhere had to be shredded first.

A store requires the master original: if you only have a photocopy (S), you must first invalidate every other copy to upgrade to M. A peer wanting to read forces you to hand back a clean copy (M → S); a peer wanting to write forces you to surrender entirely (M → I or S → I). This "one master or many photocopies" rule is SWMR.

7. Engineering Diagram — the MSI state machine

Two families of events drive the machine. Local events (this core's load or store) are what the pipeline requests. Snoop events arrive from the Home Node because another core requested the line. A correct cache reacts to both; ignoring snoops is how SWMR breaks.

8. Worked Example — CPU0 and CPU1 on line A

Run the two-core system from Module 1. Both caches start with line A Invalid; memory holds A = 5.

Notice what never happens: at no step do two caches hold write permission at once. Step 3 is the key move — CPU0 cannot just edit its S copy; it must invalidate CPU1 first, then enter M. That single rule is what stopped the lost-update race of Chapter 1.2.

9. Transaction Walkthrough — the store in Step 3, end to end

MSI describes states; the CHI cast moves the messages. Here is Step 3 (CPU0's store while in S) mapped onto the path Module 1 previewed. This is representative behavioral flow, not a byte-level CHI trace.

1. CPU0 pipeline → RN0. The store to A misses write permission (state is S). Sender: core. Purpose: request an upgrade to writable. Stall risk: none yet.
2. RN0 → Home Node (request channel). RN0 issues a "make-writable" request for A. Sender: RN0. Receiver: the one HN that owns A's address range. The HN is the serialization point: if CPU1 also races for A, the HN picks one order.
3. HN directory lookup. The HN checks who holds A. Stored info: sharer list / owner. It finds CPU1 in S. Event that changes state: the HN decides to grant CPU0 and evict CPU1.
4. HN → RN1 (snoop channel): invalidate. Purpose: remove CPU1's copy so CPU0 can be the single writer. RN1 moves S → I and acknowledges. Stall risk: CPU0's grant waits on this acknowledgement — forward progress depends on the snoop completing.
5. HN → RN0 (response): grant + data if needed. CPU0 already had data (it was in S), so only permission is granted. Directory now records CPU0 as owner (M).
6. RN0 completes; line becomes M. CPU0 writes 6. Completion = CPU0 reached M with peers invalidated. Visibility to CPU1 happens later, at Step 4, when CPU1's read is snooped and CPU0 supplies the new value. These are different events at different times.

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

A representative single-line MSI tracker. It takes this core's request (req_load / req_store) and the snoops the HN forwards (snoop_read / snoop_inval), and outputs the coherence state, the actions the cache must drive, and the read/write permissions the pipeline may use. It is behavioral and simplified: one event per cycle, one line, no data path, no credit flow.

// Representative single-line MSI coherence tracker (educational, not CHI RTL).
// State: I=00 (no copy), S=01 (read-only), M=10 (owner, writable, dirty).
module msi_line_tracker (
  input  logic       clk,
  input  logic       rst_n,
  // Local CPU request for THIS line (at most one asserted per cycle).
  input  logic       req_load,     // local read
  input  logic       req_store,    // local write
  // Remote snoops forwarded by the Home Node for THIS line.
  input  logic       snoop_read,   // a peer wants a shared (read) copy
  input  logic       snoop_inval,  // a peer wants to write / read-exclusive
  output logic [1:0] state,
  // Actions this cache must drive on the fabric.
  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 leaving M
  // Permissions the pipeline consumes.
  output logic       can_read,
  output logic       can_write
);
  localparam logic [1:0] I = 2'b00, S = 2'b01, M = 2'b10;
  logic [1:0] next;
 
  always_comb begin
    next          = state;
    do_busread    = 1'b0;
    do_invalidate = 1'b0;
    do_writeback  = 1'b0;
    // Snoops take priority: an external agent is changing our rights.
    if (snoop_inval) begin
      if (state == M) do_writeback = 1'b1; // must not lose the newest copy
      next = I;                            // surrender the line
    end
    else if (snoop_read) begin
      if (state == M) begin
        do_writeback = 1'b1;               // supply newest data to the reader
        next         = S;                  // downgrade owner to sharer
      end
    end
    else if (req_store) begin
      if (state != M) begin
        if (state == I) do_busread = 1'b1; // true write miss: fetch first
        do_invalidate = 1'b1;              // upgrade: remove peer copies
      end
      next = M;                            // single writer
    end
    else if (req_load) begin
      if (state == I) do_busread = 1'b1;   // read miss: fetch a shared copy
      next = (state == M) ? M : S;         // M stays M; I or S becomes S
    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 MSI tracker (Verilog-2001).
module msi_line_tracker (
  input            clk,
  input            rst_n,
  input            req_load,
  input            req_store,
  input            snoop_read,
  input            snoop_inval,
  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, M = 2'b10;
  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
    end else if (req_store) begin
      if (state != M) begin
        if (state == I) do_busread = 1'b1;
        do_invalidate = 1'b1;
      end
      next = M;
    end else if (req_load) begin
      if (state == I) do_busread = 1'b1;
      next = (state == M) ? M : S;
    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 MSI tracker (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity msi_line_tracker is
  port (
    clk, rst_n              : in  std_logic;
    req_load, req_store     : in  std_logic;
    snoop_read, snoop_inval : 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 msi_line_tracker is
  constant I : std_logic_vector(1 downto 0) := "00";
  constant S : std_logic_vector(1 downto 0) := "01";
  constant M : std_logic_vector(1 downto 0) := "10";
  signal cur, nxt : std_logic_vector(1 downto 0);
begin
  comb : process(cur, req_load, req_store, snoop_read, snoop_inval)
  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; end if;
    elsif req_store = '1' then
      if cur /= M then
        if cur = I then do_busread <= '1'; end if;
        do_invalidate <= '1';
      end if;
      nxt <= M;
    elsif req_load = '1' then
      if cur = I then do_busread <= '1'; end if;
      if cur = M then nxt <= M; else nxt <= S; 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: snoop priority, upgrade-before-write, writeback-before-losing-M.

11. Timing View — the two-core sequence

The MSI states of line A across the Section 8 sequence. Timing is representative — real CHI latencies depend on the interconnect and are not fixed cycle counts.

Read the invariant straight off the figure: whenever one row shows M, the other shows I — never two writers.

12. Verification View — proving SWMR

Two levels of check. First, a module-local assertion: write permission implies the Modified state. A cache must never write a line it only shares.

// Bind to msi_line_tracker. Write permission exists only in Modified.
property p_write_only_in_M;
  @(posedge clk) disable iff (!rst_n) can_write |-> (state == 2'b10);
endproperty
assert property (p_write_only_in_M);
 
// Leaving Modified must flush the dirty copy — never lose the newest value.
property p_no_silent_loss;
  @(posedge clk) disable iff (!rst_n)
    (state == 2'b10) && (snoop_inval || snoop_read) |-> do_writeback;
endproperty
assert property (p_no_silent_loss);

Second, the SWMR invariant is a system property — it spans every cache — so it lives in a scoreboard or a directory reference model, not in one module:

For each line, count caches in M and caches in S. Assert (mCount <= 1) and not (mCount == 1 and sCount > 0) on every settled cycle.

• What it proves: no two writers, and no writer beside a reader — the coherence backbone.
• What it does not prove: cross-address consistency (memory ordering, Module 12), forward progress, or CHI wire-level compliance. One passing assertion is not a compliant CHI implementation.
• Bug signature when it fails: mCount == 2 after a store that skipped invalidation, or mCount == 1 and sCount >= 1 after an upgrade that did not evict sharers — a lost update or a stale read soon follows.

13. Testbench — drive the sequence, check states and actions

Deterministic stimulus. Each event's actions are sampled while the inputs are asserted (before the clock edge); the resulting state is checked after the edge — no sampling race.

module tb_msi_line_tracker;
  logic clk = 0, rst_n;
  logic req_load, req_store, snoop_read, snoop_inval;
  logic [1:0] state;
  logic do_busread, do_invalidate, do_writeback, can_read, can_write;
  int errors = 0;
 
  msi_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,
                    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;
    #1;                                   // combinational actions valid now
    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;                   // state updates on the edge
    req_load = 0; req_store = 0; snoop_read = 0; snoop_inval = 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, 2'b00, 0,0,0, "reset");
    rst_n = 1;
    // Normal path: I -> S -> M -> S -> I
    ev(1,0,0,0, 2'b01, 1,0,0, "load: I->S (fetch shared)");
    if (can_write) begin errors++; $display("FAIL: writable while Shared"); end
    ev(0,1,0,0, 2'b10, 0,1,0, "store: S->M (upgrade, invalidate peers)");
    if (!can_write) begin errors++; $display("FAIL: not writable in Modified"); end
    ev(0,0,1,0, 2'b01, 0,0,1, "peer read: M->S (writeback)");
    ev(0,0,0,1, 2'b00, 0,0,0, "peer store: S->I (invalidate)");
    // Corner 1: write miss from I must fetch AND invalidate.
    ev(0,1,0,0, 2'b10, 1,1,0, "store miss: I->M");
    // Corner 2: a peer store while Modified must write dirty data back.
    ev(0,0,0,1, 2'b00, 0,0,1, "peer store: M->I (no silent loss)");
 
    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: I->S (fetch shared)] state=1 actions br/iv/wb=1/0/0
PASS [store: S->M (upgrade, invalidate peers)] state=2 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 (invalidate)] state=0 actions br/iv/wb=0/0/0
PASS [store miss: I->M] state=2 actions br/iv/wb=1/1/0
PASS [peer store: M->I (no silent loss)] state=0 actions br/iv/wb=0/0/1
ALL TESTS PASSED

14. DebugLab — the store that skipped the upgrade

cyc  core  event   state->next  busread inval  wb
 4   CPU0  store    S -> M          0      0    0   <-- inval=0 while leaving Shared
 4   CPU1  (S copy still valid, never snooped)
 6   CPU1  store    S -> M          0      0    0

15. Common Mistakes

• Treating Shared as writable. Assumption: a valid copy means write permission. Bug: SWMR violation and lost updates (the DebugLab). Prevention: a store from S is always an upgrade that invalidates peers first.
• Forgetting writeback on M → S or M → I. Assumption: memory already has the data. Bug: the newest value is dropped; peers and memory read stale data. Prevention: leaving M always flushes; assert do_writeback on those transitions.
• Believing memory holds the newest copy. Assumption: a read from memory is authoritative. Bug: when the line is M elsewhere, memory is stale (this is why plain AXI cannot be coherent). Prevention: route reads through the Home Node, which snoops the owner.
• Ignoring snoops while a local request is in flight. Assumption: my request has priority. Bug: deadlock or duplicate ownership when a peer's snoop is dropped. Prevention: service snoops (often with priority) even while a local miss is outstanding.
• Mistaking MSI for the CHI state set. Assumption: this three-state table is the specification. Bug: confusion when CHI's actual states appear. Prevention: treat MSI as the conceptual base; CHI's coherence states and directory come in later modules.

16. Engineering Checklist

• Every cached line carries a coherence state, not just a valid bit.
• A store from S performs an upgrade (invalidate peers) before entering M.
• Leaving M (to S or I) always issues a writeback — no silent loss.
• A load miss from I fetches a Shared copy; write permission is never implied.
• Snoops are serviced even with a local miss outstanding.
• An assertion enforces can_write only in M; a scoreboard enforces system SWMR.

17. Key Takeaways

• MSI is the smallest complete coherence machine: M, S, I, enforcing single-writer-or-multiple-readers.
• M owns the newest, dirty copy and must write it back; S is a clean read-only copy; I is nothing.
• A store from S is an upgrade, not a hit — it must invalidate peers first.
• Serialization (Home Node), ownership (M), completion (state reached), and visibility (peer snoop) are four distinct events.
• MSI here is representative and behavioral — the foundation MESI, MOESI, and CHI's own states build on.

18. Quick Revision

MSI. Three per-line states: M (owner, writable, dirty — memory stale), S (read-only, shareable, clean), I (no copy). Invariant: SWMR — one M or many S, never both. Load miss: I → S (fetch). Store: reach M; from I fetch + invalidate, from S upgrade (invalidate peers). Snoop read: M → S with writeback. Snoop invalidate: S/M → I, writeback if M. Memory is not always newest. Representative model, not the CHI spec state set.

Coming Next

Chapter 2.2 — MESI Protocol. MSI forces a wasteful broadcast every time a core writes a line it already shares, even when it is the only holder. MESI adds an Exclusive state — a clean line held by exactly one cache — so a later store can enter Modified silently, with no invalidation traffic. Same SWMR backbone, one new state, a real bandwidth win.