Introduction to Coherency

Module 1 · Chapter 1.9 · Cache Coherency Foundations · Module Capstone

Project thread — this chapter closes Module 1 by naming the three invariants the whole CHI series will implement, and previews the solution vocabulary (RN, HN, SN, snoop, directory) that Modules 2 onward detail.

1. Learning Outcomes

By the end of this lesson you will be able to:

• State the three coherency invariants precisely — write propagation, write serialization, and value/coherence — as a per-address contract.
• Explain why write serialization requires a single ordering point and cannot emerge from independent caches negotiating among themselves.
• Name the CHI solution cast — Requester Node, Home Node, Subordinate Node, snoop, directory — and what each contributes.
• Distinguish per-address coherency from cross-address consistency (Module 12).
• Trace a correct transaction where all three invariants hold, and identify which invariant fails in a broken system.

2. Key Terms

Module 1 established the problem: private caches copy data, copies go stale, and AXI cannot arbitrate it. This chapter introduces the solution vocabulary — the cast the rest of CHI details.

• Coherency invariant — one of the three testable per-address properties a coherent system must uphold.
• Write propagation — a write to a location eventually becomes visible to every other core that reads it.
• Write serialization — all cores observe the writes to one location in the same single total order.
• Value / coherence — a read returns the value of the last write to that location in the serial order.
• Requester Node (RN) — an agent (typically a CPU with a coherent cache) that initiates reads and writes; it asks, it does not decide order.
• Home Node (HN) — the coherence and serialization point for a range of addresses.
• Subordinate Node (SN) — the endpoint memory or peripheral that stores and supplies data (also called Completer).
• Snoop — the message the HN sends to other RNs to invalidate or fetch their copies.
• Directory — the HN's record of which RNs currently hold copies of a line.

3. Why Should I Learn This?

Everything in Module 1 was the problem. This chapter names the contract — the exact set of guarantees any coherency protocol, CHI included, must keep. Get these three invariants precise and every later mechanism becomes a way to satisfy them.

A real example of why this matters: a quad-core SoC once let two cores believe they both held the same spinlock, corrupting a shared queue — because competing writes to the lock word were ordered differently by different observers, with no single point forcing one total order. The fix was architectural — route the line through one serialization point — which at SoC scale is the CHI Home Node.

• Coherency is three guarantees, not one. A protocol must satisfy three distinct, testable properties for each address.
• One of them needs a single point. Serialization — all cores agreeing on the same order of writes — cannot emerge from independent caches; it requires one place that decides the order.
• It is per-address. Coherency answers "for one location, do all cores agree?" — not "across locations, in what order?" That second question is consistency (Module 12), and conflating them is a classic mistake.

4. Core Concept — the three invariants, and the solution preview

Take the running project — CPU0, CPU1, each with a private L1, over one shared memory — and state exactly what "coherent" means for a single address A.

Invariant 1 — Write propagation. A write to A by one core eventually becomes visible to every other core. If CPU0 stores A = 6, then after the write settles, any other core that reads A (and does not itself write it first) will eventually see 6 rather than an old value forever. Propagation is the "no permanently stale copy" rule.

Invariant 2 — Write serialization. All cores observe the writes to A in the same single total order. If CPU0 writes 6 and CPU1 writes 7, then every core agrees on which came last — nobody sees "6 then 7" while another sees "7 then 6." Crucially, this order cannot come from independent caches negotiating; it requires a single point that serializes writes to A. That single point, in CHI, is the Home Node.

Invariant 3 — Value / coherence. A read of A returns the value of the last write to A in that serial order. This ties the first two together: propagation makes writes visible, serialization fixes their order, and this invariant says a read must yield the most recent write in that agreed order — wherever that value currently lives.

These three, together, are the per-address coherency contract. They say nothing about different addresses. How a core's writes to A and B are ordered relative to another core's reads — consistency / memory ordering — is a separate problem solved by barriers in Module 12. Chapter 1.9 is strictly one address at a time.

The solution vocabulary (preview). To satisfy all three at SoC scale, CHI names a small cast. Detail arrives in later modules; hold the shapes now:

• Requester Node (RN) — initiates reads and writes; asks, does not decide order. (Module 4.2)
• Home Node (HN) — the coherence and serialization point for a range of addresses. Every request for A funnels to one HN, which imposes the single total order (Invariant 2), issues snoops to propagate writes (Invariant 1), and ensures a read returns the last write (Invariant 3). (Module 4.3)
• Subordinate Node (SN) — the endpoint memory that stores and supplies data when no cache has it. (Module 4.4)
• Snoop — the HN's message to other RNs to invalidate or fetch their copies; the concrete mechanism of propagation. (Module 9)
• Directory — the HN's record of which RNs hold copies, so it snoops only those, not everyone. (Module 11)

5. Engineering Diagram

6. Protocol Transaction Walkthrough — a serialized write, then a correct read

Frame the fix the way CHI will: a request goes to the Home Node, which serializes it, snoops the peer or fetches from the Subordinate Node, and returns data plus completion.

The Home Node did all three jobs: it ordered the write (serialization), snooped RN1 to void the stale copy (propagation), and returned the last write on the next read (value). Every CHI transaction in later modules is a specialization of this shape.

7. Timing Diagram — a serialized write, then a correct read

Track line A across cycles as the HN serializes CPU0's write and then satisfies CPU1's read with the new value.

The visual signature of correct coherency: the peer copy goes Invalid the moment the write is serialized, and the next read returns the new value — the exact opposite of 1.1's diverging copies. The Home Node grants one writer at a time, so writes to A are one-hot in time: one point, one order.

8. RTL Implementation — a minimal serialization-point (home node) model

This is the fix relative to 1.1's broken demo: a tiny home node arbiter over the same two private 1-entry caches. A write now goes through the home node, which enforces single-writer and invalidates the peer's copy so the write propagates. It is simplified and behavioral — not a real CHI Home Node — but it satisfies the three invariants for one line, turning 1.1's failing check into a pass.

// chi_home_node_demo.sv — minimal serialization-point over two private caches.
// A write routes through the "home node": it updates the writer's copy AND
// invalidates the peer's copy (propagation), enforcing single-writer per line.
// The FIX for 1.1's stale read — the peer's next read misses and refetches NEW.
module chi_home_node_demo #(
  parameter int DW = 8
)(
  input  logic          clk,
  input  logic          rst_n,
  input  logic          c0_wr,
  input  logic [DW-1:0] c0_wdata,
  input  logic          c0_rd,
  output logic [DW-1:0] c0_rdata,
  input  logic          c1_wr,
  input  logic [DW-1:0] c1_wdata,
  input  logic          c1_rd,
  output logic [DW-1:0] c1_rdata
);
  // Backing memory (Subordinate Node) + a private cached copy and valid bit per core.
  logic [DW-1:0] mem_A;
  logic [DW-1:0] c0_cache_A, c1_cache_A;
  logic          c0_valid,   c1_valid;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      mem_A      <= 8'd5;
      c0_cache_A <= 8'd5; c0_valid <= 1'b0;
      c1_cache_A <= 8'd5; c1_valid <= 1'b0;
    end else begin
      // HOME NODE: core0 write -> serialize, write memory, invalidate peer copy
      if (c0_wr) begin
        c0_cache_A <= c0_wdata; c0_valid <= 1'b1;
        mem_A      <= c0_wdata;            // propagate to backing memory
        c1_valid   <= 1'b0;               // snoop-invalidate peer (Invariant 1)
      end
      // HOME NODE: core1 write -> serialize, write memory, invalidate peer copy
      else if (c1_wr) begin               // single-writer: else -> one at a time
        c1_cache_A <= c1_wdata; c1_valid <= 1'b1;
        mem_A      <= c1_wdata;
        c0_valid   <= 1'b0;
      end
      // reads: on a miss, refetch the latest value from memory (Invariant 3)
      if (c0_rd && !c0_valid) begin c0_cache_A <= mem_A; c0_valid <= 1'b1; end
      if (c1_rd && !c1_valid) begin c1_cache_A <= mem_A; c1_valid <= 1'b1; end
    end
  end
 
  assign c0_rdata = c0_cache_A;
  assign c1_rdata = c1_cache_A;
