Reading State-Transition Tables

Module 2 · Chapter 2.9 · Coherency Protocol Foundations

Project thread — you have the protocols and the machinery. This chapter is the reading skill: the table notation every coherence spec — including CHI's — uses. 2.10 then applies it to compare protocols on one scenario.

1. Learning Outcomes

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

• Explain the structure of a state-transition table: rows, columns, and the two halves of a cell.
• Distinguish local (processor) events from remote (snoop) events when reading a column.
• Trace a protocol path — a sequence of transitions — by reading cells in order.
• Convert between a state-transition table and its equivalent state diagram.
• Implement a table-driven FSM that encodes the table as a lookup, in SystemVerilog, Verilog-2001, and VHDL.
• Verify that the hardware's transitions match the documented table, cell for cell.

2. Why Should I Learn This?

Every coherence protocol you will ever implement or debug is specified as a table. The CHI specification documents its coherence states and their transitions in exactly this form; so do the textbook MSI/MESI/MOESI protocols and any custom controller. If you cannot read a transition table fluently, the spec is a wall.

The skill is also directly practical: a transition table maps almost one-to-one onto RTL — a case on the current state and event, or a lookup ROM. Reading the table is half of writing the controller, and a single misread cell is a coherency bug.

3. Key Terms

4. Previous Chapter Connection

Chapters 2.1–2.8 built the protocols and the machinery — states, ownership, dirty data, invalidations, snoops. Every one of those was, implicitly, a table: "in this state, on this event, go here and do this."

This chapter makes the notation explicit. Rather than adding a new mechanism, it teaches how to read the ones you have — because the CHI spec, and any protocol you meet, hands you its behavior as a table, and fluency with that table is the difference between decoding a spec and guessing at it.

5. Core Concept — rows, columns, cells

A state-transition table specifies a machine as a matrix. Here is MSI (from 2.1) in full — three states, three events:

Read it in three moves:

1. Pick the row — your current state (say, S).
2. Pick the column — the event that just happened (say, a local Store).
3. Read the cell — → M / issue invalidate: move to Modified, and issue an invalidate to peers.

Each cell has two halves: the next state (after the arrow) and the action (after the slash). Missing the action half is the classic misread — the next state alone is not enough; the M / writeback cell tells you the state and that you must flush dirty data.

Note the two kinds of columns. Load and Store are local events — this core's own requests. Snoop-Invalidate is a remote event — triggered by another core's write. Reading a table means knowing, for each column, whether the event is your own or a peer's; they drive very different behavior.

6. Engineering Mental Model — a decision grid

A transition table is a decision grid, like a tax table or a chess opening book.

• You never read the whole grid — you index into it: "I am here (row) and this happened (column), so I do that (cell)."
• The grid is complete: every state you can be in has a row, every event you can see has a column, so there is always exactly one cell to read.
• Each answer has two parts — where you end up, and what you must do on the way — and skipping the second part is how mistakes happen.

The FSM diagram is the same grid drawn as a map instead of a spreadsheet: states are places, cells are the roads between them. Two views, one machine.

7. Engineering Diagram — the same table, drawn

Trace the correspondence: the table cell (S, Store) → M / invalidate is exactly the S → M arc labelled "store / invalidate". Every filled cell is an arc; every arc is a cell. Use the table to look up one situation precisely; use the diagram to see the reachable shape of the whole machine.

8. Worked Example — reading three cells

Read three cells of the MSI table in full, action included.

• (I, Load) → S / issue bus-read. Current Invalid, a local load: fetch a shared copy from the fabric (the action) and move to Shared. Without the action, you would move to Shared with no data — the action is what makes the state legal.
• (S, Store) → M / issue invalidate. Current Shared, a local store: this is an upgrade (2.1). The action — issue an invalidate to peers — is mandatory; move to Modified only after it. A reader who takes only the next state (M) and skips the invalidate has written the DebugLab of 2.1.
• (M, Snoop-Invalidate) → I / writeback. Current Modified, a peer wants to write: the action is a writeback (the line is dirty, 2.6), then go Invalid. The writeback half is the whole safety of the cell.

Now convert a cell to an arc: (S, Snoop-Invalidate) → I / — becomes the diagram's S → I arc labelled "snoop-inval", with no action annotation because the action half is a dash. Reading fluently is this loop — cell to behavior, cell to arc — done without hesitation.

9. Transaction Walkthrough — following a path

A protocol path is a sequence of cells read in order. Trace line A through CPU0 as events arrive; each step is one table lookup.

