Congestion Handling

Module 14 · Chapter 14.5 · CHI Flow Control

Project thread — 14.4 was implicit backpressure on the link buffer. 14.5 is explicit retry for a protocol resource; 14.6 optimizes throughput.

1. Learning Outcomes

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

• Distinguish link credits (buffer) from protocol credits (a tracker resource).
• Explain that a RetryAck means the home received a request but has no resource to service it.
• State that the requester must wait for a PCrdGrant before resending — not resend immediately.
• Describe the PCrdGrant as the home reserving a slot and inviting the retry.
• Diagnose the livelock from spin-retrying without waiting for the grant.
• Implement a representative retry state machine in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

There are two ways a home node can be too busy, and they need different responses. If its link buffer is full, link credits stall the sender — backpressure, and the answer is to wait (Chapter 14.4). But a home can accept a request flit into its buffer and still be unable to act on it, because acting requires a tracker slot — one of a finite pool of outstanding-transaction entries — and that pool can be empty while the buffer has room. Link credits do not protect that resource; a separate mechanism does.

That mechanism is explicit retry. The home returns a RetryAck — "received, but I cannot service this; retry later" — and, crucially, the requester must not resend on its own schedule. It waits for the home to send a PCrdGrant, a protocol credit that says "I have reserved a slot for you — now resend." Wait for the grant and the retry succeeds on the first attempt. Spin-retry without it and every resend slams into the still-full tracker, is rejected again, and the requester livelocks — busy forever, progressing never. This chapter is the retry handshake and why the grant is mandatory.

3. Key Terms

4. Previous Chapter Connection

Chapter 14.4 covered implicit flow control — link credits and backpressure, protecting the receive buffer. This chapter covers explicit flow control for a different resource: the home's tracker. The two are complementary — link credits gate whether a flit can be received; protocol credits gate whether a received request can be allocated.

The distinction sharpens the retry idea. Under backpressure the requester holds a flit it never sent (Chapter 14.4); here the request was sent and received, but bounced with a RetryAck, and the requester must re-send it later on invitation. The mechanisms rhyme — both make the requester wait for a credit — but the credit is different (link vs protocol) and the signalling is different (implicit withholding vs an explicit RetryAck then PCrdGrant). This chapter is the explicit half, and the last flow-control mechanism before throughput (Chapter 14.6).

5. Core Concept — RetryAck, then wait for the grant

When the home has no tracker slot for a received request, it returns a RetryAck, and the requester must wait for a PCrdGrant before resending.

• Two resources, two protections. A link credit admits a flit to the buffer; a tracker slot lets the home process it. The buffer can have room while the tracker is full.
• RetryAck: received but not serviced. With no tracker slot, the home returns RetryAck — it took the flit but cannot allocate it. The request is bounced, not queued.
• Wait for the PCrdGrant. The requester enters a retry-pending state and waits. It does not resend. When the home frees a slot, it sends a PCrdGrant (with a PCrdType) — "a slot is reserved for you."
• Resend once, with the credit. On the grant, the requester resends the request exactly once, tagged with the granted P-Credit. This time a slot is guaranteed, so it succeeds.

The synthesis:

A RetryAck means the home received a request but had no tracker slot to service it. The requester must not resend on its own — it waits for a PCrdGrant, the home's signal that a slot is now reserved, then resends once with that protocol credit. Spin-retrying without the grant hammers a still-full tracker and livelocks.

6. Engineering Mental Model — a callback list at a busy clinic

Think of a walk-in clinic (the home) with a fixed number of exam rooms (tracker slots).

• You arrive and check in (send a request). The front desk takes your details (the link buffer had room), but every room is occupied (the tracker is full). They cannot see you now.
• They do not just turn you away permanently. They say "we'll call you when a room opens" (RetryAck) and put you on a callback list.
• The right thing to do is wait for the call (PCrdGrant). When a room frees, they call you specifically — a room is now reserved for you — and you go in once. Smooth.
• The wrong thing is to keep walking back to the desk every minute asking "is a room free yet?" (spin-retry). Every trip, the desk is still full, tells you no again, and now the desk itself is mobbed with people re-asking — so even rooms that free up cannot be assigned because staff are busy fending off the crowd. Nobody gets seen. That is livelock.

