Request Processing

Module 16 · Chapter 16.1 · CHI RTL Design Thinking

Project thread — Module 15 was performance analysis. 16.1 is the HN request pipeline; 16.2 is the RN-F snoop pipeline.

1. Learning Outcomes

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

• Name the stages of a home node's request pipeline — accept, lookup, allocate, act, complete.
• Explain why a request allocates a tracker before launching snoops.
• State that two requests to the same line must be serialized.
• Describe the address-hazard check that stalls a conflicting request.
• Diagnose the directory corruption from concurrent same-address requests.
• Implement a representative address-hazard check in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

The home node is where coherence is decided, and its request pipeline is the RTL that decides it. Every idea from Modules 6–15 — directory lookups, snoops, responses, ordering — is implemented here, in a pipeline that must accept a request, find the line, act on it, and update the directory. Getting the stages right is most of the work; getting the interactions between concurrent requests right is what separates a working home from a subtly broken one.

The critical interaction is the address hazard. The home serializes conflicting accesses per address (Chapter 12.2) — but that is a conceptual guarantee; the pipeline must enforce it with actual logic. If two requests to the same line are allowed to flow through the pipeline concurrently, they both read the directory, both issue snoops, and both write the directory back — and their read-modify-write updates race, so one is lost and the sharer set ends up wrong. The result is a directory that disagrees with the caches, which later causes a snoop to miss a real sharer — a silent coherence violation. This chapter is the pipeline and the hazard check that is its beating heart.

3. Key Terms

4. Previous Chapter Connection

This chapter implements the home's role you have used since Module 5. The directory (Chapter 11.1) is looked up and updated here; snoops (Chapter 9.1) are launched here; the serialization of conflicts (Chapter 12.2) is enforced here. Where those chapters described what the home does, this one is how the RTL does it.

The address hazard is the RTL form of Chapter 12.2's per-address ordering. There, the principle was that the home is the serialization point — conflicting accesses to a line are ordered by it. This chapter shows that ordering is not free: the pipeline must detect the conflict (compare addresses against active trackers) and act on it (stall). A home that assumes serialization "just happens" without the hazard-check logic will process conflicts concurrently and break exactly the ordering Chapter 12.2 promised. This is where a conceptual guarantee becomes gates.

5. Core Concept — a pipeline that serializes conflicts

The home's request pipeline accepts, looks up, allocates a tracker, acts, completes, and updates — and it serializes same-address requests with an address-hazard check.

• The stages. Accept a request flit (link credit) → directory lookup → allocate a tracker → decide and launch an action (snoop / memory) → collect responses → complete to the requester → update the directory → deallocate.
• Allocate before acting. The tracker is allocated before snoops are launched, so returning responses have a place to land and the transaction's state is held across its lifetime.
• Serialize same-address requests. Two requests to the same line must not run concurrently. The home compares a new request's address against all active trackers.
• Stall on a hazard. If the address matches an active tracker, the new request is a hazard — it stalls until that tracker deallocates. Non-conflicting requests proceed in parallel.

The synthesis:

The home's request pipeline is accept → lookup → allocate tracker → act (snoop/memory) → complete → update directory → deallocate. It must serialize requests to the same line: a new request whose address matches an active tracker is a hazard and stalls until that tracker frees. Skip the check and two same-address flows race on the directory — one update is lost, the sharer set is wrong, and coherence breaks.

6. Engineering Mental Model — one editor per document

Think of an office where people edit shared documents (cache lines), coordinated by a manager (the home).

• When someone wants to edit a document, the manager checks it out to them (allocates a tracker), lets them make changes (snoop/act), and checks it back in when done (completes, updates, deallocates).
• Different documents can be edited in parallel — no conflict.
• But if two people ask to edit the same document at once, the manager must not hand it to both. It gives it to the first and makes the second wait until the first checks it back in.
• If the manager forgets to check — hands the same document to both — they each edit their own copy and check in conflicting versions. The second check-in overwrites the first, and the document's revision history is now wrong — a change was lost.

The check-out register is the tracker table; the "is this document already checked out?" test is the address-hazard check. Skip it and concurrent edits to one document corrupt it — exactly what concurrent same-address requests do to a directory entry.

7. Engineering Diagram — the request pipeline

Every request passes the hazard check before proceeding. A same-line conflict stalls; everything else flows through lookup, action, and completion. The check is the gate that turns concurrent requests into serialized per-address access.

8. Engineering Diagram — the request tracker FSM

