Outstanding Requests

Module 16 · Chapter 16.6 · CHI RTL Design Thinking

Project thread — 16.5 was the tracker table. 16.6 bounds outstanding requests and closes the module; 17.1 opens verification.

1. Learning Outcomes

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

• State that a node's outstanding-request count is bounded by the tracker and ID capacity.
• Distinguish a link credit (send) from a tracker entry and TxnID (track).
• Explain why the issue gate must check all three resources, not just the credit.
• Describe the orphan and alias from issuing an untrackable request.
• Diagnose a tracker overrun from an issue gate that checks only the link credit.
• Implement a representative issue gate in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Issuing a request is not just sending a flit — it is starting a transaction that will return a response the node must match and process. Sending needs a link credit (the receiver's buffer has room, Chapter 14.1); tracking needs a tracker entry (somewhere to hold the transaction's state, Chapter 16.5) and a unique TxnID (so the response can be correlated back, Chapter 13.4). These are different resources, and issue requires all of them.

The trap is gating issue on the link credit alone — the most visible resource, the one that obviously governs whether the flit can be sent. A node that does this can launch a request it cannot track: no free tracker entry, or no free TxnID. When the response returns, there is no entry for it (an orphan — the transaction hangs), or its TxnID collides with another in-flight transaction (an alias — the response is applied to the wrong transaction, corrupting both). The number of outstanding requests must be bounded to the tracker/ID capacity by the issue gate itself. This closing chapter is that gate — the RTL that keeps a node from starting more than it can finish.

3. Key Terms

4. Previous Chapter Connection

This chapter bounds what Chapter 16.5 tracks. The tracker is finite; this chapter ensures a node never issues more transactions than the tracker can hold — the front-end admission control for the back-end table. It also completes the resource story of Module 14: link credits (Chapters 14.1–14.2) govern sending, and this chapter adds the tracker/ID resources that govern tracking.