1. Start: I. CPU0 holds nothing.
2. Event: local Load. Row I, column Load → S / bus-read. CPU0 issues a bus-read, installs the line Shared.
3. Event: local Store. Row S, column Store → M / invalidate. CPU0 issues an invalidate to peers, moves to Modified, and writes.
4. Event: Snoop-Invalidate (a peer writes A). Row M, column Snoop-Invalidate → I / writeback. CPU0 writes back its dirty data, then goes Invalid.

Path: I → S → M → I, four cells, each read the same way — row, column, next-state, action. Any behavior a protocol can produce is just a path through its table; debugging one is finding the cell where reality and the table diverged.

10. RTL / Hardware View — the table as a lookup

A transition table maps almost directly to hardware: index a ROM by the current state and the event, and read out the next state and action. This table-driven FSM is the MSI table of Section 5, one ROM entry per cell. Behavioral and simplified: one event per cycle, single action per cell.

// Representative table-driven FSM — the MSI transition table encoded as a ROM
// (educational, not the CHI spec). Index = {state, event} -> {next, action}.
module table_driven_fsm (
  input  logic       clk,
  input  logic       rst_n,
  input  logic       ev_valid,
  input  logic [1:0] event_in,   // LOAD=00, STORE=01, SNOOP_INV=10
  output logic [1:0] state,      // I=00, S=01, M=10
  output logic [1:0] action      // NONE=00, BUSRD=01, INVAL=10, WB=11
);
  // The transition table as data: TABLE[{state, event}] = {next[1:0], action[1:0]}.
  // Every entry is one cell of the Section 5 table.
  logic [3:0] TABLE [0:15];
  initial begin
    TABLE[{2'b00,2'b00}] = {2'b01,2'b01}; // I , LOAD  -> S , BUSRD
    TABLE[{2'b00,2'b01}] = {2'b10,2'b10}; // I , STORE -> M , INVAL
    TABLE[{2'b00,2'b10}] = {2'b00,2'b00}; // I , SNOOP -> I , NONE
    TABLE[{2'b01,2'b00}] = {2'b01,2'b00}; // S , LOAD  -> S , NONE
    TABLE[{2'b01,2'b01}] = {2'b10,2'b10}; // S , STORE -> M , INVAL
    TABLE[{2'b01,2'b10}] = {2'b00,2'b00}; // S , SNOOP -> I , NONE
    TABLE[{2'b10,2'b00}] = {2'b10,2'b00}; // M , LOAD  -> M , NONE
    TABLE[{2'b10,2'b01}] = {2'b10,2'b00}; // M , STORE -> M , NONE
    TABLE[{2'b10,2'b10}] = {2'b00,2'b11}; // M , SNOOP -> I , WB
  end
 
  logic [3:0] entry;
  assign entry  = TABLE[{state, event_in}];
  assign action = ev_valid ? entry[1:0] : 2'b00;
 
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n)         state <= 2'b00;        // I
    else if (ev_valid)  state <= entry[3:2];   // next-state, straight from the table
endmodule

The same behavior in Verilog-2001:

// Representative table-driven FSM (Verilog-2001). ROM = the MSI table.
module table_driven_fsm (
  input            clk,
  input            rst_n,
  input            ev_valid,
  input      [1:0] event_in,
  output reg [1:0] state,
  output     [1:0] action
);
  reg [3:0] rom [0:15];
  initial begin
    rom[{2'b00,2'b00}] = 4'b0101; // I,LOAD  -> S,BUSRD
    rom[{2'b00,2'b01}] = 4'b1010; // I,STORE -> M,INVAL
    rom[{2'b00,2'b10}] = 4'b0000; // I,SNOOP -> I,NONE
    rom[{2'b01,2'b00}] = 4'b0100; // S,LOAD  -> S,NONE
    rom[{2'b01,2'b01}] = 4'b1010; // S,STORE -> M,INVAL
    rom[{2'b01,2'b10}] = 4'b0000; // S,SNOOP -> I,NONE
    rom[{2'b10,2'b00}] = 4'b1000; // M,LOAD  -> M,NONE
    rom[{2'b10,2'b01}] = 4'b1000; // M,STORE -> M,NONE
    rom[{2'b10,2'b10}] = 4'b0011; // M,SNOOP -> I,WB
  end
 
  wire [3:0] entry = rom[{state, event_in}];
  assign action = ev_valid ? entry[1:0] : 2'b00;
 
  always @(posedge clk or negedge rst_n)
    if (!rst_n)        state <= 2'b00;
    else if (ev_valid) state <= entry[3:2];
endmodule

And in VHDL:

-- Representative table-driven FSM (VHDL). The constant array is the MSI table.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity table_driven_fsm is
  port (
    clk, rst_n : in  std_logic;
    ev_valid   : in  std_logic;
    event_in   : in  std_logic_vector(1 downto 0);  -- LOAD=00 STORE=01 SNOOP=10
    state      : out std_logic_vector(1 downto 0);  -- I=00 S=01 M=10
    action     : out std_logic_vector(1 downto 0)   -- NONE=00 BUSRD=01 INVAL=10 WB=11
  );
end entity;
 
architecture rtl of table_driven_fsm is
  type rom_t is array (0 to 15) of std_logic_vector(3 downto 0);
  -- index = state*4 + event ; entry = next(3..2) & action(1..0)
  constant TAB : rom_t := (
    0  => "0101",  -- I,LOAD  -> S,BUSRD
    1  => "1010",  -- I,STORE -> M,INVAL
    2  => "0000",  -- I,SNOOP -> I,NONE
    4  => "0100",  -- S,LOAD  -> S,NONE
    5  => "1010",  -- S,STORE -> M,INVAL
    6  => "0000",  -- S,SNOOP -> I,NONE
    8  => "1000",  -- M,LOAD  -> M,NONE
    9  => "1000",  -- M,STORE -> M,NONE
    10 => "0011",  -- M,SNOOP -> I,WB
    others => "0000"
  );
  signal cur   : std_logic_vector(1 downto 0) := "00";
  signal entry : std_logic_vector(3 downto 0);
  signal idx   : integer range 0 to 15;
begin
  idx    <= to_integer(unsigned(cur)) * 4 + to_integer(unsigned(event_in));
  entry  <= TAB(idx);
  action <= entry(1 downto 0) when ev_valid = '1' else "00";
 
  process(clk, rst_n)
  begin
    if rst_n = '0' then cur <= "00";
    elsif rising_edge(clk) then
      if ev_valid = '1' then cur <= entry(3 downto 2); end if;
    end if;
  end process;
 
  state <= cur;
end architecture;

All three make the point directly: the state-transition table is not just documentation — it is the machine, and here it is literally the ROM the controller reads.

11. Verification View — the hardware matches the table

Two properties confirm the RTL implements the documented table.

