HN-F (Fully Coherent Home Node)

Module 5 · Chapter 5.3 · CHI System Components

Project thread — 5.1 and 5.2 detailed the request nodes; this chapter details the home. HN-F holds the directory and runs the per-line coherence machine. 5.4 takes the IO home, HN-I.

1. Learning Outcomes

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

• Describe HN-F as the fully coherent Home Node and where coherency is computed.
• Explain the directory / snoop filter: what it records per line and precise vs filter trade-offs.
• Read the per-line directory state machine — Invalid, Shared, Unique — and its transitions.
• Derive the snoop HN-F issues from the request type and directory state.
• State why a ReadUnique must invalidate all sharers before granting ownership.
• Implement a representative HN-F directory coherence-decision block in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

HN-F is where CHI's coherency actually happens. The request nodes ask and answer; the Home Node decides — who holds what, who to snoop, what state each line lands in. Every coherency guarantee is enforced here, so understanding HN-F's directory and state machine is understanding CHI's coherency in operation.

It is also the most intricate node to get right, because its per-line state machine must issue exactly the correct snoop for every combination of request and current state. The subtle bugs — a missed invalidation, a wrong snoop type — live in this logic. Chapter 4.3 gave the role; this chapter gives the machine that implements it.

3. Key Terms

4. Previous Chapter Connection

Chapter 4.3 established the Home Node as the Point of Coherence and Serialization: it orders requests, holds the directory, snoops holders, and returns data. It described the address serializer in depth but left the directory and the coherence decision as a black box.

This chapter opens that box for HN-F. Where 4.3 said "consult the directory and snoop the holders," 5.3 says what the directory records, what per-line states it tracks, and exactly which snoop each request-and-state combination produces. It is the coherence engine behind the role — and, being where every coherency rule is enforced, the most critical node in the taxonomy.

5. Core Concept — a directory and a state machine

HN-F is two things working together.

• A directory. For each line in its address slice, the directory records which Request Nodes hold it and in what state (shared, or uniquely held). A precise directory tracks exact holders and states; a snoop filter tracks only presence (which RNs might hold it), trading precision for storage — it may over-snoop but never under-snoops. Either way, the directory is what replaces broadcast: HN-F knows who to ask.
• A per-line state machine. HN-F tracks each line's system-level state — Invalid (no RN holds it), Shared (one or more RNs hold a shared copy), Unique (exactly one RN holds it uniquely) — and transitions it on each request. The state plus the request type determines the snoop.

The decision HN-F makes on every request:

From the line's directory state and the request type, HN-F derives three things: the snoop to issue (SnpShared, SnpUnique, or none), whether to fetch memory (on a miss), and the next directory state. A ReadUnique to a Shared line snoop-invalidates every sharer and goes Unique; a ReadShared to a Unique line snoop-downgrades the holder and goes Shared; a request to an Invalid line fetches memory. The directory tells HN-F who; the state machine tells it what.

6. Engineering Mental Model — the registrar's ledger and rulebook

Return once more to the registrar (the Home Node) from Chapter 4.3. HN-F is the registrar with two tools made explicit.

• The ledger (directory) lists, for each record, exactly who currently holds a copy and whether they hold it to read (shared) or to modify (unique). The registrar never guesses who to contact — the ledger says.
• The rulebook (state machine) says what to do for each request given the record's status: "someone wants to read a record one person holds for modification → tell that person to switch to read-only and share a copy" (Unique + ReadShared → snoop-downgrade → Shared); "someone wants to modify a record several people are reading → tell them all to drop it, then grant exclusive" (Shared + ReadUnique → snoop-invalidate → Unique).

Ledger plus rulebook is HN-F: it always knows who holds what, and always applies the right rule. The correctness of the whole system is the correctness of this pair.

7. Engineering Diagram — inside HN-F

The directory is the hub: the serializer feeds it one request at a time, and it drives both the snoop generator (who to snoop) and the SN interface (whether to touch memory).

8. The Directory / Snoop Filter

The directory is what makes targeted snooping possible. Its per-line record and the two flavors:

Two facts to carry: a directory must never under-snoop — missing a holder is a coherency violation (Chapter 3.5) — so a snoop filter that loses precision must fall back to broadcasting; and the record's state (shared vs unique) is what lets HN-F choose the right snoop and know whether memory is current. The directory is both a who (presence) and a what (state).

9. The Directory State Machine