The tracker holds the transaction from allocate to deallocate, and the address is hazarded the whole time. A new same-line request cannot allocate until this tracker returns to IDLE. The FSM is where the pipeline's per-transaction state lives.

9. Why Concurrent Same-Address Requests Corrupt the Directory

The race, made explicit.

• Each request read-modify-writes the directory. A request reads the sharer/state entry, modifies it (adds/removes a sharer, changes state), and writes it back.
• Concurrent flows read the same old value. Two same-line requests running in parallel both read the directory entry before either writes — so both see the old sharer set.
• The second write overwrites the first. Each computes its update from the old value and writes it. The later write wins, discarding the earlier request's change — a lost update.
• The directory now lies. The sharer set is missing a sharer (or holds a stale one). A later snoop misses a real sharer (a coherence hole — that cache is never invalidated) or snoops a non-sharer (waste). Coherence is broken.

The point to carry:

The directory entry is shared mutable state, and two transactions updating it concurrently is a textbook read-modify-write race — the same hazard as two threads doing count++ without a lock. The fix is the same in principle: mutual exclusion over the contended resource, which here is per-address rather than a single global lock. The address-hazard check is that per-address lock: it ensures at most one in-flight transaction per line, so the read-modify-write of that line's directory entry is atomic by construction — no second reader can observe the pre-write value. This is why serialization must be per address and not coarser (a global lock would serialize everything and kill throughput) nor finer (there is nothing finer than a line to lock). The home's whole coherence correctness rests on this one invariant — one active transaction per line — and the hazard check is the gate that maintains it. Remove the gate and every same-line concurrency becomes a lost update.

10. Processing a Request — with and without the hazard check

Two requests, A and B, both to line X, arriving close together.

1. With the check — A allocates. Request A passes the hazard check (no active tracker for X), allocates a tracker, and begins its flow. Line X is now hazarded.
2. With the check — B stalls. Request B arrives for X, the hazard check finds A's active tracker, and B stalls. It waits.
3. With the check — A completes, B proceeds. A finishes, updates the directory, and deallocates. X is no longer hazarded, so B allocates and runs — reading A's updated directory. Both updates land. Correct.
4. Without the check — both run. A and B both allocate for X and run concurrently. Both read the old directory entry, both snoop, both compute an update from the old value.
5. Without the check — a lost update. A writes its update; B writes its update (from the old value), overwriting A's. The directory now reflects only B — A's sharer change is lost. A later snoop misses the sharer A added → stale data used.

The check made B see A's result; without it, B clobbered A's result. The DebugLab is steps 4–5.

11. RTL / Hardware View — the address-hazard check

A new request's address is compared against all active trackers; a match stalls it. Representative.

// Representative address-hazard check (educational).
// Before allocating a tracker for a new request, compare its address against ALL active
// trackers. A match is a HAZARD -> the request must STALL (not allocate) until that
// tracker deallocates. This serializes same-line requests so their directory
// read-modify-writes are atomic. Without it, concurrent same-line updates race.
module chi_req_hazard #(parameter NTRK = 16, parameter AW = 44) (
  input  logic              clk, rst_n,
  input  logic              req_valid,        // a new request is offered
  input  logic [AW-1:0]     req_addr,         // its (line) address
  input  logic [NTRK-1:0]   trk_active,       // which trackers are in use
  input  logic [AW-1:0]     trk_addr [NTRK],  // each active tracker's address
  output logic              hazard,           // same-line conflict -> must stall
  output logic              can_allocate      // clear to allocate this request
);
  always_comb begin
    hazard = 1'b0;
    for (int i = 0; i < NTRK; i++)
      if (trk_active[i] && (trk_addr[i] == req_addr))
        hazard = 1'b1;                         // an active tracker holds this line
  end
  // Allocate only when there is no same-line hazard (and the request is valid).
  assign can_allocate = req_valid && !hazard;
endmodule

The same behavior in Verilog-2001 (flattened tracker addresses):

// Representative address-hazard check (Verilog-2001).
module chi_req_hazard #(parameter NTRK = 16, parameter AW = 44) (
  input                    clk, rst_n, req_valid,
  input  [AW-1:0]          req_addr,
  input  [NTRK-1:0]        trk_active,
  input  [NTRK*AW-1:0]     trk_addr_flat,
  output reg               hazard,
  output                   can_allocate
);
  integer i;
  always @* begin
    hazard = 1'b0;
    for (i = 0; i < NTRK; i = i + 1)
      if (trk_active[i] && (trk_addr_flat[i*AW +: AW] == req_addr))
        hazard = 1'b1;
  end
  assign can_allocate = req_valid & ~hazard;
