State Transitions

Module 10 · Chapter 10.2 · Cache State Management

Project thread — 10.1 defined the five states. This chapter connects them into the transition graph the cache controller runs. 10.3 focuses on ownership at each moment.

1. Learning Outcomes

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

• Describe the state transitions as a directed graph over UC, UD, SC, SD, I.
• Distinguish the two sources of transitions — local actions and remote snoops.
• State the rules: write only from a unique state; snoops handled from every valid state.
• Explain why the transition table must be total — defined for every state-and-event pair.
• Diagnose the coherence bug a missing table entry creates.
• Implement a representative next-state function in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

The states are static; the transitions are the protocol in motion. A cache controller is a state machine, and its correctness is exactly the correctness of its transition table — which state a line moves to for every event it can receive. Every flow in Module 8 and every snoop in Module 9 was a walk through this graph. To implement or verify a cache, you build this table, and its bugs are coherence bugs.

The subtlety unique to transitions is that they arrive from two independent directions. A line changes state because this cache did something (a local read, write, or eviction) or because another cache did something that snooped it. Both must be handled, from every state — and the temptation to handle only the "obvious" cases leaves holes. A transition table with a hole is not a cosmetic gap; it is a state-and-event combination that will eventually occur and send a line somewhere undefined. Understanding transitions means understanding that the table must be complete.

3. Key Terms

4. Previous Chapter Connection

Chapter 10.1 laid out the five states on two axes and read each one's permissions and obligations. It was a static picture — the grid, not the moves.

This chapter adds the edges. Each flow you traced earlier is a path through this graph: ReadShared is I → SC; ReadUnique is I → UC; a write is UC → UD; WriteBack is UD → I; SnpShared is any → SC; SnpUnique is any → I. The permissions from 10.1 become the rules on the edges — a write edge exists only from unique states, because only unique states may write. So 10.2 turns the grid into the directed graph the controller implements, and pins down which edges are legal and from where.

5. Core Concept — two sources of transitions, and a total table

A cache line's state changes for one of two reasons, and the transition table must cover both, exhaustively.

• Local actions. This cache acts on the line: a read brings it in (I → SC or UC), a write on a unique line makes it dirty (UC → UD), an eviction drops it (UD/SD → I with writeback; UC/SC → I silently).
• Remote snoops. Another cache's request reaches this line through the home: SnpShared downgrades it (any valid → SC), SnpUnique invalidates it (any valid → I). These arrive unbidden — the cache did not initiate them.
• Write is unique-only. A write transition exists only from a unique state (UC, UD). A shared line (SC, SD) cannot go directly to UD; it must first upgrade (MakeUnique / ReadUnique), which invalidates the other sharers. No silent SC → UD.
• Snoops apply from every state. A snoop must be handled from any valid state — SnpUnique invalidates UC, UD, SC, and SD. Leaving any state unhandled is a hole.

The synthesis:

Transitions come from local actions (this cache reads/writes/evicts) and remote snoops (another cache's request reaches in). The transition table must be total — every (state, event) pair defined. Two rules shape it: write is legal only from a unique state (shared lines upgrade first), and snoops are handled from every valid state. A missing entry is a latent coherence bug waiting for its combination to occur.

6. Engineering Mental Model — a status board updated by two hands

Picture a shared status board tracking one item, updated by two kinds of event.

• You update it when you act: you check the item out, mark it edited, return it. Those are your local transitions.
• Others update it too: someone with authority sends a notice — "downgrade your hold" or "release it entirely" — and the board must change to match. Those are the snoops.
• The board's rulebook must cover every situation: for each current status and each possible notice, what the new status is. If the rulebook says nothing about "release it entirely while you had it edited-and-shared," then when that exact situation arises, whoever is updating the board guesses — and the board goes wrong.

A good rulebook has no blank cells: every status crossed with every event has an answer. That completeness is what keeps the board trustworthy no matter which of the two hands writes to it.

7. Engineering Diagram — the transition graph

Read the edges by their trigger: readUnique and read are local fetches out of I; write and own dirty are local changes in place; SnpShared, SnpUnique, and evict return a line toward the top or to I. Two kinds of arrow — local and snoop — into one graph.

8. The Transition Table

The transitions, organized by trigger. (Dirty states also forward or write back their data — Chapter 9.3.)

The rule to carry: local rows are initiated by this cache; remote rows arrive from another. A write row exists only from unique states — a shared line must take the Upgrade row first. And the snoop rows say any valid — they must be defined from UC, UD, SC, and SD alike. The table is read as for this state and this event, go here — and every cell must have an entry.

9. Local versus Snoop Transitions — the two drivers

The two sources behave differently, and both must be handled.

• Local transitions are chosen. The cache decides to read, write, or evict, so it controls when they happen and can prepare (e.g., issue an upgrade before writing a shared line).
• Snoop transitions are imposed. They arrive because another cache acted; this cache must respond whatever its current state. It cannot refuse a SnpUnique.
• Snoops must cover every state. Because a snoop can arrive in any state, the table's snoop rows must be total over states — no state is exempt from being snooped.
• The two can interact. A local action in flight and an incoming snoop to the same line must be reconciled (the home orders them, Chapter 7.6) — but each, individually, must still have a defined transition.

The point to carry:

The two drivers demand different mindsets. Local transitions you initiate, so you can gate them on preconditions — the write edge is unique-only precisely because the cache upgrades first. Snoop transitions are handed to you, so you must accept them from wherever you are — which is why the snoop rows must be complete over all states. A table that handles local actions carefully but leaves a snoop unhandled in some state has covered the easy half and left the hard half open, because the unhandled snoop will arrive whether the table is ready or not.

10. Reading the Table — a line's journey

Follow one line through a sequence of events.

1. I, local read. A read brings the line in shared: I → SC. The cache now holds a read-only copy.
2. SC, local write intent. The cache wants to write, but SC is not writable. It takes the Upgrade row: SC → UC (MakeUnique invalidates the other sharers), then UC → UD on the write.
3. UD, remote SnpShared. Another core issues a ReadShared; the snoop arrives: UD → SC, and the cache forwards its dirty data (PassDirty). It is now a shared, clean sharer.
4. SC, remote SnpUnique. A third core issues a ReadUnique; the snoop invalidates: SC → I. The line is gone.
5. I again. Back to the start; the journey can repeat.

Every step was a table lookup — (current state, event) → next state — mixing local actions (steps 1–2) and remote snoops (steps 3–4). The line never landed anywhere undefined, because every cell it hit had an entry.

11. RTL / Hardware View — a next-state function

The controller's core is a next-state function: given the current state and the event, produce the next state and whether the transition is legal. Representative and combinational.

// Representative cache-state next-state function (educational).
// Events come from LOCAL actions (READ, READUNIQUE, WRITE, EVICT) and REMOTE
// snoops (SNP_SHARED, SNP_UNIQUE). Write is legal only from a UNIQUE state; snoops
// are handled from EVERY valid state. 'legal' flags a permitted transition.
module chi_next_state (
  input  logic [2:0] cur_state,   // I, UC, UD, SC, SD
  input  logic [2:0] event_in,    // READ, READUNIQUE, WRITE, EVICT, SNP_SHARED, SNP_UNIQUE
  output logic [2:0] next_state,
  output logic       legal        // is this (state, event) a permitted move?
);
  localparam logic [2:0] I=3'd0, UC=3'd1, UD=3'd2, SC=3'd3, SD=3'd4;
  localparam logic [2:0] READ=3'd0, READUNIQUE=3'd1, WRITE=3'd2, EVICT=3'd3,
                         SNP_SHARED=3'd4, SNP_UNIQUE=3'd5;
 
  logic valid;
  assign valid = (cur_state != I);
 
  always_comb begin
    next_state = cur_state;   // default: stay
    legal      = 1'b0;
    case (event_in)
      READ:       if (cur_state == I)          begin next_state = SC;  legal = 1'b1; end
      READUNIQUE: if (cur_state == I)          begin next_state = UC;  legal = 1'b1; end
      // Write is legal ONLY from a unique state; shared must upgrade first.
      WRITE:      if (cur_state==UC || cur_state==UD) begin next_state = UD; legal = 1'b1; end
      EVICT:      if (valid)                    begin next_state = I;   legal = 1'b1; end
      // Snoops are handled from EVERY valid state (totality).
      SNP_SHARED: if (valid)                    begin next_state = SC;  legal = 1'b1; end
      SNP_UNIQUE: if (valid)                    begin next_state = I;   legal = 1'b1; end
      default: ;
    endcase
  end
endmodule

The same behavior in Verilog-2001:

// Representative cache-state next-state function (Verilog-2001).
module chi_next_state (
  input  [2:0] cur_state,
  input  [2:0] event_in,
  output reg [2:0] next_state,
  output reg       legal
);
  localparam I=3'd0, UC=3'd1, UD=3'd2, SC=3'd3, SD=3'd4;
  localparam READ=3'd0, READUNIQUE=3'd1, WRITE=3'd2, EVICT=3'd3,
             SNP_SHARED=3'd4, SNP_UNIQUE=3'd5;
 
  wire valid = (cur_state != I);
 
  always @* begin
    next_state = cur_state;
    legal      = 1'b0;
    case (event_in)
      READ:       if (cur_state == I)                  begin next_state = SC; legal = 1'b1; end
      READUNIQUE: if (cur_state == I)                  begin next_state = UC; legal = 1'b1; end
      WRITE:      if (cur_state==UC || cur_state==UD)  begin next_state = UD; legal = 1'b1; end
      EVICT:      if (valid)                           begin next_state = I;  legal = 1'b1; end
      SNP_SHARED: if (valid)                           begin next_state = SC; legal = 1'b1; end
      SNP_UNIQUE: if (valid)                           begin next_state = I;  legal = 1'b1; end
      default: ;
    endcase
  end
endmodule

And in VHDL:

-- Representative cache-state next-state function (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_next_state is
  port (
    cur_state  : in  std_logic_vector(2 downto 0);
    event_in   : in  std_logic_vector(2 downto 0);
    next_state : out std_logic_vector(2 downto 0);
    legal      : out std_logic
  );
end entity;
 
architecture rtl of chi_next_state is
  constant I  : std_logic_vector(2 downto 0) := "000";
  constant UC : std_logic_vector(2 downto 0) := "001";
  constant UD : std_logic_vector(2 downto 0) := "010";
  constant SC : std_logic_vector(2 downto 0) := "011";
  constant READ       : std_logic_vector(2 downto 0) := "000";
  constant READUNIQUE : std_logic_vector(2 downto 0) := "001";
  constant WRITE      : std_logic_vector(2 downto 0) := "010";
  constant EVICT      : std_logic_vector(2 downto 0) := "011";
  constant SNP_SHARED : std_logic_vector(2 downto 0) := "100";
  constant SNP_UNIQUE : std_logic_vector(2 downto 0) := "101";
  signal valid : boolean;
begin
  valid <= (cur_state /= I);
 
  process (cur_state, event_in, valid)
  begin
    next_state <= cur_state;
    legal      <= '0';
    case event_in is
      when READ       => if cur_state = I then next_state <= SC; legal <= '1'; end if;
      when READUNIQUE => if cur_state = I then next_state <= UC; legal <= '1'; end if;
      when WRITE      => if cur_state = UC or cur_state = UD then next_state <= UD; legal <= '1'; end if;
      when EVICT      => if valid then next_state <= I;  legal <= '1'; end if;
      when SNP_SHARED => if valid then next_state <= SC; legal <= '1'; end if;
      when SNP_UNIQUE => if valid then next_state <= I;  legal <= '1'; end if;
      when others     => null;
    end case;
  end process;
end architecture;

All three make write legal only from a unique state and handle snoops from every valid state — SnpUnique invalidates SC and SD as well as UC and UD. The DebugLab shows the coherence break when a snoop row leaves a state out.

12. Verification View — snoops total, write unique-only

The properties that keep the table sound: snoops apply from every valid state, and write is unique-only.

// Bind to chi_next_state.
// 1. SnpUnique invalidates EVERY valid state — no state is left unhandled.
property p_snp_unique_total;
  @(*) (event_in == 3'd5 /*SNP_UNIQUE*/ && cur_state != 3'd0 /*I*/)
       |-> (legal && next_state == 3'd0 /*I*/);
endproperty
 
// 2. SnpShared downgrades every valid state to SC.
property p_snp_shared_total;
  @(*) (event_in == 3'd4 /*SNP_SHARED*/ && cur_state != 3'd0)
       |-> (legal && next_state == 3'd3 /*SC*/);
endproperty
 
// 3. A write is legal only from a unique state — never a silent SC/SD -> UD.
property p_write_unique_only;
  @(*) (event_in == 3'd2 /*WRITE*/)
       |-> (legal == (cur_state == 3'd1 /*UC*/ || cur_state == 3'd2 /*UD*/));
endproperty

The system point, beyond the checks:

A transition table is a contract with every possible future: for any state the line reaches and any event that can arrive, the table promises a defined next state. The hard part is that snoops make the event set adversarial — you do not choose when a SnpUnique arrives or what state you are in when it does, so the table must answer for the whole cross-product, not the subset that happens in the common case. Verifying totality over the snoop rows is therefore not pedantry; it is checking that the contract has no gap an adversary (another core, at an inconvenient moment) can drive the line into. A table proven total cannot be surprised.

• What it proves: snoops are handled from every valid state; write is unique-only.
• What it does not prove: the accompanying data actions (forward/writeback) — those are Module 9.
• Bug signature: a snoop event in some valid state with legal low or the wrong next state — a hole.

13. Testbench — local and snoop transitions

Drives representative local and snoop events from several states and checks the next state and legality — including snoops from SD.

module tb_chi_next_state;
  logic [2:0] cur_state, event_in, next_state;
  logic legal;
  int errors = 0;
  localparam I=3'd0, UC=3'd1, UD=3'd2, SC=3'd3, SD=3'd4;
  localparam READ=3'd0, READUNIQUE=3'd1, WRITE=3'd2, EVICT=3'd3, SNP_SHARED=3'd4, SNP_UNIQUE=3'd5;
 
  chi_next_state dut (.*);
 
  task automatic check(input logic [2:0] s, e, exp_ns, input logic exp_legal, input string name);
    cur_state = s; event_in = e; #1;
    if (next_state !== exp_ns || legal !== exp_legal) begin
      errors++; $display("FAIL %s: next=%0d legal=%0b", name, next_state, legal);
    end else $display("PASS %s: next=%0d legal=%0b", name, next_state, legal);
  endtask
 
  initial begin
    check(I,  READ,       SC, 1'b1, "I  + read       -> SC");
    check(I,  READUNIQUE, UC, 1'b1, "I  + readUnique -> UC");
    check(UC, WRITE,      UD, 1'b1, "UC + write      -> UD");
    check(SC, WRITE,      SC, 1'b0, "SC + write      -> illegal (upgrade first)");
    check(UD, EVICT,      I,  1'b1, "UD + evict      -> I (writeback)");
    check(UC, SNP_SHARED, SC, 1'b1, "UC + SnpShared  -> SC");
    check(SD, SNP_UNIQUE, I,  1'b1, "SD + SnpUnique  -> I (total!)");
    check(SC, SNP_UNIQUE, I,  1'b1, "SC + SnpUnique  -> I");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS I  + read       -> SC: next=3 legal=1
PASS I  + readUnique -> UC: next=1 legal=1
PASS UC + write      -> UD: next=2 legal=1
PASS SC + write      -> illegal (upgrade first): next=3 legal=0
PASS UD + evict      -> I (writeback): next=0 legal=1
PASS UC + SnpShared  -> SC: next=3 legal=1
PASS SD + SnpUnique  -> I (total!): next=0 legal=1
PASS SC + SnpUnique  -> I: next=0 legal=1
ALL TESTS PASSED

14. DebugLab — a missing table entry

RN1 = SD (shared dirty owner, value = NEW)
RN0 ReadUnique -> HN sends SnpUnique to RN1
controller table: SnpUnique handled from UC, UD, SC -> I
                  NO entry for (SD, SnpUnique)  <-- hole
RN1 stays SD (or undefined) -> not invalidated, dirty NOT forwarded
RN0 becomes "unique" while RN1 still holds SD(NEW) -> two copies, stale

15. Common Mistakes

• A missing snoop entry. Assumption: rare states can be skipped. Bug: stale copy survives (the DebugLab). Prevention: snoops total over all states.
• Silent SC → UD. Assumption: holding a copy means writable. Bug: stale sharers. Prevention: write only from unique; upgrade first.
• Ignoring an incoming snoop. Assumption: local actions take priority. Bug: unhandled invalidation. Prevention: snoops always apply.
• Forgetting the data action on a transition. Assumption: state change is enough. Bug: dropped dirty data. Prevention: dirty transitions forward/writeback (Module 9).
• Not reconciling local vs snoop. Assumption: they never collide. Bug: a race. Prevention: the home orders same-line events (Chapter 7.6).
• An unreachable or extra edge. Assumption: more edges are safer. Bug: illegal moves. Prevention: only the legal transitions exist.

16. Engineering Checklist

• Build the table over both sources — local actions and remote snoops.
• Make it total — every event defined from every state.
• Allow write only from a unique state; require an upgrade from shared.
• Handle snoops from every valid state — including SD.
• Attach the correct data action to each dirty transition (forward / writeback).
• Verify legality — no illegal or silent transitions.

17. Key Takeaways

• The cache states form a directed graph; transitions are driven by local actions and remote snoops.
• Local transitions are chosen (read, write, evict); snoop transitions are imposed by other caches.
• Write is legal only from a unique state — a shared line must upgrade first.
• Snoops must be handled from every valid state — including SharedDirty.
• The transition table must be total; a missing entry is a latent coherence bug.
• Cover both sources, keep the table complete; the model here is representative.

18. Quick Revision

State transitions. The five cache states form a directed graph, and transitions come from two sources: local actions this cache takes (read → SC/UC, write on a unique line → UD, evict → I) and remote snoops forced by other caches (SnpShared → SC, SnpUnique → I). Two rules shape the table: a write is legal only from a unique state — a shared line (SC/SD) must upgrade (MakeUnique) first, never a silent SC → UD; and a snoop must be handled from every valid state, because it arrives unbidden in whatever state the line is in. The overriding requirement is totality: every (state, event) pair must have a defined next state. A missing entry — say, no rule for SnpUnique arriving in SD — is a latent coherence bug: when that combination occurs, the invalidation does not happen, a stale copy survives, and dirty data is dropped. Cover local and snoop events; keep the table complete; write only from unique. Representative model; 10.3 tracks ownership at each moment.

Coming Next

Chapter 10.3 — Ownership in CHI. The transition graph moved lines between states; ownership is the thread running through it. Chapter 10.3 tracks which Request Node owns the line at each moment — who holds the dirty data and the duty to write it back — as transactions and snoops move it around. It ties the SharedDirty state, the PassDirty bit, and the ownership transfers of Module 9 into a single question answered at every step: right now, who owns this line?