Wait for the call. The PCrdGrant is the call; spin-retrying is pacing back to a desk that will tell you no until it is ready to tell you yes.

7. Engineering Diagram — RetryAck and the invited retry

The request bounces with RetryAck, the requester waits, the home grants a P-Credit when a slot frees, and the requester resends once with the credit — accepted. The self-message is the mandatory wait. The DebugLab replaces it with immediate, repeated resends.

8. Link Credits vs Protocol Credits

The two mechanisms compared.

The rule to carry: buffer room is not resource room, and each is protected separately. Link credits answer "can this flit be received?"; protocol credits answer "can this request be allocated?" A request can pass the first gate and fail the second — accepted into the buffer, then bounced for lack of a tracker slot. The RetryAck/PCrdGrant loop is the resource gate, and like the buffer gate it makes the requester wait for a credit — but the credit is explicitly granted, not silently returned.

9. Why the Grant Is Mandatory

The reasoning behind waiting for PCrdGrant.

• RetryAck is not "retry now." It means "I cannot service this yet." Resending immediately re-asks a question whose answer is still no — the tracker is still full.
• PCrdGrant is a reservation. When the home frees a slot, the grant reserves it for this requester. A resend after the grant is guaranteed a slot — it succeeds first try.
• Waiting decouples retries from congestion. The home paces grants to its own freeing of slots, so retries arrive exactly when they can be served — no wasted attempts.
• Spin-retrying is positive feedback. Resends without a grant flood the home with requests it must RetryAck again, consuming link credits and bandwidth on rejections — a livelock amplifying the congestion (echoing Chapter 14.4's retry storm).

The point to carry:

The PCrdGrant turns retry from polling into notification, and that inversion is the whole point. Polling — resend, get rejected, resend — spends work in proportion to how long the resource is unavailable, which is exactly backwards: the more congested the home, the more useless retries it must field, so the busier it is the more its scarce capacity is wasted on saying "no." Notification spends zero work while waiting and exactly one resend when the resource is ready, so cost is independent of congestion duration. The home is the only party that knows when a slot frees, so it must be the one to initiate the retry — the requester cannot guess. This is a recurring principle in resource arbitration: the holder of the resource grants access; the waiter waits to be granted. A waiter that polls instead of waiting converts a solved allocation problem into a livelock, because it forces the grantor to spend its recovery capacity rejecting the very requests that are preventing it from recovering.

10. A Retry Episode — bounce, wait, resend

The tracker is full; the request rides out the resource shortage.

1. RN sends ReadShared. The flit reaches the HN (a link credit was available); the HN's buffer accepts it.
2. HN's tracker is full. Every tracker slot is occupied by an outstanding transaction. The HN cannot allocate this request.
3. HN returns RetryAck, PCrdType = P. "Received, but no slot — retry later, with a type-P credit." The request is bounced.
4. RN waits — retry-pending. The RN records the pending retry and waits for a type-P grant. It resends nothing.
5. HN frees a slot, sends PCrdGrant, PCrdType = P. An outstanding transaction completes; the HN reserves the freed slot and grants a type-P credit.
6. RN resends ReadShared once, with the P-Credit. A slot is reserved, so the HN allocates it immediately. The transaction proceeds normally.

The request succeeded on its one resend because the RN waited for the grant. The DebugLab is an RN that, at step 4, resends immediately and repeatedly — every attempt bouncing off the full tracker.

11. RTL / Hardware View — the retry state machine

The requester sends, and on RetryAck waits for a matching PCrdGrant before resending exactly once. Representative FSM.

// Representative requester retry FSM (educational).
// On RetryAck the requester enters RETRY_WAIT and MUST wait for a matching PCrdGrant
// before resending. It never resends while merely waiting -- spin-retrying floods the
// still-full home and livelocks. The grant reserves a slot; the resend then succeeds.
typedef enum logic [1:0] { IDLE, SENT, RETRY_WAIT, RESEND } rstate_e;
 
module chi_retry_fsm (
  input  logic  clk, rst_n,
  input  logic  want_req,       // requester has a request to issue
  input  logic  retry_ack,      // home returned RetryAck (no tracker slot)
  input  logic  pcrd_grant,     // home granted a protocol credit (matching type)
  input  logic  accepted,       // home accepted the request (allocated a slot)
  output logic  send_req,       // drive a request flit this cycle
  output rstate_e state
);
  rstate_e st_q;
  assign state    = st_q;
  // Send on the initial issue OR on a resend -- but a resend requires we are in RESEND,
  // which is reachable ONLY after a PCrdGrant. Never send from RETRY_WAIT directly.
  assign send_req = (st_q == IDLE && want_req) || (st_q == RESEND);
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) st_q <= IDLE;
    else case (st_q)
      IDLE:       st_q <= (want_req)   ? SENT       : IDLE;
      SENT:       st_q <= retry_ack    ? RETRY_WAIT :        // bounced -> wait for grant
                          accepted      ? IDLE       : SENT;  // accepted -> done
      RETRY_WAIT: st_q <= pcrd_grant   ? RESEND     : RETRY_WAIT; // WAIT for the grant
      RESEND:     st_q <= accepted      ? IDLE       : SENT;  // resent once with the credit
      default:    st_q <= IDLE;
    endcase
  end