endmodule

// chi_home_node_demo.v — Verilog-2001 equivalent (simplified/behavioral).
module chi_home_node_demo #(
  parameter DW = 8
)(
  input               clk,
  input               rst_n,
  input               c0_wr,
  input      [DW-1:0] c0_wdata,
  input               c0_rd,
  output     [DW-1:0] c0_rdata,
  input               c1_wr,
  input      [DW-1:0] c1_wdata,
  input               c1_rd,
  output     [DW-1:0] c1_rdata
);
  reg [DW-1:0] mem_A;
  reg [DW-1:0] c0_cache_A, c1_cache_A;
  reg          c0_valid,   c1_valid;
 
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      mem_A      <= 8'd5;
      c0_cache_A <= 8'd5; c0_valid <= 1'b0;
      c1_cache_A <= 8'd5; c1_valid <= 1'b0;
    end else begin
      if (c0_wr) begin
        c0_cache_A <= c0_wdata; c0_valid <= 1'b1;
        mem_A      <= c0_wdata;
        c1_valid   <= 1'b0;
      end
      else if (c1_wr) begin
        c1_cache_A <= c1_wdata; c1_valid <= 1'b1;
        mem_A      <= c1_wdata;
        c0_valid   <= 1'b0;
      end
      if (c0_rd && !c0_valid) begin c0_cache_A <= mem_A; c0_valid <= 1'b1; end
      if (c1_rd && !c1_valid) begin c1_cache_A <= mem_A; c1_valid <= 1'b1; end
    end
  end
 
  assign c0_rdata = c0_cache_A;
  assign c1_rdata = c1_cache_A;
endmodule

-- chi_home_node_demo.vhd — VHDL equivalent (simplified/behavioral).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_home_node_demo is
  generic ( DW : integer := 8 );
  port (
    clk      : in  std_logic;
    rst_n    : in  std_logic;
    c0_wr    : in  std_logic;
    c0_wdata : in  std_logic_vector(DW-1 downto 0);
    c0_rd    : in  std_logic;
    c0_rdata : out std_logic_vector(DW-1 downto 0);
    c1_wr    : in  std_logic;
    c1_wdata : in  std_logic_vector(DW-1 downto 0);
    c1_rd    : in  std_logic;
    c1_rdata : out std_logic_vector(DW-1 downto 0)
  );
end entity;
 
architecture rtl of chi_home_node_demo is
  signal mem_A      : unsigned(DW-1 downto 0);
  signal c0_cache_A : unsigned(DW-1 downto 0);
  signal c1_cache_A : unsigned(DW-1 downto 0);
  signal c0_valid   : std_logic;
  signal c1_valid   : std_logic;
begin
  process(clk, rst_n)
  begin
    if rst_n = '0' then
      mem_A      <= to_unsigned(5, DW);
      c0_cache_A <= to_unsigned(5, DW); c0_valid <= '0';
      c1_cache_A <= to_unsigned(5, DW); c1_valid <= '0';
    elsif rising_edge(clk) then
      if c0_wr = '1' then
        c0_cache_A <= unsigned(c0_wdata); c0_valid <= '1';
        mem_A      <= unsigned(c0_wdata);
        c1_valid   <= '0';
      elsif c1_wr = '1' then
        c1_cache_A <= unsigned(c1_wdata); c1_valid <= '1';
        mem_A      <= unsigned(c1_wdata);
        c0_valid   <= '0';
      end if;
      if c0_rd = '1' and c0_valid = '0' then c0_cache_A <= mem_A; c0_valid <= '1'; end if;
      if c1_rd = '1' and c1_valid = '0' then c1_cache_A <= mem_A; c1_valid <= '1'; end if;
    end if;
  end process;
 
  c0_rdata <= std_logic_vector(c0_cache_A);
  c1_rdata <= std_logic_vector(c1_cache_A);
end architecture;

