Sharer Tracking

Module 11 · Chapter 11.3 · Directory-Based Coherency

Project thread — 11.2 distributed the directory. This chapter is how each slice encodes its sharer set. 11.4 covers how it stores the owner.

1. Learning Outcomes

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

• Describe the full bit-vector encoding — one bit per cache, exact, O(N) storage.
• Describe the coarse-grain encoding — one bit per group, cheaper, over-approximate.
• State the storage-versus-precision trade between them.
• State the safety rule — an encoding may over-approximate but never under-approximate.
• Diagnose the stale reader from mis-decoding a coarse group bit as one cache.
• Implement a representative sharer decoder in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

The directory's sharer set is not free — it is storage, and at scale that storage dominates the directory's cost. A full bit-vector, one bit per cache per line, is exact but grows linearly with the core count; for a large system tracking many lines, that is a lot of silicon. So real directories often use coarse-grain encodings that trade some precision for far less storage. Knowing the encodings is knowing where the directory's area goes and how to shrink it.

The trade has a hard boundary, and it is the reason to get this right. Precision loss is only acceptable in one direction: an encoding may claim more sharers than truly exist (extra, wasted snoops — a bandwidth cost) but never fewer (a missed snoop — a coherence bug). Coarse-grain encodings live on exactly this line, and mis-handling one turns a bandwidth optimization into a stale-data bug. This chapter is about spending storage wisely without ever crossing that boundary.

3. Key Terms

4. Previous Chapter Connection

Chapter 10.4 introduced the sharer set and its accuracy rule — a write invalidates exactly the recorded set, so it must include every holder. Chapter 11.2 distributed the directory across homes. This chapter asks the storage question left open: how does a directory slice encode the sharer set?

The set of 10.4 was drawn as an exact bitmask — one bit per cache. That is the full bit-vector, precise but O(N) in storage. This chapter adds the alternative — coarse-grain encodings that use fewer bits by tracking groups — and the constraint that any encoding must obey the 10.4 rule from a different angle: the decoded set must still cover every true holder. So the accuracy of 10.4 becomes a property of the encoding: over-approximate freely, under-approximate never.

5. Core Concept — bit-vector versus coarse-grain, and the safety direction

The directory can encode the sharer set exactly or approximately, and the approximation is only safe in one direction.

• Full bit-vector — exact. One bit per cache; bit i set means cache i holds the line. The directory knows precisely who to snoop. Cost: N bits per line, growing with core count.
• Coarse-grain — cheaper, approximate. One bit per group of G caches (N/G bits). A set group bit means some cache in that group may hold the line — not which one.
• Coarse decode expands. To snoop, a set group bit must expand to a snoop of every cache in the group — because any of them could be the holder. This over-approximates: it may snoop caches that do not hold the line.
• The safety direction. Over-approximation is safe — extra snoops waste bandwidth but miss no holder. Under-approximation is a bug — a holder outside the encoded set is never snooped, and a write leaves it stale.

The synthesis:

A directory encodes the sharer set as a full bit-vector (one bit per cache — exact, O(N) storage) or coarse-grain (one bit per group — cheaper, but a set bit means some cache in the group may hold the line). Coarse decoding expands a group bit to a snoop of the whole group, which over-approximates — safe, extra snoops. The rule that never bends: an encoding may over-approximate (superset) but must never under-approximate (subset), because a missed holder reads stale.

6. Engineering Mental Model — a precise list versus a floor map

Two ways for the front desk to record who borrowed a document.

• A precise list names each borrower individually. To recall the document, the desk contacts exactly those people. Accurate, but the list grows with every possible borrower.
• A floor map marks only which floors have a borrower — one tick per floor, not per person. Smaller to keep, but a ticked floor means someone on that floor has it, not who.
• To recall using the floor map, the desk must page the entire floor — everyone on it — because any of them might be the borrower. That is over-approximating: some people paged do not have the document, but no borrower is missed.

The floor map is cheaper and still safe, as long as "a floor is ticked" is read as "page everyone on it." The mistake would be to page just one person per ticked floor — then the actual borrower, elsewhere on the floor, is never recalled. That is under-approximating: cheaper still, but wrong.

7. Engineering Diagram — the two encodings

Left, the bit-vector: one bit per cache — exact, but N bits. Right, coarse-grain: one bit per group — fewer bits, but a set group bit covers all its members. The coarse bit is read as "snoop the whole group," which over-approximates safely.