endmodule

The same behavior in Verilog-2001:

// Representative requester retry FSM (Verilog-2001).
module chi_retry_fsm (
  input  wire       clk, rst_n, want_req, retry_ack, pcrd_grant, accepted,
  output wire       send_req,
  output wire [1:0] state
);
  localparam IDLE = 2'd0, SENT = 2'd1, RETRY_WAIT = 2'd2, RESEND = 2'd3;
  reg [1:0] st_q;
  assign state    = st_q;
  assign send_req = (st_q == IDLE && want_req) || (st_q == RESEND);
 
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) st_q <= IDLE;
    else case (st_q)
      IDLE:       st_q <= want_req   ? SENT       : IDLE;
      SENT:       st_q <= retry_ack  ? RETRY_WAIT : (accepted ? IDLE : SENT);
      RETRY_WAIT: st_q <= pcrd_grant ? RESEND     : RETRY_WAIT;   // wait for grant
      RESEND:     st_q <= accepted   ? IDLE       : SENT;
      default:    st_q <= IDLE;
    endcase
  end
endmodule

And in VHDL:

-- Representative requester retry FSM (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_retry_fsm is
  port (
    clk, rst_n                          : in  std_logic;
    want_req, retry_ack, pcrd_grant, accepted : in std_logic;
    send_req                            : out std_logic;
    state                               : out std_logic_vector(1 downto 0)
  );
end entity;
 
architecture rtl of chi_retry_fsm is
  constant IDLE : std_logic_vector(1 downto 0) := "00";
  constant SENT : std_logic_vector(1 downto 0) := "01";
  constant RETRY_WAIT : std_logic_vector(1 downto 0) := "10";
  constant RESEND : std_logic_vector(1 downto 0) := "11";
  signal st_q : std_logic_vector(1 downto 0) := IDLE;
begin
  state    <= st_q;
  send_req <= '1' when ((st_q = IDLE and want_req = '1') or st_q = RESEND) else '0';
 
  process (clk, rst_n)
  begin
    if rst_n = '0' then
      st_q <= IDLE;
    elsif rising_edge(clk) then
      case st_q is
        when IDLE =>
          if want_req = '1' then st_q <= SENT; end if;
        when SENT =>
          if retry_ack = '1' then st_q <= RETRY_WAIT;    -- bounced: wait for grant
          elsif accepted = '1' then st_q <= IDLE; end if;
        when RETRY_WAIT =>
          if pcrd_grant = '1' then st_q <= RESEND; end if; -- wait for the grant
        when others =>  -- RESEND
          if accepted = '1' then st_q <= IDLE; else st_q <= SENT; end if;
      end case;
    end if;
  end process;
end architecture;

In all three, the path from RETRY_WAIT to a resend passes only through a PCrdGrant — there is no edge that resends while still waiting. The DebugLab adds exactly that missing edge: resending straight from the wait state.

12. Verification View — no resend without a grant

The properties that keep retry sound: a resend follows a grant, never a bare RetryAck.

// Bind to chi_retry_fsm.
// 1. A resend (RESEND state) is only reached via a PCrdGrant.
property p_resend_needs_grant;
  @(posedge clk) disable iff (!rst_n)
    (state == RESEND) |-> $past(pcrd_grant);
endproperty
 
// 2. In RETRY_WAIT, no request is sent (no spin-retry).
property p_no_send_while_waiting;
  @(posedge clk) disable iff (!rst_n)
    (state == RETRY_WAIT) |-> !send_req;
endproperty
 
// 3. A RetryAck moves to waiting, not to an immediate resend.
property p_retryack_goes_to_wait;
  @(posedge clk) disable iff (!rst_n)
    (state == SENT && retry_ack) |=> (state == RETRY_WAIT);
endproperty

The system point, beyond the checks:

The key property — no send in RETRY_WAIT — is what makes retry a bounded operation instead of an unbounded one. With it, each request costs at most two transmissions: the original and, after a grant, exactly one resend. Without it, a request can be transmitted an unbounded number of times, once per spin, and the count grows with congestion — precisely when the fabric can least afford it. That unboundedness is the signature of livelock: the system is doing work, so it does not look hung, but the work is self-cancelling and progress is zero. Verifying p_no_send_while_waiting therefore proves more than a state-machine detail; it proves the retry mechanism terminates with bounded cost regardless of how long the resource is scarce. And it composes with the grant guarantee: the home will eventually free a slot (its own transactions complete) and issue the grant, so RETRY_WAIT is exited in bounded time — waiting is safe and finite, which together mean the request always eventually succeeds.

• What it proves: a resend requires a prior grant; no send occurs while waiting; RetryAck leads to waiting.
• What it does not prove: the home eventually grants — a home-side liveness obligation.
• Bug signature: send_req asserted in RETRY_WAIT — a spin-retry.

13. Testbench — a RetryAck must not trigger an immediate resend

Bounces a request and checks the requester waits for the grant.

module tb_chi_retry_fsm;
  logic clk = 0, rst_n = 0, want_req = 0, retry_ack = 0, pcrd_grant = 0, accepted = 0;
  logic send_req;
  logic [1:0] state;
  localparam IDLE = 2'd0, SENT = 2'd1, RETRY_WAIT = 2'd2, RESEND = 2'd3;
  int errors = 0, sends = 0;
 
  chi_retry_fsm dut (.*);
  always #5 clk = ~clk;
 
  // Count every request transmission.
  always @(posedge clk) if (rst_n && send_req) sends++;
 
  initial begin
    @(posedge clk) rst_n = 1;
 
    // Issue a request.
    @(posedge clk) want_req = 1;
    @(posedge clk) want_req = 0;   // -> SENT
 
    // Home bounces it: RetryAck. Requester must go to RETRY_WAIT and NOT resend.
    @(posedge clk) retry_ack = 1;
    @(posedge clk) retry_ack = 0;
 
    // Sit in RETRY_WAIT for several cycles with NO grant -> must not resend.
    repeat (5) begin
      @(posedge clk);
      if (state == RETRY_WAIT && send_req) begin errors++; $display("FAIL spin-retry: sent while waiting"); end
    end
    $display("PASS no resend while waiting (state=%0d, sends so far=%0d)", state, sends);
 
    // Now the grant arrives -> exactly one resend.
    @(posedge clk) pcrd_grant = 1;
    @(posedge clk) pcrd_grant = 0;   // -> RESEND -> send
    @(posedge clk) accepted = 1;
    @(posedge clk) accepted = 0;
 
    if (sends != 2) begin errors++; $display("FAIL expected 2 sends (orig + 1 resend), got %0d", sends); end
    else $display("PASS bounded retry: exactly 2 sends");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS no resend while waiting (state=2, sends so far=1)
PASS bounded retry: exactly 2 sends
ALL TESTS PASSED

14. DebugLab — spin-retrying without waiting for the grant

RN sends ReadShared -> HN tracker FULL -> RetryAck (PCrdType = P)
buggy RN: immediately resends ReadShared (no wait for grant)
  -> HN tracker STILL full -> RetryAck again
  -> RN resends again -> RetryAck again -> ... (tight loop)
  -> HN flooded with retries, spends capacity emitting RetryAcks
  -> grants delayed -> livelock: busy, zero progress
correct: RetryAck -> WAIT for PCrdGrant(P) -> resend ONCE with the P-credit

15. Common Mistakes

• Spin-retrying after RetryAck. Assumption: retry means retry now. Bug: livelock (the DebugLab). Prevention: wait for PCrdGrant.
• Resending without the P-Credit. Assumption: any resend works. Bug: bounced again or dropped. Prevention: resend with the granted credit.
• Confusing RetryAck with backpressure. Assumption: same as a link stall. Bug: wrong response. Prevention: RetryAck is explicit; wait for a grant, not a link credit.
• Ignoring PCrdType. Assumption: any grant matches. Bug: mis-paired credit. Prevention: match grant type to the retry.
• Unbounded resends. Assumption: keep trying. Bug: cost grows with congestion. Prevention: bounded — one resend per grant.
• No home-side grant guarantee. Assumption: the requester self-recovers. Bug: never invited. Prevention: the home must eventually grant.

16. Engineering Checklist

• Treat a RetryAck as "received, no resource" — not "retry now."
• Enter a retry-pending state and wait for a PCrdGrant.
• Do not resend while waiting — no spin-retry.
• Resend exactly once on the grant, tagged with the P-Credit.
• Match the PCrdType of the grant to the pending retry.
• Confirm each request costs at most two transmissions — bounded retry.

17. Key Takeaways

• A RetryAck means the home received a request but had no tracker slot.
• Link credits protect the buffer; protocol credits protect the tracker.
• The requester must wait for a PCrdGrant before resending — not resend immediately.
• The PCrdGrant reserves a slot and invites the retry; the resend then succeeds.
• Spin-retrying floods a full tracker and livelocks — busy, no progress.
• Wait to be granted, resend once; the model here is representative.

18. Quick Revision

Congestion handling. Beyond the link buffer (protected by link credits, Chapters 14.1–14.4), a home node needs a tracker slot — one of a finite pool of outstanding-transaction entries — to process a request, and that pool can be full even when the buffer has room. When it is, the home accepts the flit but returns a RetryAck: "received, but no resource — retry later." The requester must not resend on its own; it enters a retry-pending state and waits for a PCrdGrant (a protocol credit of a matching PCrdType), the home's signal that it has reserved a slot. Only then does the requester resend the request exactly once, tagged with that P-Credit — and it succeeds, because a slot is guaranteed. The failure to avoid: spin-retrying — resending the moment a RetryAck arrives, without the grant. Every premature resend hits the still-full tracker, is RetryAck'd again, and floods the home with rejections, consuming the capacity it needs to complete transactions and issue grants — a livelock: links busy, progress zero. Retry is notification, not polling — the home invites the retry when it can serve it. Wait for the grant; resend once. Representative model; 14.6 covers throughput optimization.

Coming Next

Chapter 14.6 — Throughput Optimisation. Flow control keeps traffic correct; the last chapter of the module makes it fast. Chapter 14.6 covers throughput optimisation — why a single outstanding request wastes bandwidth, how pipelining many outstanding requests fills the latency window, and how Little's Law sets the number of outstanding transactions needed to saturate a link.