Throughput Optimisation

Module 14 · Chapter 14.6 · CHI Flow Control

Project thread — 14.5 handled resource retry. 14.6 closes the module on throughput; Module 15 opens CHI Performance.

1. Learning Outcomes

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

• Explain why one outstanding request pins throughput at one over latency.
• State that pipelining — many outstanding requests — fills the latency window.
• Apply Little's Law — outstanding = throughput × latency.
• Compute the outstanding count needed to saturate a link (its bandwidth-delay product).
• Diagnose the latency-bound design from a one-at-a-time (blocking) requester.
• Implement a representative outstanding-transaction model in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Flow control (Chapters 14.1–14.5) makes the fabric correct — no overflow, no deadlock, no loss. But correct is not fast. A requester can obey every flow-control rule and still use a fraction of the link's bandwidth, if it issues one request at a time and waits for each to complete. The link is capable; the requester is starving it. Throughput is where the fabric's capability meets the requester's issue discipline.

The physics is unavoidable: a transaction takes a round-trip latency to complete, and during that time a blocking requester does nothing. Its throughput is therefore one transaction per latency — a number set by latency alone, wholly independent of how much bandwidth the link has. To use the bandwidth you must overlap transactions: keep many outstanding so completions arrive continuously. Little's Law tells you exactly how many — throughput equals outstanding over latency — so saturating a link means provisioning enough outstanding requests to cover its bandwidth-delay product. This chapter closes the module by turning correct flow control into full flow control.

3. Key Terms

4. Previous Chapter Connection

The whole module built the machinery that makes outstanding requests possible: per-transaction identifiers (TxnID, Chapter 6.6) let many requests be in flight and matched to their completions, and credits (Chapters 14.1–14.2) let a requester issue ahead without overrunning the receiver. This chapter is what to do with that machinery — issue enough at once to keep the link busy.

It also inverts the module's earlier concern. Chapters 14.4–14.5 were about too much offered load — backpressure and retry throttle a requester that outruns the fabric. This chapter is about too little — a requester that under-drives a fabric with capacity to spare. The sweet spot is between: enough outstanding to saturate the link, not so many as to congest it. This closing chapter finds that spot with the throughput math, completing Module 14 and setting up Module 15's deeper performance analysis.

5. Core Concept — overlap transactions to fill the pipe

Throughput is set by how many transactions are outstanding: one at a time pins it at one over latency; pipelining many fills the latency window up to the link's bandwidth.

• A transaction costs a round-trip. From issue to completion is one latency. A requester that blocks on each completion does one transaction per latency — the link is idle the rest of the time.
• Pipelining overlaps them. Issue the next request before the previous completes. With many outstanding, completions stream back continuously and the link stays busy.
• Little's Law sets the count. Outstanding = throughput × latency. To hit a target throughput, keep that many transactions in flight; to saturate a link, that is its bandwidth-delay product.
• Under-provisioning caps throughput. With only N outstanding, throughput is at most N / latency — below the link's bandwidth if N is too small, no matter how fast the link.

The synthesis:

Throughput is governed by outstanding transactions, not link speed alone. One-at-a-time issue pins throughput at 1 / latency — the link idles through every round-trip. Pipelining keeps many requests outstanding so the latency window stays full. Little's Law — outstanding = throughput × latency — sizes the window: to saturate a link, keep its bandwidth-delay product of transactions in flight. Too few, and throughput caps at N / latency.

6. Engineering Mental Model — a conveyor to a distant station

Think of sending parcels along a long conveyor to a station and getting a receipt back.

• The conveyor is long — a parcel takes a while to reach the station and its receipt to return (the latency). But the conveyor is also wide — it can carry many parcels side by side at once (the bandwidth).
• If you send one parcel and wait by the belt for its receipt before sending the next, the whole wide conveyor carries a single parcel at a time. Its width is wasted; your rate is one parcel per round-trip.
• If instead you keep loading parcels continuously — many riding the belt at once — receipts start streaming back and you are completing parcels as fast as the belt is wide, not as slow as it is long.
• How many parcels must be on the belt to keep it full? Exactly enough to cover its length at full width — the belt's length times its width. That is the bandwidth-delay product.

Waiting by the belt is the one-at-a-time bug. Keeping the belt full is pipelining. The belt's length (latency) sets how many parcels you must have in flight to exploit its width (bandwidth).

7. Engineering Diagram — serial vs pipelined issue

The top row is latency-bound: one in flight, the link idle between completions. The bottom row is bandwidth-bound: N in flight, the link full. The only difference is how many transactions are outstanding — and Little's Law says how many are needed.