The two-resource distinction directly echoes Chapter 14.5. There, a link credit (buffer) was different from a protocol credit (a home's tracker slot) — and issuing on one while lacking the other caused retries. Here, the same shape appears at the issuer: a link credit (send) is different from a tracker entry and TxnID (track), and issuing on the credit alone overruns the tracker. Both chapters teach the same lesson — a resource that lets you start an action is not the same as the resource that lets you finish it — applied once at the completer (14.5) and once at the requester (16.6). This chapter closes the module on that idea.

5. Core Concept — gate issue on all three resources

A request may be issued only when the node has a link credit (to send), a free tracker entry (to track), and a free unique TxnID (to correlate) — bounding outstanding to the tracker/ID capacity.

• Sending needs a link credit. The receiver's buffer must have room for the request flit (Chapter 14.1) — else the flit overflows.
• Tracking needs a tracker entry. The transaction's state (its expected-response mask, address, type) must have an entry to live in (Chapter 16.5) — else the response has nowhere to land.
• Correlation needs a unique TxnID. The response must carry a TxnID that maps unambiguously back to this transaction (Chapter 13.4) — else it aliases onto another.
• Issue requires all three. The issue gate permits a request only when a link credit, a free tracker entry, and a free TxnID are all available — bounding the outstanding count to the tracker/ID capacity.

The synthesis:

A node may issue a request only when it has a link credit (send), a free tracker entry (track), and a free unique TxnID (correlate) — all three. These are different resources: a credit governs sending, the tracker and ID govern tracking. Gating on the credit alone lets the node issue a request it cannot track — the response returns to no entry (orphan → hang) or a reused ID (alias → wrong transaction). Bound outstanding to the tracker/ID capacity.

6. Engineering Mental Model — booking a delivery you can receive

Think of ordering packages you must personally sign for at home (the responses).

• To place an order you need the store to have stock and a delivery slot (the link credit — the send side works).
• But to receive the package you also need to be home to sign (a tracker entry — you can handle the return) and a way to know which order the package is (a unique order number — the TxnID).
• If you place orders based only on "the store can ship" — ignoring whether you can be home to receive them — packages arrive with no one to sign (orphans, returned to sender — your order never completes), or two orders share the same order number (aliased — the courier hands you one and marks the other delivered).
• The right rule: place an order only when the store can ship and you have a free signing slot and a unique order number. Then every package that ships has someone to receive it and a number to identify it.

The signing slot is the tracker entry; the order number is the TxnID. Ordering on "can ship" alone floods you with packages you cannot receive — orphans and mixups.

7. Engineering Diagram — the issue gate

The gate is an AND of three availabilities — credit, tracker entry, TxnID. Only when all are present does the request issue, allocating the tracker and ID. Checking only the credit (one input) is the bug — it lets issues through that the tracker cannot back.

8. The Three Resources Compared

Each resource, what it governs, and the failure if it is missing.

The rule to carry: each resource guards a different stage of a transaction's life, and all three are needed to issue. The link credit guards arrival at the receiver; the tracker entry guards the return trip home; the TxnID guards identifying the return. A request that satisfies only the credit will send fine and fail on return — either orphaned (no entry) or aliased (reused ID). The issue gate must check all three so that every issued request is sendable, trackable, and correlatable — and the outstanding count is thereby bounded to the scarcest of the tracker and ID capacities.

9. Why a Credit-Only Gate Overruns the Tracker

The failure of checking one resource.

• Credits and trackers are decoupled. Link credits return as the receiver drains its buffer; tracker entries free as this node's transactions complete. They run on different clocks of availability.
• Credit available, tracker full. The receiver may have buffer room (credit available) while this node's tracker is full (all transactions still outstanding). A credit-only gate issues anyway.
• The response has nowhere to land. The issued request will return a response, but there is no tracker entry for it — it is orphaned (dropped), and the transaction hangs waiting.
• Or the TxnID collides. If issuing reused a TxnID already in flight (because the ID space was exhausted but unchecked), the response matches two transactions — it is aliased onto the wrong one, corrupting both.

The point to carry:

This bug is the issuer-side mirror of the completer-side retry (Chapter 14.5), and seeing them together completes the resource-management picture of CHI. At the completer, a request could be received (buffer credit) but not allocated (tracker slot), and the protocol handles it with an explicit RetryAck/PCrdGrant. At the issuer, a request can be sendable (link credit) but not trackable (tracker entry/ID) — and there is no protocol retry for this, because it is the issuer's own resource; the issuer must simply not issue until it has one. The unifying principle is that a transaction consumes a chain of resources across its lifetime — send, receive, track, correlate, complete — and it may only start when the resources it needs at its own end are secured. The link credit is necessary but not sufficient: it secures only the first hop. A robust issue gate secures the whole issuer-side chain (tracker entry, unique ID) before committing, because a transaction you cannot finish is worse than one you never start — the unfinishable one consumes bandwidth, hangs, and may corrupt a sibling. Bounding outstanding to the trackable capacity is how the issuer keeps its promises to the transactions it starts.

10. Issuing a Request — credit-only vs full gate

A node with a link credit available but its tracker full.

1. Full gate — check all three. The issue gate checks: link credit (yes), free tracker entry (no — full), free TxnID (n/a). The AND is false — the request does not issue. It waits for a transaction to complete and free an entry.
2. Full gate — a transaction completes. An outstanding transaction finishes, freeing a tracker entry and its TxnID. Now the gate's AND is true — the request issues, allocating the freed entry and a unique ID. Correct.
3. Credit-only gate — issue anyway. The buggy gate checks only the link credit (yes) and issues — despite the tracker being full. No entry is allocated (there is none).
4. Credit-only gate — the response orphans. The issued request returns a response with no tracker entry to receive it → orphaned (dropped). The transaction hangs. (Or, if a TxnID was reused, the response aliases onto another transaction — corruption.)

The full gate waited for a trackable slot; the credit-only gate issued into an overrun. The DebugLab is steps 3–4.

11. RTL / Hardware View — the issue gate

A request issues only when a link credit, a free tracker entry, and a free TxnID are all available. Representative.

// Representative issue gate (educational).
// A request may issue ONLY when all three resources are available: a link credit (send),
// a free tracker entry (track the response), and a free unique TxnID (correlate it).
// On issue, allocate a tracker entry and a unique TxnID. Gating on link_credit ALONE
// overruns the tracker -> orphaned or aliased responses.
module chi_issue_gate #(parameter NTRK = 16, parameter NID = 16) (
  input  logic              clk, rst_n,
  input  logic              want_issue,     // the node wants to issue a request
  input  logic              link_credit,    // receiver buffer has room (send resource)
  input  logic [NTRK-1:0]   trk_free,       // which tracker entries are free
  input  logic [NID-1:0]    id_free,        // which TxnIDs are free
  output logic              can_issue,       // all resources available -> issue
  output logic              do_issue,
  output logic [$clog2(NTRK)-1:0] alloc_trk, // allocated tracker entry
  output logic [$clog2(NID)-1:0]  alloc_id   // allocated unique TxnID
);
  logic tracker_avail, id_avail;
  assign tracker_avail = |trk_free;     // at least one free tracker entry
  assign id_avail      = |id_free;      // at least one free unique TxnID
  // Issue ONLY when send AND track AND correlate resources are ALL available.
  assign can_issue = link_credit && tracker_avail && id_avail;
  assign do_issue  = want_issue && can_issue;
 
  // Allocate the lowest free tracker entry and TxnID on issue (priority-encode).
  always_comb begin
    alloc_trk = '0; alloc_id = '0;
    for (int i = NTRK-1; i >= 0; i--) if (trk_free[i]) alloc_trk = i[$clog2(NTRK)-1:0];
    for (int j = NID-1;  j >= 0; j--) if (id_free[j])  alloc_id  = j[$clog2(NID)-1:0];
  end