HN-F tracks each line as Invalid, Shared, or Unique, and transitions it per request. This is the coherence machine behind every decision.

The single most important transition is Shared → Unique on ReadUnique: it must snoop-invalidate every sharer before granting the requester ownership. Skip that and stale sharers survive — the DebugLab.

10. Transaction Walkthrough — ReadUnique to a shared line

Two cores hold line A shared; a third wants to write it.

1. State. The directory has line A in Shared, held by CPU0 and CPU1 (both SC).
2. Request. CPU2's RN-F issues ReadUnique for line A — it intends to write.
3. Decide. HN-F reads the directory: state Shared, holders CPU0 and CPU1. The rule for Shared + ReadUnique is snoop-invalidate all sharers.
4. Snoop. HN-F sends SnpUnique to both CPU0 and CPU1. Each invalidates its copy (→ I) and acknowledges; neither held it dirty, so no data comes back.
5. Grant and update. HN-F returns the data (from memory, current since the sharers were clean) to CPU2 as Unique; the directory transitions Shared → Unique, holder CPU2. CPU2 writes.

Every prior sharer was invalidated before CPU2 got ownership, so at the instant CPU2 can write, no other cache holds the line. Single-writer is preserved — provided step 4 snoops all sharers, which is exactly what the DebugLab gets wrong.

11. RTL / Hardware View — the directory coherence decision

The core of HN-F is turning (directory state, request type) into (snoop, fetch, next state). Here it is for the Invalid/Shared/Unique model. Representative and combinational.

// Representative HN-F directory coherence decision (educational, I/S/U model).
// From the line's directory state and the request type, decide the snoop to
// issue, whether to fetch memory, and the next directory state.
module hnf_dir_fsm (
  input  logic [1:0] dir_state,     // I=0, S=1, U=2
  input  logic       req_unique,    // 1 = ReadUnique, 0 = ReadShared
  output logic [1:0] snoop,         // 0 none, 1 SnpShared, 2 SnpUnique
  output logic       fetch_mem,     // read from the SN (miss)
  output logic [1:0] next_state
);
  localparam logic [1:0] I=2'd0, S=2'd1, U=2'd2;
  localparam logic [1:0] SNP_NONE=2'd0, SNP_SHARED=2'd1, SNP_UNIQUE=2'd2;
  always_comb begin
    snoop = SNP_NONE; fetch_mem = 1'b0; next_state = dir_state;
    unique case (dir_state)
      I: begin                                   // no holders: fetch and grant
        fetch_mem  = 1'b1;
        next_state = req_unique ? U : S;
      end
      S: begin
        if (req_unique) begin snoop = SNP_UNIQUE; next_state = U; end  // invalidate ALL sharers
        else                  next_state = S;                          // add a sharer
      end
      U: begin                                   // one exclusive holder: snoop it
        if (req_unique) begin snoop = SNP_UNIQUE; next_state = U; end  // invalidate, new owner
        else            begin snoop = SNP_SHARED; next_state = S; end  // downgrade to shared
      end
      default: next_state = I;
    endcase
  end
endmodule

The same behavior in Verilog-2001:

// Representative HN-F directory coherence decision (Verilog-2001).
module hnf_dir_fsm (
  input      [1:0] dir_state,
  input            req_unique,
  output reg [1:0] snoop,
  output reg       fetch_mem,
  output reg [1:0] next_state
);
  localparam I=2'd0, S=2'd1, U=2'd2;
  localparam SNP_NONE=2'd0, SNP_SHARED=2'd1, SNP_UNIQUE=2'd2;
  always @* begin
    snoop = SNP_NONE; fetch_mem = 1'b0; next_state = dir_state;
    case (dir_state)
      I: begin fetch_mem = 1'b1; next_state = req_unique ? U : S; end
      S: if (req_unique) begin snoop = SNP_UNIQUE; next_state = U; end
         else                 next_state = S;
      U: if (req_unique) begin snoop = SNP_UNIQUE; next_state = U; end
         else            begin snoop = SNP_SHARED; next_state = S; end
      default: next_state = I;
    endcase
  end
endmodule

And in VHDL:

-- Representative HN-F directory coherence decision (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity hnf_dir_fsm is
  port (
    dir_state  : in  std_logic_vector(1 downto 0);   -- I=00,S=01,U=10
    req_unique : in  std_logic;
    snoop      : out std_logic_vector(1 downto 0);    -- none=00,SnpShared=01,SnpUnique=10
    fetch_mem  : out std_logic;
    next_state : out std_logic_vector(1 downto 0)
  );
end entity;
 
architecture rtl of hnf_dir_fsm is
  constant I : std_logic_vector(1 downto 0) := "00";
  constant S : std_logic_vector(1 downto 0) := "01";
  constant U : std_logic_vector(1 downto 0) := "10";
begin
  process(dir_state, req_unique)
  begin
    snoop <= "00"; fetch_mem <= '0'; next_state <= dir_state;
    case dir_state is
      when I => fetch_mem <= '1';
                if req_unique = '1' then next_state <= U; else next_state <= S; end if;
      when S => if req_unique = '1' then snoop <= "10"; next_state <= U;   -- SnpUnique
                else next_state <= S; end if;
      when U => if req_unique = '1' then snoop <= "10"; next_state <= U;   -- SnpUnique
                else snoop <= "01"; next_state <= S; end if;               -- SnpShared
      when others => next_state <= I;
    end case;
  end process;
end architecture;

All three encode the directory rules: fetch on a miss, SnpUnique to invalidate sharers on ReadUnique, SnpShared to downgrade on a ReadShared to a Unique line. The one line that guards single-writer is the SnpUnique on S + req_unique — the DebugLab is its omission.

12. Verification View — ReadUnique always snoop-invalidates existing holders

Two properties: a ReadUnique to a line with holders always issues SnpUnique, and a miss always fetches memory.

// Bind to hnf_dir_fsm.
localparam logic [1:0] I=2'd0, S=2'd1, U=2'd2, SNP_UNIQUE=2'd2;
 
// 1. A ReadUnique to a line with holders (S or U) must SnpUnique them —
//    no sharer may survive when ownership is granted.
always_comb if (req_unique && (dir_state == S || dir_state == U))
  assert (snoop == SNP_UNIQUE);
 
// 2. A request to an Invalid line fetches memory (no cached copy exists).
always_comb if (dir_state == I) assert (fetch_mem);

The system point, beyond the two checks:

HN-F's correctness is the correctness of a small rule table, and one rule dominates: granting Unique requires invalidating every current holder first. If a ReadUnique to a Shared line does not SnpUnique all sharers, the requester writes while stale copies survive — Single-Writer/Multiple-Reader is broken at the source. The RN-side rule (SnpUnique → Invalid, Chapter 5.1) and the HN-side rule (issue SnpUnique to all holders) are two halves of the same invariant: after a ReadUnique completes, exactly one cache holds the line.

• What it proves: ReadUnique snoop-invalidates holders; misses fetch memory.
• What it does not prove: that the snoop reaches every sharer (a directory-completeness property — Chapter 3.5).
• Bug signature: a granted Unique with surviving sharers (the DebugLab).

13. Testbench — decide for each state and request

Drives all three states with ReadShared and ReadUnique and checks snoop / fetch / next state.

module tb_hnf_dir_fsm;
  logic [1:0] dir_state, snoop, next_state;
  logic req_unique, fetch_mem;
  int errors = 0;
  localparam logic [1:0] I=2'd0, S=2'd1, U=2'd2;
  localparam logic [1:0] SNP_NONE=2'd0, SNP_SHARED=2'd1, SNP_UNIQUE=2'd2;
 
  hnf_dir_fsm dut (.*);
 
  task automatic check(input logic [1:0] st, input logic u, input logic [1:0] exp_snp,
                       input logic exp_fetch, input logic [1:0] exp_ns, input string tag);
    dir_state = st; req_unique = u; #1;
    if (snoop !== exp_snp || fetch_mem !== exp_fetch || next_state !== exp_ns) begin
      errors++; $display("FAIL [%s] snp=%0d fetch=%b ns=%0d", tag, snoop, fetch_mem, next_state);
    end else $display("PASS [%s] snp=%0d fetch=%b ns=%0d", tag, snoop, fetch_mem, next_state);
  endtask
 
  initial begin
    check(I, 1'b0, SNP_NONE,   1'b1, S, "I + ReadShared -> fetch, S");
    check(I, 1'b1, SNP_NONE,   1'b1, U, "I + ReadUnique -> fetch, U");
    check(S, 1'b0, SNP_NONE,   1'b0, S, "S + ReadShared -> add sharer");
    check(S, 1'b1, SNP_UNIQUE, 1'b0, U, "S + ReadUnique -> SnpUnique, U");
    check(U, 1'b0, SNP_SHARED, 1'b0, S, "U + ReadShared -> SnpShared, S");
    check(U, 1'b1, SNP_UNIQUE, 1'b0, U, "U + ReadUnique -> SnpUnique, U");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS [I + ReadShared -> fetch, S] snp=0 fetch=1 ns=1
PASS [I + ReadUnique -> fetch, U] snp=0 fetch=1 ns=2
PASS [S + ReadShared -> add sharer] snp=0 fetch=0 ns=1
PASS [S + ReadUnique -> SnpUnique, U] snp=2 fetch=0 ns=2
PASS [U + ReadShared -> SnpShared, S] snp=1 fetch=0 ns=1
PASS [U + ReadUnique -> SnpUnique, U] snp=2 fetch=0 ns=2

14. DebugLab — ReadUnique to Shared that forgets to invalidate

dir_state  req_unique  snoop      next_state  note
   S           1        NONE          U        WRONG: sharers not SnpUnique'd

15. Common Mistakes

• Granting Unique without invalidating. Assumption: ownership is just a state change. Bug: stale sharers, SWMR violation (the DebugLab). Prevention: SnpUnique all holders before granting.
• Wrong snoop type. Assumption: any snoop works. Bug: sharing when you meant to invalidate. Prevention: ReadUnique → SnpUnique; ReadShared to a Unique line → SnpShared.
• Under-snooping from a filter. Assumption: the snoop filter is exact. Bug: a missed holder. Prevention: a filter may over-snoop but must never under-snoop; broadcast on uncertainty.
• Forgetting the fetch on a miss. Assumption: the directory always has data. Bug: returning nothing on an Invalid line. Prevention: an Invalid line fetches memory.
• Treating state as presence only. Assumption: knowing who holds it is enough. Bug: wrong snoop / stale-memory assumptions. Prevention: track state too (shared vs unique, clean vs dirty).
• Ignoring serialization. Assumption: the FSM handles concurrency. Bug: two transactions racing a line. Prevention: the serializer (Chapter 4.3) admits one per address; the FSM assumes that.

16. Engineering Checklist

• Record per line who holds it and in what state (directory or snoop filter).
• Never under-snoop: a filter over-snoops or broadcasts on uncertainty.
• Track each line as Invalid / Shared / Unique and transition per request.
• On ReadUnique with any holders, SnpUnique all of them before granting.
• On ReadShared to a Unique line, SnpShared to downgrade.
• Fetch memory on a miss (Invalid line); update the directory on every completion.

17. Key Takeaways

• HN-F is where coherency is computed: a directory (who holds what, in what state) plus a per-line state machine (Invalid / Shared / Unique).
• The directory enables targeted snoops; a snoop filter trades precision for storage but must never under-snoop.
• From (state, request) HN-F derives the snoop, whether to fetch memory, and the next state.
• The dominant rule: a ReadUnique invalidates all holders before granting ownership — the HN-side of single-writer.
• A ReadShared to a Unique line downgrades the holder (SnpShared); a request to Invalid fetches memory.
• HN-F is the most critical node — every coherency rule is enforced here; the model here is representative.

18. Quick Revision

HN-F (fully coherent Home Node). Where coherency is computed for an address slice. Two parts: a directory (per line: which RNs hold it and in what state) — a snoop filter is a lighter version that tracks presence and may over-snoop but must never under-snoop — and a per-line state machine (Invalid no holder, Shared shared holders, Unique one exclusive holder). From (directory state, request type) HN-F derives the snoop (SnpShared / SnpUnique / none), whether to fetch memory (miss), and the next state. Key rules: I + Read → fetch and grant; S + ReadUnique → SnpUnique all sharers → U; U + ReadShared → SnpShared downgrade → S; WriteBack/last-Evict → I. The dominant invariant: grant Unique only after invalidating every holder — the HN-side of single-writer. Representative model; 5.4 covers HN-I.

Coming Next

Chapter 5.4 — HN-I (IO Home Node). HN-F manages coherency; the next home does not. Chapter 5.4 details HN-I, the Home Node for I/O and peripheral address ranges: it serializes and routes accesses like any home, but holds no directory and issues no snoops, because its address space is non-coherent. We will see which of HN-F's machinery it keeps — the serialization and routing — and which it sheds — the directory and coherence state machine — the home-node counterpart to the request-node subtraction of Chapter 5.2.