8. The Throughput Math

Little's Law and its consequence, in numbers.

The rule to carry: to go faster, raise N — the outstanding count — until throughput reaches the link bandwidth. Throughput is N / latency, so with N = 1 you get the latency-bound floor, and each additional outstanding transaction adds 1 / latency of throughput until the link saturates. The saturating N is the bandwidth-delay product divided by request size — provision at least that many transaction IDs and buffer entries, and the link runs full; provision fewer and throughput is stuck at N / latency.

9. Sizing the Outstanding Window

Choosing N to saturate the link.

• Measure the latency. The round-trip from issue to completion — through the interconnect, home, and (if needed) memory. Call it L.
• Know the target bandwidth. The link's bytes-per-cycle B you want to sustain.
• Compute the bandwidth-delay product. B × L bytes must be in flight to keep the link full; dividing by request size gives N — the number of outstanding transactions.
• Provision at least N. Size the transaction-ID space and outstanding-tracking buffers to at least N. Fewer caps throughput at N / L; more gives headroom for latency spikes but risks congestion (Chapters 14.4–14.5).

The point to carry:

The bandwidth-delay product is the bridge between the two numbers a link is described by — its bandwidth and its latency — and it explains why fast links can feel slow. Latency and bandwidth are independent: a link can be wide (high bandwidth) yet long (high latency), and the two do not trade off. A one-at-a-time requester experiences only the latency — it never sees the bandwidth at all, because it never has more than one transaction exploiting the width. Pipelining is precisely the act of converting latency tolerance into bandwidth utilization: each outstanding transaction hides one transaction's worth of latency behind another's progress. The number you need is set by how much latency there is to hide relative to how fast you want to go — the product B × L. This is why the same link needs more outstanding transactions as it gets longer: a distant home across a large mesh has a bigger delay to fill, so a requester that saturated a nearby home will under-drive a far one with the identical issue rate.

10. Two Requesters — same link, different throughput

The same link and latency, driven two ways.

1. Link: 32 B/cycle bandwidth, latency 20 cycles. The bandwidth-delay product is 32 × 20 = 640 bytes in flight to saturate. With 64-byte lines, that is 10 outstanding transactions.
2. Serial requester: N = 1. It issues a request, waits 20 cycles, gets 64 bytes, repeats. Throughput = 64 / 20 ≈ 3.2 B/cycle — one-tenth of the link.
3. Pipelined requester: N = 10. It keeps 10 requests outstanding; a completion returns roughly every 2 cycles. Throughput ≈ 64 / 2 = 32 B/cycle — the link is saturated.
4. Same link, 10× the throughput. Nothing changed about the fabric — only the issue discipline. The serial requester was latency-bound; the pipelined one is bandwidth-bound.

The pipelined requester extracted the link's full bandwidth because it kept the bandwidth-delay product outstanding. The DebugLab is the serial requester at step 2 — correct, but using a tenth of the fabric.

11. RTL / Hardware View — an outstanding-request window

The requester issues while outstanding is below the window size, tracking issues and completions. Representative.

// Representative outstanding-request window (educational).
// Throughput = outstanding / latency, so a bigger window (up to the bandwidth-delay
// product) yields more throughput. A window of 1 pins throughput at 1/latency and
// starves a fast link. Issue while outstanding < MAX_OUT; ++ on issue, -- on complete.
module chi_outstanding #(parameter MAX_OUT = 16) (
  input  logic                       clk, rst_n,
  input  logic                       want_issue,   // requester has a request ready
  input  logic                       complete,      // a transaction completed
  output logic                       can_issue,      // window has room
  output logic                       do_issue,       // a request is issued this cycle
  output logic [$clog2(MAX_OUT+1)-1:0] outstanding
);
  logic [$clog2(MAX_OUT+1)-1:0] out_q;
  assign outstanding = out_q;
  assign can_issue   = (out_q < MAX_OUT);           // pipeline up to MAX_OUT in flight
  assign do_issue    = want_issue && can_issue;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) out_q <= '0;
    else begin
      case ({do_issue, complete})
        2'b10:   out_q <= out_q + 1'b1;   // issued
        2'b01:   out_q <= out_q - 1'b1;   // completed
        default: out_q <= out_q;          // both or neither
      endcase
    end
  end
endmodule

The same behavior in Verilog-2001:

// Representative outstanding-request window (Verilog-2001).
module chi_outstanding #(parameter MAX_OUT = 16, parameter CW = 5) (
  input  wire          clk, rst_n, want_issue, complete,
  output wire          can_issue, do_issue,
  output wire [CW-1:0] outstanding
);
  reg [CW-1:0] out_q;
  assign outstanding = out_q;
  assign can_issue   = (out_q < MAX_OUT[CW-1:0]);
  assign do_issue    = want_issue & can_issue;
 
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) out_q <= {CW{1'b0}};
    else begin
      if (do_issue & ~complete)      out_q <= out_q + 1'b1;
      else if (~do_issue & complete) out_q <= out_q - 1'b1;
    end
  end
endmodule

And in VHDL:

-- Representative outstanding-request window (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_outstanding is
  generic ( MAX_OUT : integer := 16; CW : integer := 5 );
  port (
    clk, rst_n        : in  std_logic;
    want_issue        : in  std_logic;
    complete          : in  std_logic;
    can_issue         : out std_logic;
    do_issue          : out std_logic;
    outstanding       : out unsigned(CW-1 downto 0)
  );
end entity;
 
architecture rtl of chi_outstanding is
  signal out_q : unsigned(CW-1 downto 0) := (others => '0');
  signal room  : std_logic;
  signal iss   : std_logic;
begin
  room        <= '1' when out_q < MAX_OUT else '0';   -- window has room
  iss         <= want_issue and room;
  can_issue   <= room;
  do_issue    <= iss;
  outstanding <= out_q;
 
  process (clk, rst_n)
  begin
    if rst_n = '0' then
      out_q <= (others => '0');
    elsif rising_edge(clk) then
      if iss = '1' and complete = '0' then out_q <= out_q + 1;
      elsif iss = '0' and complete = '1' then out_q <= out_q - 1;
      end if;
    end if;
  end process;
end architecture;

All three allow up to MAX_OUT transactions in flight — set MAX_OUT to at least the bandwidth-delay product and the link saturates. The DebugLab is effectively MAX_OUT = 1: one outstanding, latency-bound.

12. Verification View — the window bounds outstanding

The properties tie the window to throughput: outstanding never exceeds the size, and issue is allowed with room.

// Bind to chi_outstanding.
// 1. Outstanding never exceeds the window size.
property p_outstanding_bounded;
  @(posedge clk) disable iff (!rst_n)
    outstanding <= MAX_OUT;
endproperty
 
// 2. A request issues whenever the requester wants to and the window has room.
property p_issue_when_room;
  @(posedge clk) disable iff (!rst_n)
    (want_issue && outstanding < MAX_OUT) |-> do_issue;
endproperty
 
// 3. With a window of 1, at most one transaction is ever outstanding (latency-bound).
//    (Instantiate MAX_OUT=1 and check outstanding <= 1 -- the DebugLab configuration.)

The system point, beyond the checks:

Throughput is the one property in this module that is not enforced by a rule you can assert — it is an emergent consequence of a parameter, MAX_OUT, and the surrounding latency. You cannot write an assertion that "throughput is high"; you can only verify that the window permits enough outstanding transactions and then reason, via Little's Law, that the resulting throughput meets the target given the measured latency. This makes throughput a design-time sizing problem rather than a runtime-checkable invariant: the verification artifact is a calculation (bandwidth-delay product) plus a check that the implementation's window and ID space are at least that large. It is worth stressing because it is a different kind of correctness than the rest of Module 14 — flow control is about never entering a bad state, throughput is about being provisioned to reach a good rate. A design can be perfectly flow-control-correct and still be a tenth as fast as it should be, and no safety property will ever flag it. Only the throughput math will.

• What it proves: outstanding stays within the window; issue proceeds when there is room.
• What it does not prove: the window is sized to the bandwidth-delay product — a design calculation.
• Bug signature: an effective window of one — throughput pinned at 1 / latency.

13. Testbench — a wider window must raise throughput

Runs the window with a fixed latency and checks a larger window completes more.

module tb_chi_outstanding;
  localparam MAX_OUT = 8, CW = 5, LAT = 4;   // completion latency = 4 cycles
  logic clk = 0, rst_n = 0, want_issue = 1, complete = 0;
  logic can_issue, do_issue;
  logic [CW-1:0] outstanding;
  int completions = 0;
  int issue_time[$];
 
  chi_outstanding #(.MAX_OUT(MAX_OUT)) dut (.*);
  always #5 clk = ~clk;
 
  // Model latency: a request issued now completes LAT cycles later.
  int cyc = 0;
  always @(posedge clk) if (rst_n) begin
    cyc++;
    complete <= 0;
    if (do_issue) issue_time.push_back(cyc);
    if (issue_time.size() > 0 && issue_time[0] + LAT == cyc) begin
      complete <= 1; void'(issue_time.pop_front()); completions++;
    end
  end
 
  initial begin
    @(posedge clk) rst_n = 1;
    // With MAX_OUT=8 and latency 4, the window is never the bottleneck:
    // throughput approaches 1 completion/cycle rather than 1/LAT.
    repeat (40) @(posedge clk);
    // A serial (window=1) design would complete ~ 40/LAT = 10; pipelined completes far more.
    if (completions <= 40/LAT) $display("FAIL latency-bound: only %0d completions", completions);
    else $display("PASS pipelined: %0d completions (>> serial bound %0d)", completions, 40/LAT);
    if (outstanding > MAX_OUT) $display("FAIL window exceeded");
    else $display("PASS outstanding within window (peak <= %0d)", MAX_OUT);
    $display("ALL TESTS PASSED");
    $finish;
  end
endmodule

Expected output:

PASS pipelined: 36 completions (>> serial bound 10)
PASS outstanding within window (peak <= 8)
ALL TESTS PASSED

14. DebugLab — a one-at-a-time requester

link: 32 B/cycle, latency 20 cycles -> bandwidth-delay product = 640 B (10 x 64B lines)
serial requester: issue -> wait 20 cycles for completion -> issue next
  -> outstanding is always <= 1
  -> throughput = 64 B / 20 cycles = 3.2 B/cycle  (10% of the 32 B/cycle link)
  -> link idle 90% of the time
correct: keep 10 outstanding -> completion every ~2 cycles -> 32 B/cycle (saturated)

15. Common Mistakes

• One-at-a-time issue. Assumption: simplicity. Bug: latency-bound, link idle (the DebugLab). Prevention: pipeline outstanding requests.
• Under-sizing the window. Assumption: a few outstanding suffice. Bug: throughput caps at N / latency. Prevention: size to the bandwidth-delay product.
• Ignoring latency growth. Assumption: one window fits all. Bug: a distant home under-driven. Prevention: size to the worst-case latency.
• Too few transaction IDs. Assumption: small ID space is fine. Bug: cannot keep enough outstanding. Prevention: provision IDs to N.
• Over-provisioning wildly. Assumption: more is always better. Bug: congestion (Chapters 14.4–14.5). Prevention: target the bandwidth-delay product plus modest headroom.
• Assuming correctness means speed. Assumption: no bugs = fast. Bug: a correct but slow design. Prevention: check the throughput math separately.

16. Engineering Checklist

• Pipeline — keep many transactions outstanding, do not block on each completion.
• Measure the round-trip latency and target bandwidth.
• Size the outstanding window to at least the bandwidth-delay product.
• Provision the transaction-ID space and tracking buffers to that many.
• Size to the worst-case (most distant) latency to saturate every path.
• Verify throughput by the math, not by a safety assertion.

17. Key Takeaways

• One outstanding request pins throughput at one over latency — latency-bound.
• Pipelining many outstanding requests fills the latency window.
• Little's Law: outstanding = throughput × latency.
• Saturating a link needs its bandwidth-delay product of transactions in flight.
• Too few outstanding caps throughput at N / latency, a fraction of the link.
• Throughput is a sizing problem, not a safety one; the model here is representative.

18. Quick Revision

Throughput optimisation. Flow control (Chapters 14.1–14.5) makes the fabric correct; throughput makes it fast, and the two are independent. Every transaction takes a round-trip latency to complete, so a requester that issues one request and blocks until it completes achieves throughput of 1 / latency — a number set by latency alone, leaving a bandwidth-rich link idle through every round-trip. The cure is pipelining: keep many requests outstanding so completions stream back while new requests go out, filling the latency window. Little's Law sizes it exactly — outstanding = throughput × latency — so to saturate a link you must keep its bandwidth-delay product (bandwidth × latency ÷ request size) of transactions in flight; provision fewer and throughput caps at N / latency. The failure to avoid: the one-at-a-time, blocking requester — perfectly flow-control-correct but pinned at 1 / latency, running the fabric at a fraction of its bandwidth, and worsening as the home grows more distant. Latency and bandwidth do not trade off; pipelining converts latency tolerance into bandwidth utilization. Size the outstanding window (and the transaction-ID space) to the bandwidth-delay product. Throughput is a sizing calculation, not a safety property. Representative model; this closes Module 14.

Coming Next

Chapter 15.1 — CHI Latency Anatomy. Module 14 closed on throughput; Module 15 opens on where the time actually goes. Chapter 15.1 covers CHI latency anatomy — a hop-by-hop decomposition of a transaction's round-trip, from request issue through interconnect traversal, home lookup, snoop or memory access, and data return, so each contributor to the latency you just learned to hide can be seen and attacked.