Sharing in CHI

Module 10 · Chapter 10.4 · Cache State Management

Project thread — 10.3 tracked the single owner. This chapter tracks the many readers — the sharer set. 10.5 follows dirty data to memory or another cache.

1. Learning Outcomes

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

• Describe the Shared states — multiple caches holding a line read-only at once.
• Define the sharer set — the home's record of which caches hold the line.
• Explain why the sharer set drives which caches a write must invalidate.
• State the accuracy rule — the set must record every holder.
• Diagnose the stale-reader bug from an under-counted sharer set.
• Implement a representative sharer-set model in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Read-sharing is the common case: instructions, constants, read-mostly data are held by many caches at once, all reading, none writing. That coexistence is what caches are for — local copies serving local reads. The Shared states make it possible, and the home's sharer set is what keeps it coherent.

The set matters most at the moment sharing ends — when a core writes the line. To make that write safe, every other copy must be invalidated (Chapter 8.2), and the home invalidates exactly the caches in its sharer set. So the set is not passive bookkeeping; it is the list the home acts on to protect a write. An inaccurate set is a coherence hazard: miss a sharer and the write leaves it stale. Understanding sharing means understanding that the sharer set must be an exact record of who holds the line.

3. Key Terms

4. Previous Chapter Connection

Chapter 10.3 tracked the single owner; this chapter tracks the many readers. They are complementary directory records: ownership names one node (or memory); the sharer set names a group.

The Shared states — SC, and the SD owner — are where sharing lives, and you have seen them throughout: ReadShared adds a sharer (Chapter 8.1), SnpShared downgrades a holder into the sharer set (Chapter 9.2), ReadUnique invalidates the whole set (Chapter 8.2). This chapter makes the set the subject: how the home records it, how it grows and shrinks, and why its accuracy determines whether a later write is safe. The coverage rule of 8.2 — invalidate every sharer — depends entirely on the set being right.

5. Core Concept — many readers, one tracked set

Sharing is multiple caches holding a line read-only at once, and the home tracks who they are.

• The Shared states coexist. Any number of caches can hold a line in SC simultaneously, all reading. One may be the SD owner (holding the dirty data), but all are readers.
• The home tracks the sharer set. The directory records which caches hold the line — as a set (often a bitmask, one bit per cache). This is how the home knows who to reach.
• The set drives invalidation. When a core issues a ReadUnique to write the line, the home invalidates exactly the caches in the sharer set — so the set must list every holder (Chapter 8.2).
• The set drives forwarding. When a new reader wants a line the set already holds, the home can forward from a sharer (cache-to-cache, Chapters 9.5, 9.7) instead of reading memory.

The synthesis:

Sharing lets many caches hold a line read-only at once, and the home records them in a sharer set. The set is load-bearing: a later write invalidates exactly the set, so it must record every holder — an under-count leaves a stale reader. The set also enables forwarding a new reader from an existing sharer. Accurate sharing tracking is what makes both safe writes and cache-to-cache reads possible.

6. Engineering Mental Model — the circulation list

A shared reference document is on a circulation list — everyone on the list holds a copy to read.

• Many people can be on the list at once; they all read their copies, and nobody edits.
• The library keeps the list — it knows exactly who currently holds a copy.
• When someone finally wants to edit the document, the library must recall every copy — and it recalls exactly the people on the list. If the list is right, every copy comes back and the editor is safe.
• If someone was handed a copy but never added to the list, the recall misses them. They keep reading their now-outdated copy while the editor rewrites — working from stale text.

The list is what makes editing safe: it is the recall roster. A copy that is not on the list is a copy the recall cannot reach. Keeping the list complete is the whole job.

7. Engineering Diagram — the sharer set

Three readers, one recorded set. The home's directory lists (RN0, RN1, RN2) — and that list is exactly who a later write must invalidate. Every reader shown is in the set; a reader not in the set would be invisible to the home.

8. What the Sharer Set Drives

The set is read for two purposes.