9. Testbench — prove the peer read now returns the NEW value

Drive the identical scenario as 1.1 — both cores cache A, CPU0 writes 6, CPU1 reads — but now the home node invalidated CPU1's copy, so its read misses and refetches 6. The check that failed in 1.1 now passes. Signals are driven on the negedge so they are stable at the sampling posedge (no race).

// tb_chi_home_node_demo.sv — the fixed counterpart to 1.1; peer read = NEW.
module tb_chi_home_node_demo;
  logic clk = 0, rst_n = 0;
  logic       c0_wr, c0_rd, c1_wr, c1_rd;
  logic [7:0] c0_wdata, c0_rdata, c1_wdata, c1_rdata;
 
  chi_home_node_demo dut (.clk, .rst_n,
    .c0_wr, .c0_wdata, .c0_rd, .c0_rdata,
    .c1_wr, .c1_wdata, .c1_rd, .c1_rdata);
 
  always #5 clk = ~clk;
 
  initial begin
    c0_wr=0; c0_rd=0; c0_wdata=0; c1_wr=0; c1_rd=0; c1_wdata=0;
    @(negedge clk) rst_n = 1;
 
    @(negedge clk) c0_rd = 1;            // CPU0 caches A (=5)
    @(negedge clk) c0_rd = 0; c1_rd = 1; // CPU1 caches its own A (=5)
    @(negedge clk) c1_rd = 0;
    @(negedge clk) c0_wr = 1; c0_wdata = 8'd6; // CPU0 writes A=6 via home node
    @(negedge clk) c0_wr = 0; c1_rd = 1;       // CPU1 reads (its copy invalidated)
    @(negedge clk) c1_rd = 0;
    @(negedge clk);                            // allow refetch to settle
 
    if (c1_rdata == 8'd6)
      $display("[FIXED] COHERENT: CPU1 sees A=%0d (last write), expected 6", c1_rdata);
    else
      $display("[FAIL] CPU1 sees stale A=%0d, expected 6", c1_rdata);
    $finish;
  end
endmodule

10. Expected Simulation Output

[FIXED] COHERENT: CPU1 sees A=6 (last write), expected 6

Why this happens: the home node serialized CPU0's write (granting one writer at a time), wrote it to backing memory, and invalidated CPU1's stale copy on the same write (propagation). When CPU1 read next, its line was no longer valid, so it missed and refetched the latest value — returning 6, the last write in the serial order (value/coherence). The exact check that failed in 1.1 — CPU1 sees A=5 — now passes as CPU1 sees A=6. That single flipped result is the three invariants working together.

11. Verification Assertion

The three invariants are three separate, testable properties. Encode two directly as SystemVerilog assertions against the read/write ports, and treat peer-invalidate-on-write as the mechanism for the third (propagation). Here ref_A is a golden model of the last serialized write.

// chi_coherency_invariants.sv — encodes the three invariants for line A.
// ref_A tracks the last write in the serial order; the assertions check that
// only one writer is granted per cycle (serialization) and that a completed
// read returns the last serialized write (value). Peer-invalidate in the DUT
// is the propagation mechanism these two properties rely on.
module chi_coherency_invariants (
  input logic       clk,
  input logic       c0_wr, input logic [7:0] c0_wdata,
  input logic       c1_wr, input logic [7:0] c1_wdata,
  input logic       c1_rd, input logic [7:0] c1_rdata
);
  logic [7:0] ref_A = 8'd5;                 // last write in the HN-imposed order
  always_ff @(posedge clk) begin
    if (c0_wr) ref_A <= c0_wdata;           // each serialized write updates ref
    if (c1_wr) ref_A <= c1_wdata;
  end
 
  // Invariant 2 (serialization): at most one writable owner per cycle.
  a_single_writer: assert property (@(posedge clk) !(c0_wr && c1_wr))
    else $error("SERIALIZATION VIOLATION: two writers to A in one cycle");
 
  // Invariant 3 (value): a completed read returns the last serialized write.
  // The DUT's read data is registered (a read miss fills the line on the next
  // clock), so sample c1_rdata the cycle AFTER the request against the reference
  // captured at request time — checking same-cycle would false-fire on a miss.
  a_read_is_last_write: assert property (@(posedge clk)
    c1_rd |=> (c1_rdata == $past(ref_A)))
    else $error("VALUE VIOLATION: read %0d != last write %0d", c1_rdata, $past(ref_A));
endmodule

Prose invariant: single-writer — at most one cache holds a writable copy at a time, so writes are totally ordered by one authority (serialization); propagation — every serialized write invalidates other copies before the next read observes them; value — a read must return the last write in that order. The home-node model upholds all three; 1.1's demo violated propagation and value, and a multi-observer system with no single ordering point violates serialization.

12. DebugLab — "one core says it won the lock, the other disagrees"

13. Common Mistakes

• Thinking coherency is one guarantee. It is three — propagation, serialization, value — and a system can satisfy two while silently breaking the third.
• Believing independent caches can agree on write order. They cannot; serialization requires a single point per address (the Home Node).
• Confusing serialization with cross-address ordering. Serialization is one address, one order of its writes. Cross-address ordering is consistency (Module 12).
• Assuming "eventually visible" is enough. Propagation alone does not fix which write is last; without serialization, observers still disagree.
• Reaching for barriers to fix a coherency bug. Barriers order a core's accesses across addresses; they do not create a serialization point for one address.
• Calling the Home Node "just a memory controller." The HN is the coherence/serialization point and directory owner; the memory endpoint is the Subordinate Node — different roles.

14. Interview Questions

15. Engineering Checklist

• I can state all three invariants precisely: write propagation, write serialization, value/coherence — per address.
• I can explain why serialization requires a single point and cannot emerge from independent caches.
• I can name that point in CHI — the Home Node — and what it does for each invariant.
• I can preview the solution cast: RN (asks), HN (serializes), SN (stores), snoop (propagates), directory (tracks sharers).
• I can distinguish per-address coherency from cross-address consistency (Module 12).
• I can show a trace where all three invariants hold, and identify which one fails in a broken system.

16. Key Takeaways

• Coherency is three invariants, per address: write propagation (a write eventually reaches all cores), write serialization (all cores see one total order of writes), and value/coherence (a read returns the last write in that order).
• Serialization needs a single point. Independent caches cannot agree on an order; one ordering authority per address must impose it — in CHI, the Home Node.
• The solution cast: RN asks, HN serializes and owns coherency, SN stores, snoop propagates writes, directory tracks sharers so propagation stays cheap.
• Per-address, not cross-address. These invariants are coherency; cross-address ordering is consistency, solved in Module 12.
• This is the specification the CHI series implements. Every later mechanism satisfies one of these three invariants.

17. Quick Revision

Introduction to coherency. Coherency = three per-address invariants: (1) write propagation — a write eventually becomes visible to all cores; (2) write serialization — all cores observe writes to one location in the same single total order (needs ONE serialization point, foreshadowing the Home Node); (3) value/coherence — a read returns the value of the last write in that order. Serialization is the hard one: independent caches cannot agree on order, so CHI routes each address to one HN. Solution cast (preview): RN asks, HN serializes + owns coherency, SN stores, snoop propagates, directory tracks sharers. This is per-address coherency, NOT cross-address consistency (Module 12). The three invariants are the acceptance test the whole CHI series implements.

18. Coming Next

Next — Module 2: Coherency Protocol Foundations (MSI/MESI/MOESI/MESIF). The invariants are the contract; Module 2 introduces the state machine that keeps it. You will add:

• Per-line states — how a cached line is tagged Modified, Owned, Exclusive, Shared, or Invalid, so hardware knows who may read or write it.
• State transitions on reads, writes, and snoops — the exact rules that move a line between states while preserving single-writer and propagation.
• Why MSI, MESI, MOESI, and MESIF differ — what each extra state buys (silent sharing, dirty-sharing, clean forwarding) and what it costs.

We keep the same project and the same three invariants; Module 2 turns "one serialization point enforces the contract" into "here are the precise per-line states and transitions that implement it."