endmodule

And in VHDL:

-- Representative address-hazard check (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_req_hazard is
  generic ( NTRK : integer := 16; AW : integer := 44 );
  port (
    clk, rst_n   : in  std_logic;
    req_valid    : in  std_logic;
    req_addr     : in  std_logic_vector(AW-1 downto 0);
    trk_active   : in  std_logic_vector(NTRK-1 downto 0);
    trk_addr     : in  std_logic_vector(NTRK*AW-1 downto 0);  -- NTRK addresses packed
    hazard       : out std_logic;
    can_allocate : out std_logic
  );
end entity;
 
architecture rtl of chi_req_hazard is
begin
  process (req_valid, req_addr, trk_active, trk_addr)
    variable hz : std_logic;
  begin
    hz := '0';
    for i in 0 to NTRK-1 loop
      if trk_active(i) = '1' and
         trk_addr((i+1)*AW-1 downto i*AW) = req_addr then
        hz := '1';
      end if;
    end loop;
    hazard       <= hz;
    can_allocate <= req_valid and (not hz);
  end process;
end architecture;

All three compare the request address against every active tracker and block allocation on a match — so at most one transaction per line is ever active. The DebugLab is a pipeline that allocates without this check.

12. Verification View — one active transaction per line

The properties enforce serialization: no allocate on a hazard, and never two active trackers for one address.

// Bind to chi_req_hazard (and the tracker table).
// 1. A request is never allocated while a same-line tracker is active.
property p_no_allocate_on_hazard;
  @(posedge clk) disable iff (!rst_n)
    can_allocate |-> !hazard;
endproperty
 
// 2. At most one active tracker holds any given address (the core invariant).
property p_one_active_per_line;
  @(posedge clk) disable iff (!rst_n)
    (trk_active[i] && trk_active[j] && i != j) |-> (trk_addr[i] != trk_addr[j]);
endproperty
 
// 3. A hazard is asserted whenever an active tracker matches the request address.
property p_hazard_detects_conflict;
  @(posedge clk) disable iff (!rst_n)
    (req_valid && trk_active[i] && trk_addr[i] == req_addr) |-> hazard;
endproperty

The system point, beyond the checks:

The invariant p_one_active_per_line is the linchpin of the entire home node, and it is worth appreciating how much correctness rides on it. Because at most one transaction per line is ever active, every downstream stage can treat the directory entry for its line as private — the lookup reads a value no other in-flight transaction will change, the action operates on stable sharer information, and the update writes back without a concurrent writer. The single-active-transaction invariant is what makes the read-modify-write atomic without any explicit locking hardware — the hazard check at the front of the pipeline is the lock, held for the tracker's lifetime and keyed by address. This is a powerful architectural simplification: serialize at one point (allocation) and every stage afterward is free of concurrency reasoning for its line. It also means the invariant must hold absolutely — a single escaped concurrent same-line pair corrupts the directory, and the corruption is silent (a missing sharer surfaces only later, as a stale read). So verification here is not about the happy path but about proving the invariant can never be violated, across every arrival timing of conflicting requests.

• What it proves: no allocation on a hazard; at most one active tracker per line.
• What it does not prove: the directory update logic itself is correct — that is the action/update stages.
• Bug signature: two active trackers with the same address — the serialization invariant broken.

13. Testbench — a same-line request must stall

Allocates a tracker for a line, then offers a second request to the same line and checks it is hazarded.

module tb_chi_req_hazard;
  localparam NTRK = 4, AW = 16;
  logic clk = 0, rst_n = 1, req_valid;
  logic [AW-1:0] req_addr;
  logic [NTRK-1:0] trk_active;
  logic [AW-1:0] trk_addr [NTRK];
  logic hazard, can_allocate;
  int errors = 0;
 
  chi_req_hazard #(.NTRK(NTRK), .AW(AW)) dut (.*);
  always #5 clk = ~clk;
 
  initial begin
    trk_active = 4'b0001;               // tracker 0 active
    trk_addr[0] = 16'hABCD; trk_addr[1]=0; trk_addr[2]=0; trk_addr[3]=0;
 
    // A new request to a DIFFERENT line -> no hazard, may allocate.
    req_valid = 1; req_addr = 16'h1234; #1;
    if (hazard || !can_allocate) begin errors++; $display("FAIL different line hazarded"); end
    else $display("PASS different line: can allocate");
 
    // A new request to the SAME line as tracker 0 -> hazard, must NOT allocate.
    req_addr = 16'hABCD; #1;
    if (!hazard || can_allocate) begin errors++; $display("FAIL same line not hazarded (would race!)"); end
    else $display("PASS same line hazarded: request stalls");
 
    // Once tracker 0 deallocates, the same-line request may allocate.
    trk_active = 4'b0000; #1;
    if (hazard || !can_allocate) begin errors++; $display("FAIL still hazarded after dealloc"); end
    else $display("PASS after dealloc: same line can allocate");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS different line: can allocate
PASS same line hazarded: request stalls
PASS after dealloc: same line can allocate
ALL TESTS PASSED

14. DebugLab — no address-hazard check

requests A and B both target line X, arrive within a few cycles
pipeline (no hazard check): allocates BOTH -> both process concurrently
  A: read dir(X) = sharers {c0}; add c1; write {c0,c1}
  B: read dir(X) = sharers {c0}  (BEFORE A's write); add c2; write {c0,c2}
  -> B's write OVERWRITES A's -> dir(X) = {c0,c2}  (c1 LOST)
later: write to X snoops {c0,c2} -> c1 NOT snooped -> c1 keeps stale line -> uses it
correct: hazard check -> B stalls until A deallocates -> B reads {c0,c1} -> {c0,c1,c2}

15. Common Mistakes

• No hazard check. Assumption: serialization is automatic. Bug: directory race (the DebugLab). Prevention: compare against active trackers.
• Allocating before checking. Assumption: allocate then resolve. Bug: two active same-line trackers. Prevention: check, then allocate.
• Comparing full addresses, not lines. Assumption: byte address. Bug: same line, different offset, not hazarded. Prevention: compare line addresses.
• Launching snoops before allocating. Assumption: order is free. Bug: responses with no tracker. Prevention: allocate first.
• Global instead of per-address lock. Assumption: one lock is simpler. Bug: throughput collapse. Prevention: hazard per line.
• Freeing the tracker before completion. Assumption: early free is fine. Bug: hazard window closes early. Prevention: deallocate on complete (Chapter 16.5).

16. Engineering Checklist

• Stage the pipeline: accept → hazard check → lookup → allocate → act → complete → update.
• Allocate a tracker before launching snoops.
• Compare each request's line address against all active trackers.
• Stall a same-line request until the conflicting tracker deallocates.
• Maintain one active transaction per line as an invariant.
• Keep the address hazarded for the tracker's whole lifetime.

17. Key Takeaways

• The home's request pipeline: accept → lookup → allocate → act → complete → update.
• A tracker is allocated before snoops so responses have a home.
• Two requests to the same line must be serialized.
• The address-hazard check stalls a conflicting request until the prior one frees.
• Skipping it lets concurrent same-line requests race on the directory — a lost update.
• One active transaction per line is the invariant; the model here is representative.

18. Quick Revision

Request processing. A home node's request pipeline is: accept a request flit (link credit) → directory lookup → allocate a tracker → decide and launch an action (snoop peers / read memory) → collect responses → complete to the requester → update the directory → deallocate. The tracker is allocated before snoops so returning responses have a place to land, and it holds the transaction's state from allocate to deallocate. The correctness crux is address hazarding: two requests to the same cache line must not be processed concurrently, because each does a read-modify-write of the line's directory entry, and two overlapping flows both read the old value before either writes — so the second write overwrites the first, losing an update and leaving the sharer set wrong. A later snoop then misses a real sharer (a coherence hole — stale data used) or snoops a non-sharer. The home must compare each incoming request's line address against all active trackers and stall a same-line request until the conflicting tracker deallocates — maintaining the invariant of one active transaction per line, which makes each directory read-modify-write atomic with no explicit lock. This is the RTL enforcement of Chapter 12.2's per-address serialization; the guarantee does not hold without the check. Representative model; 16.2 covers the RN-F snoop pipeline.

Coming Next

Chapter 16.2 — Snoop Processing. The home launches snoops; the RN-F must process them. Chapter 16.2 covers the snoop-processing pipeline at a fully-coherent request node — how it looks up the snooped line, forms the response and its state transition, and why a snoop that finds a dirty line must return the data with its response, not just a state acknowledgment, or the only dirty copy is lost.