The rule to carry: the sharer set is the home's action list. On a write, it is the invalidation roster — so it must include every holder, or the write leaves a stale copy. On a read, it names potential forwarders. Under-counting is a correctness bug (a missed invalidation); over-counting is a performance bug (a wasted snoop). The set must be an exact record of who holds the line.

9. Accuracy — the Sharer Set Must Record Every Holder

The accuracy requirement deserves its own emphasis, because a write depends on it.

• Every reader must be recorded. When a cache becomes a sharer — via ReadShared, or a SnpShared downgrade — the home must add it to the set.
• Every departure must be recorded. When a sharer drops the line (Evict, Chapter 8.7) or is invalidated, the home must remove it — or the set over-counts.
• A write invalidates the recorded set. ReadUnique snoops exactly the caches the set lists. A holder not in the set is not snooped — and survives the write.
• So under-count is the dangerous direction. An over-count wastes a snoop (harmless to correctness); an under-count leaves a real holder uninvalidated, reading stale after the write.

The point to carry:

The sharer set is the bridge between who actually holds the line and who the home will act on. The home does not inspect caches on a write; it invalidates the set. So the set must equal the true set of holders — and the asymmetry matters: an over-count costs bandwidth, but an under-count costs correctness, because the one holder the set forgot is exactly the one the write will not invalidate. Accurate sharing tracking is not tidiness; it is the guarantee that a write reaches every copy.

10. Reading the Set — a share then a write

Follow the sharer set as readers join and a write clears them.

1. RN0 reads. ReadShared: RN0 installs SC. Home records sharers = (RN0).
2. RN1 reads. ReadShared: RN1 installs SC, sourced by forwarding from RN0. Home updates sharers = (RN0, RN1).
3. RN2 reads. Another sharer joins: sharers = (RN0, RN1, RN2). Three readers coexist.
4. RN3 writes. ReadUnique: the home snoops exactly (RN0, RN1, RN2) — every recorded sharer — invalidating all three. RN3 installs UC and writes.
5. After. Sharers = (empty); RN3 is the sole (unique) holder. No stale copy survives.

The write in step 4 was safe because the set in step 3 was complete. Had RN2 read the line without being recorded (an under-count), step 4 would have snooped only (RN0, RN1), and RN2 would read stale — the DebugLab.

11. RTL / Hardware View — a sharer-set model

The home's sharer tracking is a bitmask, one bit per cache. Adding a reader sets its bit; a write must snoop every set bit. Representative.

// Representative sharer-set model (educational).
// The sharer set is a bitmask: bit i = 1 means cache i holds the line (Shared).
// Adding a reader sets its bit; a write must snoop EVERY set bit (the whole set).
// The set must record every holder, or a write misses one -> stale reader.
module chi_sharer_set #(parameter N = 4) (
  input  logic [N-1:0] sharers_in,   // current sharer set
  input  logic         add_reader,   // a new reader is joining
  input  logic [N-1:0] reader_onehot,// which cache is joining (one-hot)
  output logic [N-1:0] sharers_out,  // updated sharer set
  output logic [N-1:0] snoop_mask,   // caches a write must invalidate (= the set)
  output logic [$clog2(N+1)-1:0] num_sharers
);
  // Add the new reader to the set (if any). Every reader must be recorded.
  assign sharers_out = add_reader ? (sharers_in | reader_onehot) : sharers_in;
  // A write invalidates EXACTLY the recorded sharer set.
  assign snoop_mask  = sharers_out;
  // Count the sharers (popcount).
  always_comb begin
    num_sharers = '0;
    for (int i = 0; i < N; i++) num_sharers += sharers_out[i];
  end
endmodule

The same behavior in Verilog-2001:

// Representative sharer-set model (Verilog-2001).
module chi_sharer_set #(parameter N = 4) (
  input  [N-1:0] sharers_in,
  input          add_reader,
  input  [N-1:0] reader_onehot,
  output [N-1:0] sharers_out,
  output [N-1:0] snoop_mask,
  output [31:0]  num_sharers
);
  integer i;
  reg [31:0] cnt;
  assign sharers_out = add_reader ? (sharers_in | reader_onehot) : sharers_in;
  assign snoop_mask  = sharers_out;
  always @* begin
    cnt = 32'd0;
    for (i = 0; i < N; i = i + 1) cnt = cnt + sharers_out[i];
  end
  assign num_sharers = cnt;