endmodule

The same behavior in Verilog-2001:

// Representative issue gate (Verilog-2001).
module chi_issue_gate #(parameter NTRK = 16, parameter NID = 16,
                        parameter TW = 4, parameter IW = 4) (
  input                  clk, rst_n, want_issue, link_credit,
  input  [NTRK-1:0]      trk_free,
  input  [NID-1:0]       id_free,
  output                 can_issue, do_issue,
  output reg [TW-1:0]    alloc_trk,
  output reg [IW-1:0]    alloc_id
);
  integer i, j;
  wire tracker_avail = |trk_free;
  wire id_avail      = |id_free;
  assign can_issue = link_credit & tracker_avail & id_avail;   // all three
  assign do_issue  = want_issue & can_issue;
  always @* begin
    alloc_trk = {TW{1'b0}}; alloc_id = {IW{1'b0}};
    for (i = NTRK-1; i >= 0; i = i - 1) if (trk_free[i]) alloc_trk = i[TW-1:0];
    for (j = NID-1;  j >= 0; j = j - 1) if (id_free[j])  alloc_id  = j[IW-1:0];
  end
endmodule

And in VHDL:

-- Representative issue gate (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_issue_gate is
  generic ( NTRK : integer := 16; NID : integer := 16; TW : integer := 4; IW : integer := 4 );
  port (
    clk, rst_n  : in  std_logic;
    want_issue  : in  std_logic;
    link_credit : in  std_logic;
    trk_free    : in  std_logic_vector(NTRK-1 downto 0);
    id_free     : in  std_logic_vector(NID-1 downto 0);
    can_issue   : out std_logic;
    do_issue    : out std_logic;
    alloc_trk   : out unsigned(TW-1 downto 0);
    alloc_id    : out unsigned(IW-1 downto 0)
  );
end entity;
 
architecture rtl of chi_issue_gate is
  signal tracker_avail, id_avail, ci : std_logic;
begin
  tracker_avail <= '1' when trk_free /= (trk_free'range => '0') else '0';
  id_avail      <= '1' when id_free  /= (id_free'range  => '0') else '0';
  ci            <= link_credit and tracker_avail and id_avail;   -- all three
  can_issue     <= ci;
  do_issue      <= want_issue and ci;
 
  process (trk_free, id_free)
    variable t : unsigned(TW-1 downto 0);
    variable d : unsigned(IW-1 downto 0);
  begin
    t := (others => '0'); d := (others => '0');
    for i in NTRK-1 downto 0 loop
      if trk_free(i) = '1' then t := to_unsigned(i, TW); end if;
    end loop;
    for j in NID-1 downto 0 loop
      if id_free(j) = '1' then d := to_unsigned(j, IW); end if;
    end loop;
    alloc_trk <= t;
    alloc_id  <= d;
  end process;
end architecture;

In all three, can_issue is the AND of link_credit, a free tracker entry, and a free TxnID — so an issue always has somewhere to track and a unique ID to correlate. The DebugLab reduces can_issue to link_credit alone.

12. Verification View — no issue without a trackable slot

The properties bound outstanding: no issue without a tracker entry and a unique ID.

// Bind to chi_issue_gate (and the tracker/ID tables).
// 1. A request never issues without a free tracker entry.
property p_issue_needs_tracker;
  @(posedge clk) disable iff (!rst_n)
    do_issue |-> (|trk_free);
endproperty
 
// 2. A request never issues without a free unique TxnID.
property p_issue_needs_id;
  @(posedge clk) disable iff (!rst_n)
    do_issue |-> (|id_free);
endproperty
 
// 3. Outstanding transactions never exceed the tracker capacity (bounded).
//    outstanding = NTRK - popcount(trk_free); always <= NTRK, and no issue at 0 free.
property p_bounded_outstanding;
  @(posedge clk) disable iff (!rst_n)
    do_issue |-> (link_credit && (|trk_free) && (|id_free));
endproperty

The system point, beyond the checks:

Bounding outstanding requests is a flow-control-completeness property: it guarantees that a node never commits to more transactions than it can see through to completion. This is the final piece of a chain the whole module has built — the request pipeline serializes (16.1), the snoop pipeline responds correctly (16.2), the directory maintains inclusion (16.3), the cache preserves dirty data (16.4), the tracker's lifetime covers the transaction (16.5) — and here the issue gate ensures the tracker is never asked to hold more than it can (16.6). Each chapter secured a resource against reuse-before-retire or overrun; together they make the node's every in-flight transaction fully backed by the resources it needs. The recurring principle across all six is the same: a hardware resource has a finite capacity and a defined lifetime, and correctness is keeping every use within both. The issue gate is where that principle meets admission — the cheapest place to enforce a bound is at the point of entry, by simply not starting what cannot be finished. A system that admits unboundedly and hopes to cope downstream will orphan, alias, overflow, or deadlock; a system that bounds at admission is correct by construction. Closing the RTL module, this is the discipline that ties the individual pipelines into a node that keeps every promise it makes.

• What it proves: no issue without a tracker entry and a unique ID; outstanding is bounded.
• What it does not prove: the tracker/ID capacities are sized for target throughput — that is Chapter 14.6.
• Bug signature: do_issue asserted while trk_free or id_free is zero — a tracker/ID overrun.

13. Testbench — a full tracker must block issue despite a credit

Offers a request with a link credit available but the tracker full, and checks issue is blocked.

module tb_chi_issue_gate;
  localparam NTRK = 4, NID = 4, TW = 2, IW = 2;
  logic clk = 0, rst_n = 1, want_issue, link_credit;
  logic [NTRK-1:0] trk_free;
  logic [NID-1:0] id_free;
  logic can_issue, do_issue;
  logic [TW-1:0] alloc_trk;
  logic [IW-1:0] alloc_id;
  int errors = 0;
 
  chi_issue_gate #(.NTRK(NTRK), .NID(NID), .TW(TW), .IW(IW)) dut (.*);
  always #5 clk = ~clk;
 
  initial begin
    // Link credit available, tracker has a free entry and a free ID -> issue OK.
    want_issue = 1; link_credit = 1; trk_free = 4'b0010; id_free = 4'b0100; #1;
    if (!do_issue) begin errors++; $display("FAIL should issue with all resources"); end
    else $display("PASS issue: trk=%0d id=%0d", alloc_trk, alloc_id);
 
    // Link credit available but TRACKER FULL -> must NOT issue (credit-only bug would).
    trk_free = 4'b0000; id_free = 4'b0100; #1;
    if (do_issue) begin errors++; $display("FAIL issued with tracker full -> response would orphan!"); end
    else $display("PASS blocked: tracker full despite link credit");
 
    // Link credit available, tracker free, but NO free TxnID -> must NOT issue.
    trk_free = 4'b0010; id_free = 4'b0000; #1;
    if (do_issue) begin errors++; $display("FAIL issued with no free TxnID -> response would alias!"); end
    else $display("PASS blocked: no free TxnID despite credit + tracker");
 
    // No link credit -> must NOT issue even with tracker + ID free.
    link_credit = 0; trk_free = 4'b0010; id_free = 4'b0100; #1;
    if (do_issue) begin errors++; $display("FAIL issued with no link credit"); end
    else $display("PASS blocked: no link credit");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS issue: trk=1 id=2
PASS blocked: tracker full despite link credit
PASS blocked: no free TxnID despite credit + tracker
PASS blocked: no link credit
ALL TESTS PASSED

14. DebugLab — an issue gate that checks only the link credit

tracker capacity = 16 entries; TxnID space = 16
issue gate: can_issue = link_credit   (ONLY the credit checked)
under load: link credits available, tracker FULL (16 outstanding)
  -> gate issues a 17th request -> no tracker entry allocated (none free)
  -> response returns -> no entry to match -> ORPHAN -> transaction hangs
  -> TxnID space exhausted -> 17th reuses an in-flight ID
  -> its response matches TWO transactions -> ALIAS -> wrong transaction corrupted
correct: can_issue = link_credit && (free tracker entry) && (free unique TxnID)

15. Common Mistakes

• Gating on link credit alone. Assumption: sendable means issuable. Bug: tracker overrun (the DebugLab). Prevention: check all three resources.
• Forgetting the TxnID resource. Assumption: IDs are infinite. Bug: reused ID aliases. Prevention: check for a free unique ID.
• Not allocating on issue. Assumption: allocate later. Bug: a race with the response. Prevention: allocate tracker + ID at issue.
• Assuming credits and trackers track together. Assumption: one implies the other. Bug: credit available, tracker full. Prevention: independent checks.
• Unbounded issue. Assumption: downstream copes. Bug: orphans/aliases. Prevention: bound at admission.
• Confusing with window sizing. Assumption: 14.6 covers it. Bug: throughput vs correctness. Prevention: 14.6 sizes; 16.6 gates.

16. Engineering Checklist

• Gate issue on a link credit (send resource).
• And a free tracker entry (track resource).
• And a free unique TxnID (correlate resource).
• Allocate the tracker entry and TxnID on issue.
• Bound the outstanding count to the tracker/ID capacity.
• Confirm no issue occurs when the tracker or ID space is full.

17. Key Takeaways

• Outstanding requests are bounded by the tracker and TxnID capacity.
• Sending (link credit) and tracking (tracker entry, TxnID) are different resources.
• The issue gate must check all three — not just the credit.
• A credit-only gate overruns the tracker.
• A returning response then orphans (hang) or aliases (corruption).
• Bound at admission — don't start what you can't finish; the model here is representative.

18. Quick Revision

Outstanding requests. A node's tracker is finite, so its number of in-flight (outstanding) requests must be bounded — and the issue gate enforces the bound. Issuing a request is not merely sending a flit; it starts a transaction whose response must return, be tracked, and be correlated. Three different resources are needed: a link credit (the receiver's buffer has room — Chapter 14.1), a free tracker entry (state to hold the transaction — Chapter 16.5), and a free unique TxnID (so the response maps back — Chapter 13.4). The issue gate must permit a request only when all three are available, allocating the tracker entry and ID on issue. The failure to avoid: gating on the link credit alone. Credits and tracker entries free on different schedules, so a credit can be available while the tracker is full — a credit-only gate then issues a request it cannot track. The response returns to no entry (an orphan — dropped, so the transaction hangs) or, if a TxnID was reused, is aliased onto another in-flight transaction — corrupting both. Bound the outstanding count to the tracker/ID capacity at admission: do not start what you cannot finish. This is the issuer-side mirror of Chapter 14.5's completer-side retry — the resource that lets you start is not the one that lets you finish. Representative model; this closes Module 16.

Coming Next

Chapter 17.1 — Protocol Verification. Module 16 built CHI's RTL; Module 17 verifies it, and verifying CHI is harder than any other AMBA bus. Chapter 17.1 opens CHI Verification with protocol verification — the per-channel protocol-rule checks that confirm every flit is legal on its channel, the assertions that encode those rules, and how they form the first layer of a CHI verification environment before coherence invariants are even considered.