// Bind to table_driven_fsm. States: I=00, S=01, M=10 (11 is never reached).
// 1. The state is always a legal MSI state — never the unused encoding.
property p_legal_state;
  @(posedge clk) disable iff (!rst_n) (state != 2'b11);
endproperty
assert property (p_legal_state);
 
// 2. Spot-check documented cells: a store from Shared upgrades to Modified
//    with the invalidate action.
property p_cell_S_store;
  @(posedge clk) disable iff (!rst_n)
    (state == 2'b01 && ev_valid && event_in == 2'b01)
      |-> (action == 2'b10) ##1 (state == 2'b10);
endproperty
assert property (p_cell_S_store);
 
// 3. A snoop-invalidate from Modified writes back, then goes Invalid.
property p_cell_M_snoop;
  @(posedge clk) disable iff (!rst_n)
    (state == 2'b10 && ev_valid && event_in == 2'b10)
      |-> (action == 2'b11) ##1 (state == 2'b00);
endproperty
assert property (p_cell_M_snoop);

The system invariant is a reference-model rule:

For every (state, event) the hardware visits, the (next-state, action) it produces equals the spec table's cell. A reference model that holds the canonical table can check the RTL cell for cell.

• What it proves: the implemented machine is exactly the documented table — no transcription drift.
• What it does not prove: that the table itself is correct coherence (that is the protocol's job, 2.1–2.4), nor that omitted transient states are handled (2.7), nor cross-line ordering (Module 12).
• Bug signature when it fails: an action or next-state that disagrees with the table for some cell — a mis-encoded ROM entry (the DebugLab).

12. Testbench — walk the documented path

Deterministic stimulus; the combinational action is sampled while the event is asserted.

module tb_table_driven_fsm;
  logic clk = 0, rst_n;
  logic ev_valid;
  logic [1:0] event_in, state, action;
  int errors = 0;
 
  table_driven_fsm dut (.*);
  always #5 clk = ~clk;
 
  localparam logic [1:0] LOAD = 2'b00, STORE = 2'b01, SNOOP = 2'b10;
 
  task automatic ev(input logic [1:0] e, input logic [1:0] exp_action, exp_next, input string tag);
    logic [1:0] act;
    ev_valid = 1; event_in = e;
    #1;
    act = action;                              // combinational, valid this cycle
    if (act !== exp_action) begin
      errors++; $display("FAIL [%s] action=%b exp=%b", tag, act, exp_action);
    end
    @(posedge clk); #1;
    ev_valid = 0;
    if (state !== exp_next) begin
      errors++; $display("FAIL [%s] state=%b exp=%b", tag, state, exp_next);
    end else
      $display("PASS [%s] state=%b action=%b", tag, state, act);
  endtask
 
  initial begin
    rst_n = 0; @(posedge clk); rst_n = 1;
    // Path I -> S -> M -> I, reading one documented cell per step.
    ev(LOAD,  2'b01, 2'b01, "I,LOAD  -> S / BUSRD");
    ev(STORE, 2'b10, 2'b10, "S,STORE -> M / INVAL");
    ev(SNOOP, 2'b11, 2'b00, "M,SNOOP -> I / WB");
    // Back in I: a snoop does nothing.
    ev(SNOOP, 2'b00, 2'b00, "I,SNOOP -> I / NONE");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS [I,LOAD  -> S / BUSRD] state=01 action=01
PASS [S,STORE -> M / INVAL] state=10 action=10
PASS [M,SNOOP -> I / WB] state=00 action=11
PASS [I,SNOOP -> I / NONE] state=00 action=00
ALL TESTS PASSED

13. DebugLab — one mis-transcribed cell

cell (S, SNOOP_INVALIDATE)
  canonical table:  -> I / NONE     (drop the copy)
  ROM entry:        -> S / NONE     (!) next-state mis-transcribed as S
trace: peer writes A -> this cache stays S -> later read returns stale A

14. Common Mistakes

• Reading only the next state. Assumption: the cell is just where you go. Bug: the action (invalidate, writeback, bus-read) is skipped — a lost update or a missing fetch. Prevention: every cell has two halves; read both.
• Confusing local and remote columns. Assumption: all columns are this core's events. Bug: treating a peer's snoop like a local request, or vice versa. Prevention: label each column local or remote before reading.
• Misreading a dash as impossible (or the reverse). Assumption: a blank cell means it cannot happen. Bug: hiding a real "no-action" transition, or handling an impossible one. Prevention: distinguish "no action" from "cannot occur".
• Ignoring transient states. Assumption: transitions are atomic. Bug: reading a collapsed teaching table as if a real controller had no wait states. Prevention: expect transient rows in a full spec; they are the handshakes.
• Transcribing a cell wrong. Assumption: copying the table is mechanical. Bug: one wrong next-state or action is a coherency break (the DebugLab). Prevention: cross-check every ROM/case entry against the canonical table.
• Treating a teaching table as the full CHI spec. Assumption: three states and three events are the whole story. Bug: the real spec has more states, events, and transient rows. Prevention: this is the reading skill; the complete CHI table is Modules 5 and 9.

15. Engineering Checklist

• Every state has a row and every event a column — indexing always lands on one cell.
• Each cell is read as two halves: next state and action.
• Each column is identified as a local or remote event before use.
• A dash (no action) is distinguished from an impossible cell.
• The table and the state diagram are treated as the same machine, converted freely.
• Every implemented cell (ROM/case entry) is cross-checked against the canonical table.

16. Key Takeaways

• A state-transition table is rows (current state) × columns (events) with cells of next-state + action.
• Local (load/store) and remote (snoop) events drive different behavior — read the column type first.
• The action half of a cell is load-bearing: skipping it drops invalidates, writebacks, and fetches.
• A table and a state diagram are the same machine — every filled cell is an arc.
• The table maps almost directly to hardware — a case or a lookup ROM — so reading it is half of writing the controller.
• These tables are representative — the reading skill, not the complete CHI specification.

17. Quick Revision

Reading transition tables. A matrix: rows = current state, columns = events, cell = next-state / action. To read: pick the row (state), the column (event), read the cell — both halves. Columns are local (load, store) or remote (snoop) events — they behave differently. A dash means "no action" (a real transition); an impossible cell means it cannot occur — not the same. A protocol path is a sequence of cells (I → S → M → I). Table and state diagram are the same machine; every filled cell is an arc. The table maps to a case or a lookup ROM — one mis-transcribed cell is a coherency bug. Representative model, not the complete CHI spec.

Coming Next

Chapter 2.10 — Real Coherency Examples. With the protocols built and their tables readable, the next chapter puts them side by side: one producer-consumer scenario traced through MSI, MESI, and MOESI at once, so you can see exactly where the Exclusive and Owned states change the traffic and the timing — the module's capstone comparison before CHI itself begins in Module 3.