endmodule

And in VHDL:

-- Representative sharer-set model (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_sharer_set is
  generic ( N : integer := 4 );
  port (
    sharers_in    : in  std_logic_vector(N-1 downto 0);
    add_reader    : in  std_logic;
    reader_onehot : in  std_logic_vector(N-1 downto 0);
    sharers_out   : out std_logic_vector(N-1 downto 0);
    snoop_mask    : out std_logic_vector(N-1 downto 0);
    num_sharers   : out integer
  );
end entity;
 
architecture rtl of chi_sharer_set is
  signal setv : std_logic_vector(N-1 downto 0);
begin
  setv <= (sharers_in or reader_onehot) when add_reader = '1' else sharers_in;
  sharers_out <= setv;
  snoop_mask  <= setv;
  process (setv)
    variable c : integer;
  begin
    c := 0;
    for i in 0 to N-1 loop
      if setv(i) = '1' then c := c + 1; end if;
    end loop;
    num_sharers <= c;
  end process;
end architecture;

All three make the snoop mask equal the sharer set — a write invalidates exactly the recorded holders — and add each new reader to the set. The DebugLab shows what a missed add costs.

12. Verification View — the write snoops the whole set

The properties that keep sharing sound: the snoop mask equals the set, and a joined reader is recorded.

// Bind to chi_sharer_set.
// 1. A write's snoop mask is exactly the recorded sharer set.
property p_snoop_equals_set;
  @(*) snoop_mask == sharers_out;
endproperty
 
// 2. A joining reader is added to the set (recorded, so a later write will reach it).
property p_reader_recorded;
  @(*) add_reader |-> ((sharers_out & reader_onehot) == reader_onehot);
endproperty
 
// 3. The set never silently loses a prior sharer on an add.
property p_no_silent_drop_on_add;
  @(*) (sharers_in & sharers_out) == sharers_in;
endproperty

The system point, beyond the checks:

The sharer set is a representation of a distributed fact — which caches hold the line — and coherence depends on the representation being complete. The home acts on the set, not on the caches, so any holder outside the set is, to the home, invisible: it will not be forwarded from, not counted, and — the dangerous part — not invalidated. The invariant that matters is therefore containment: the recorded set must be a superset of, ideally equal to, the true holders. Equality is best (no waste); a superset is at least safe (extra snoops); a subset is a correctness bug, because the missing holder escapes the one operation — invalidation — that sharing must eventually submit to.

• What it proves: the write snoops the whole recorded set, and joins are recorded.
• What it does not prove: the set equals the true holders at all times — that needs every join/leave recorded.
• Bug signature: a real holder absent from the set — a hidden sharer the write cannot reach.

13. Testbench — building and snooping the set

Adds readers to the set and checks the count and the write snoop mask.

module tb_chi_sharer_set;
  localparam N = 4;
  logic [N-1:0] sharers_in, reader_onehot, sharers_out, snoop_mask;
  logic add_reader;
  logic [$clog2(N+1)-1:0] num_sharers;
  int errors = 0;
 
  chi_sharer_set #(.N(N)) dut (.*);
 
  task automatic check(input logic [N-1:0] si, input logic ar, input logic [N-1:0] roh,
                       input logic [N-1:0] exp_set, input int exp_n, input string name);
    sharers_in = si; add_reader = ar; reader_onehot = roh; #1;
    if (sharers_out !== exp_set || snoop_mask !== exp_set || num_sharers !== exp_n) begin
      errors++; $display("FAIL %s: set=%b mask=%b n=%0d", name, sharers_out, snoop_mask, num_sharers);
    end else $display("PASS %s: set=%b n=%0d", name, sharers_out, num_sharers);
  endtask
 
  initial begin
    check(4'b0000, 1'b1, 4'b0001, 4'b0001, 1, "add RN0 -> {RN0}");
    check(4'b0001, 1'b1, 4'b0010, 4'b0011, 2, "add RN1 -> {RN0,RN1}");
    check(4'b0011, 1'b1, 4'b0100, 4'b0111, 3, "add RN2 -> {RN0,RN1,RN2}");
    check(4'b0111, 1'b0, 4'b0000, 4'b0111, 3, "write -> snoop {RN0,RN1,RN2}");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS add RN0 -> {RN0}: set=0001 n=1
PASS add RN1 -> {RN0,RN1}: set=0011 n=2
PASS add RN2 -> {RN0,RN1,RN2}: set=0111 n=3
PASS write -> snoop {RN0,RN1,RN2}: set=0111 n=3
ALL TESTS PASSED

14. DebugLab — an under-counted sharer set

true holders: RN0, RN1, RN2 (all SC)
recorded sharer set: {RN0, RN1}   <-- RN2 was never added
RN3 ReadUnique -> home snoops the SET: RN0, RN1 (not RN2)
  RN0, RN1 -> I;  RN2 still SC(old)  <-- never snooped
RN3 writes NEW; RN2 reads -> old  -> COHERENCE VIOLATION

15. Common Mistakes

• Under-counting the set. Assumption: some readers can be skipped. Bug: stale reader (the DebugLab). Prevention: record every join.
• Over-counting the set. Assumption: never remove sharers. Bug: wasted snoops. Prevention: record every departure (Evict).
• Confusing the tracked set with the true set. Assumption: they always match. Bug: latent inaccuracy. Prevention: update on every join/leave.
• Forgetting the SD owner is a sharer. Assumption: only SC caches share. Bug: missing a holder. Prevention: the SD owner shares too.
• Snooping a subset on a write. Assumption: a few sharers suffice. Bug: a survivor. Prevention: snoop the whole set (Chapter 8.2).
• Ignoring forwarding opportunities. Assumption: always read memory. Bug: needless latency. Prevention: forward from a sharer.

16. Engineering Checklist

• Let multiple caches hold a line in SC at once — readers coexist.
• Track the sharer set in the directory — one entry per holder.
• Add every reader as it joins; remove every sharer as it leaves.
• On a write, invalidate exactly the sharer set — every recorded holder.
• Keep the set a superset of the true holders — never a subset.
• Use the set to forward a new reader from a sharer when it helps.

17. Key Takeaways

• Sharing lets many caches hold a line read-only at once — the Shared states (SC, and the SD owner).
• The home tracks a sharer set — the record of which caches hold the line.
• The set is the home's action list: a write invalidates exactly the set.
• It must be accurate — an under-count leaves a holder that a write cannot reach, reading stale.
• The set also drives forwarding — a new reader can be sourced from a sharer.
• Record every join and leave; keep the set complete; the model here is representative.

18. Quick Revision

Sharing in CHI. The Shared states let many caches hold a line read-only at once — any number in SC, plus the SD owner — all reading, none writing. The home tracks them in a sharer set (a bitmask of holders), which is its action list. On a write (ReadUnique), the home invalidates exactly the sharer set, so the set must record every holder: an under-count leaves a real holder unsnooped, and it reads stale the moment the write lands — a coherence violation. An over-count merely wastes snoops (a performance cost), so the set must be kept a superset of the true holders, ideally equal: add every reader as it joins, remove every sharer as it leaves. The set also drives forwarding — a new reader can be sourced cache-to-cache from an existing sharer instead of memory. Track every holder; the write reaches exactly the set. Representative model; 10.5 follows dirty data to memory or another cache.

Coming Next

Chapter 10.5 — Dirty Data Handling. Ownership and sharing were about who holds the line; this next chapter is about how the dirty data itself moves. Chapter 10.5 traces the paths a modified line takes — from the owner to memory on a writeback, or from the owner directly to another Request Node on a snoop — tying together PassDirty, cache-to-cache transfer, and the writeback flows into one view of how the latest value is always preserved and delivered.