8. Bit-Vector versus Coarse-Grain

The two encodings, compared.

The rule to carry: the bit-vector spends storage to snoop precisely; coarse-grain spends snoop bandwidth to save storage. Both are correct as long as the decoded snoop set covers every true holder — the bit-vector does so exactly, coarse-grain does so by expanding each group bit to its whole group. Coarse-grain is only safe when read as a superset; read as a subset (one cache per group), it under-approximates and breaks.

9. Over-Approximate Safely, Never Under-Approximate

The one-directional safety rule deserves its own statement.

• The decoded set must cover every holder. Whatever the encoding, when the home decodes it to a snoop set, that set must be a superset of the true holders (Chapter 10.4).
• Over-approximation is safe. A superset snoops caches that do not hold the line — wasted snoops, a bandwidth cost, but every holder is reached.
• Under-approximation is a bug. A subset omits a real holder, which a write will not snoop — the holder survives and reads stale. This is a correctness failure.
• Coarse-grain lives on the line. Its whole value is over-approximating cheaply; decode it wrongly (a subset) and it crosses into under-approximation instantly.

The point to carry:

Every sharer encoding is judged by one question at decode time: is the snoop set a superset of the true holders? The bit-vector answers yes exactly; coarse-grain answers yes by expanding groups. The asymmetry is the whole design space: you may pay more snoops to save storage (safe), but you may never pay fewer holders' invalidations to save snoops (a coherence bug). So a coarse encoding is a bandwidth-for-storage trade that is correct only while it stays on the over-approximating side — and mis-decoding a group bit as a single cache is the one move that pushes it over.

10. Reading an Encoding — a coarse-grain snoop

Two caches per group; groups A = (RN0, RN1) and B = (RN2, RN3). The line is held only by RN1.

1. Encode. RN1 is in group A, so the directory sets group A's bit (group B's is clear). The coarse record is one bit: A set.
2. Write arrives. A ReadUnique must invalidate every holder.
3. Decode — expand. Group A's bit is set, so the home snoops both members of A: RN0 and RN1. It does not know which holds the line, so it snoops all of A.
4. Over-approximate. RN0 does not hold the line — that snoop is wasted (bandwidth). But RN1, the real holder, is snooped and invalidated. No holder is missed.
5. Group B untouched. B's bit was clear, so RN2 and RN3 are not snooped — correctly, they hold nothing.

The coarse encoding cost one extra snoop (to RN0) and saved storage — a safe trade, because the decode expanded A to its whole group. Snoop only one member of A (a subset) and, if the holder were the other, it would be missed — the DebugLab.

11. RTL / Hardware View — a sharer decoder

The decoder turns a stored encoding into a snoop mask: bit-vector passes through; coarse-grain expands each set group bit to its whole group. Representative.

// Representative sharer-set decoder (educational).
// Bit-vector: the stored bits ARE the snoop mask (exact). Coarse-grain: each set
// GROUP bit expands to a snoop of ALL caches in that group (over-approximate,
// superset). An encoding may over-approximate (safe) but never under-approximate.
module chi_sharer_decode #(parameter N = 4, parameter G = 2) (   // N caches, group size G
  input  logic             is_coarse,      // 0 = bit-vector, 1 = coarse-grain
  input  logic [N-1:0]     bv_bits,        // bit-vector: one bit per cache
  input  logic [N/G-1:0]   cg_bits,        // coarse: one bit per group
  output logic [N-1:0]     snoop_mask       // caches to snoop (a superset of holders)
);
  logic [N-1:0] expanded;
  always_comb begin
    expanded = '0;
    // Each set group bit expands to ALL caches in that group.
    for (int g = 0; g < N/G; g++)
      if (cg_bits[g])
        for (int k = 0; k < G; k++)
          expanded[g*G + k] = 1'b1;
  end
  // Bit-vector is exact; coarse-grain is the expanded superset.
  assign snoop_mask = is_coarse ? expanded : bv_bits;
endmodule

The same behavior in Verilog-2001:

// Representative sharer-set decoder (Verilog-2001).
module chi_sharer_decode #(parameter N = 4, parameter G = 2) (
  input              is_coarse,
  input  [N-1:0]     bv_bits,
  input  [N/G-1:0]   cg_bits,
  output [N-1:0]     snoop_mask
);
  integer g, k;
  reg [N-1:0] expanded;
  always @* begin
    expanded = {N{1'b0}};
    for (g = 0; g < N/G; g = g + 1)
      if (cg_bits[g])
        for (k = 0; k < G; k = k + 1)
          expanded[g*G + k] = 1'b1;
  end
  assign snoop_mask = is_coarse ? expanded : bv_bits;
endmodule

And in VHDL:

-- Representative sharer-set decoder (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_sharer_decode is
  generic ( N : integer := 4; G : integer := 2 );
  port (
    is_coarse  : in  std_logic;
    bv_bits    : in  std_logic_vector(N-1 downto 0);
    cg_bits    : in  std_logic_vector(N/G-1 downto 0);
    snoop_mask : out std_logic_vector(N-1 downto 0)
  );
end entity;
 
architecture rtl of chi_sharer_decode is
  signal expanded : std_logic_vector(N-1 downto 0);
begin
  process (cg_bits)
    variable e : std_logic_vector(N-1 downto 0);
  begin
    e := (others => '0');
    for g in 0 to N/G-1 loop
      if cg_bits(g) = '1' then
        for k in 0 to G-1 loop
          e(g*G + k) := '1';   -- expand the group bit to all its caches
        end loop;
      end if;
    end loop;
    expanded <= e;
  end process;
  snoop_mask <= expanded when is_coarse = '1' else bv_bits;
end architecture;

All three make the coarse decode expand each set group bit to its whole group — a superset of the true holders — while the bit-vector passes through exactly. The DebugLab shows the stale read when a group bit is decoded to a single cache instead.

12. Verification View — the decode is always a superset

The properties that keep sharer tracking safe: the coarse decode covers every cache in a set group, and the snoop mask is a superset.

// Bind to chi_sharer_decode (N=4, G=2).
// 1. A set coarse group bit snoops EVERY cache in that group (full expansion).
property p_group_fully_expanded;
  @(*) is_coarse |-> ( (cg_bits[0] |-> (snoop_mask[0] && snoop_mask[1])) &&
                       (cg_bits[1] |-> (snoop_mask[2] && snoop_mask[3])) );
endproperty
 
// 2. Bit-vector decodes exactly to its bits.
property p_bitvector_exact;
  @(*) (!is_coarse) |-> (snoop_mask == bv_bits);
endproperty
 
// 3. A cleared coarse group snoops none of its members (no needless over-reach beyond set groups).
property p_clear_group_none;
  @(*) (is_coarse && !cg_bits[0]) |-> (!snoop_mask[0] && !snoop_mask[1]);
endproperty

The system point, beyond the checks:

Sharer tracking is where coherence correctness meets area budget, and the encodings are the knob. The deep property is containment: the decoded snoop set must contain the true holders, and every valid encoding is just a different way of guaranteeing that containment at a different storage cost. The bit-vector guarantees it with exact bits; coarse-grain guarantees it by rounding up — snooping whole groups. The verification target is therefore not "is the set exact?" but "is the decoded set a superset?" — which admits cheap, lossy encodings as long as they lose precision upward. The single fatal move is any decode that rounds down, because containment is a one-sided guarantee and a missed holder has no second chance.

• What it proves: set coarse groups expand fully; bit-vector is exact; cleared groups snoop none.
• What it does not prove: the encoding was populated correctly (every holder set a bit) — that is 10.4.
• Bug signature: a set group bit that snoops fewer than all its members — an under-approximation.

13. Testbench — bit-vector and coarse decodes

Decodes both encodings and checks the snoop mask, especially the group expansion.

module tb_chi_sharer_decode;
  localparam N = 4, G = 2;
  logic is_coarse;
  logic [N-1:0] bv_bits, snoop_mask;
  logic [N/G-1:0] cg_bits;
  int errors = 0;
 
  chi_sharer_decode #(.N(N), .G(G)) dut (.*);
 
  task automatic check(input logic ic, input logic [N-1:0] bv, input logic [N/G-1:0] cg,
                       input logic [N-1:0] exp, input string name);
    is_coarse = ic; bv_bits = bv; cg_bits = cg; #1;
    if (snoop_mask !== exp) begin
      errors++; $display("FAIL %s: mask=%b exp=%b", name, snoop_mask, exp);
    end else $display("PASS %s: mask=%b", name, snoop_mask);
  endtask
 
  initial begin
    // Bit-vector: exact.
    check(1'b0, 4'b0010, 2'b00, 4'b0010, "bit-vector RN1 -> snoop RN1 exactly");
    // Coarse: group A (RN0,RN1) set -> snoop both members.
    check(1'b1, 4'b0000, 2'b01, 4'b0011, "coarse group A -> snoop RN0+RN1 (expand)");
    // Coarse: group B set -> snoop RN2+RN3.
    check(1'b1, 4'b0000, 2'b10, 4'b1100, "coarse group B -> snoop RN2+RN3");
    // Coarse: both groups clear -> snoop none.
    check(1'b1, 4'b0000, 2'b00, 4'b0000, "coarse none -> snoop none");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS bit-vector RN1 -> snoop RN1 exactly: mask=0010
PASS coarse group A -> snoop RN0+RN1 (expand): mask=0011
PASS coarse group B -> snoop RN2+RN3: mask=1100
PASS coarse none -> snoop none: mask=0000
ALL TESTS PASSED

14. DebugLab — a coarse group bit decoded as one cache

group A = (RN0, RN1); line held by RN1 -> group A bit SET
write -> decode group A bit as "RN0" (one cache)  <-- wrong
snoop only RN0;  RN1 (the real holder) NOT snooped
RN1 stays with old data -> reads stale -> COHERENCE VIOLATION

15. Common Mistakes

• Decoding a coarse group as one cache. Assumption: a group bit points to a cache. Bug: stale holder (the DebugLab). Prevention: expand to the whole group.
• Under-approximating to save snoops. Assumption: fewer snoops is fine. Bug: a missed holder. Prevention: never a subset of the true holders.
• Over-approximating without accounting for bandwidth. Assumption: extra snoops are free. Bug: wasted bandwidth. Prevention: size groups to balance storage and snoops.
• A bit-vector at huge N. Assumption: exact is always affordable. Bug: excessive storage. Prevention: coarse-grain at scale.
• Populating the encoding incompletely. Assumption: some joins can skip. Bug: under-count (Chapter 10.4). Prevention: record every holder.
• Mixing encodings inconsistently. Assumption: any encoding per line. Bug: mis-decode. Prevention: a defined encoding the decoder matches.

16. Engineering Checklist

• Choose an encoding by the storage-versus-snoop trade — bit-vector or coarse-grain.
• Decode a bit-vector exactly to its per-cache bits.
• Decode a coarse group bit into a snoop of all caches in the group.
• Ensure the decoded snoop set is always a superset of the true holders.
• Never under-approximate — a missed holder reads stale.
• Size groups to balance directory storage against extra snoop bandwidth.

17. Key Takeaways

• The directory encodes the sharer set as a full bit-vector (exact, O(N) storage) or coarse-grain (cheaper, approximate).
• Coarse-grain uses one bit per group; a set bit means some cache in the group may hold the line.
• Coarse decoding expands a group bit to a snoop of the whole group — an over-approximation.
• An encoding may over-approximate (extra snoops, safe) but must never under-approximate (a missed holder, stale).
• Mis-decoding a group bit as one cache under-approximates and breaks coherence.
• Trade storage for snoops, decode as a superset; the model here is representative.

18. Quick Revision

Sharer tracking. The directory encodes which caches share a line as either a full bit-vector — one bit per cache, exact but N bits per line (storage grows with core count) — or coarse-grain — one bit per group of caches, far cheaper, but a set group bit means only that some cache in the group may hold the line. Coarse decoding therefore expands each set group bit into a snoop of every cache in the group, which over-approximates the holders: extra, wasted snoops (a bandwidth cost) but no holder missed. The trade is storage against snoop bandwidth, bounded by one unbreakable rule: an encoding may over-approximate the sharer set (a superset — safe) but must never under-approximate it (a subset), because a holder left out of the decoded set is never snooped on a write and reads stale. The classic bug is decoding a coarse group bit as a single cache instead of the whole group — an under-approximation. Over-approximate safely; expand groups fully. Representative model; 11.4 covers how the directory stores the owner.

Coming Next

Chapter 11.4 — Owner Tracking. Sharer tracking recorded the readers; owner tracking records the one owner. Chapter 11.4 covers how the directory stores the owner ID — a pointer to the single cache holding the dirty line — alongside its tracker entries, and the consistency rule that binds it to the sharer set: the owner must always be one of the recorded sharers, or the directory contradicts itself.