Two identical requesters read from two identical memories. One of them waits for each answer before asking for the next word. The other asks for up to four words before the first answer comes back. Over the same 20 cycles, the first gets 5 words and the second gets 20. Nothing about the memories differs.

Why does one request at a time waste the link, and how many should be outstanding?

The obvious answer, and why it breaks

The obvious requester is sequential: ask, wait, use the answer, ask again. It is simple, and it is what a program naturally does when each step needs the previous result. But while it waits, the request path and the target sit idle. The link could carry another request every cycle; the requester sends one per round trip.

The idea: keep several requests outstanding

An outstanding request is one that has been sent and not yet answered. If the requester may have N outstanding and each takes L cycles, Little's law (lesson 6.2) says it completes at most N / L per cycle. With N = 1 that is 1/L; with N ≥ L the link is full. Allowing more outstanding transactions is how a split-transaction protocol turns latency into throughput.

Build it: one versus four outstanding

Both requesters read from memories that answer 4 cycles after a request. Requester 1 allows one outstanding read, requester 4 allows four. Each sends a new request in any cycle where it is below its limit, counting a response that arrives that cycle as freeing a slot.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// Two requesters read from identical memories with a 4-cycle latency: a request
// issued in cycle t is answered in cycle t + 4. Requester 1 allows one request
// outstanding; requester 4 allows four. Each issues a new request in any cycle
// where it is below its limit (a response arriving that cycle frees a slot).
module tb;
  logic clk = 0;
  always #5 clk = ~clk;
  initial begin $dumpfile("wave.vcd"); $dumpvars(0, tb); end
  localparam int LAT = 4;

  // Each memory: a shift register; a request entering it comes out LAT cycles later
  logic [LAT-1:0] pipe1 = 0, pipe4 = 0;
  wire rsp1 = pipe1[LAT-1];
  wire rsp4 = pipe4[LAT-1];
  logic [2:0] out1 = 0, out4 = 0;               // requests outstanding
  int cyc = 0;                                  // requests start in cycle 1
  wire req1 = (cyc >= 1) && (out1 - rsp1) < 1;
  wire req4 = (cyc >= 1) && (out4 - rsp4) < 4;
  always @(posedge clk) begin
    pipe1 <= {pipe1[LAT-2:0], req1};
    pipe4 <= {pipe4[LAT-2:0], req4};
    out1  <= out1 + req1 - rsp1;
    out4  <= out4 + req4 - rsp4;
  end

  int n1 = 0, n4 = 0;
  always @(posedge clk) begin
    cyc <= cyc + 1;
    if (cyc >= 8 && cyc < 28) begin n1 += rsp1; n4 += rsp4; end   // 20 cycles in steady state
  end
  initial begin
    #300;
    if (n1 == 5 && n4 == 20) $display("PASS: in 20 cycles, 1 outstanding completes %0d reads, 4 outstanding completes %0d", n1, n4);
    else $display("FAIL: %0d and %0d", n1, n4);
    $finish;
  end
endmodule

Each memory is a 4-stage shift register: a request entering it comes out as a response four cycles later.

Watch it run

How to read it, slot by slot:

• Requester 1, slot 0: it sends a read (req1); from slot 1 it has one outstanding (out1 1) and may not send another until the answer comes.

• Requester 1, slot 4: the response arrives (rsp1), and in the same cycle the next read goes out. The pattern repeats every 4 slots: one read per 4 cycles.

• Requester 4, slots 0 to 3: it sends a read every cycle, and out4 climbs to 4 by slot 4.

• Requester 4, from slot 4: the first response arrives and a new read leaves in the same cycle, so out4 stays at 4 and a response arrives every cycle: four times the throughput from the same memory.

What limits outstanding transactions

• Tags or IDs to match responses with requests (lesson 6.4): the tag pool caps how many can be outstanding.

• Buffer space for responses: the requester must be able to accept every response it has asked for.

• Dependencies in the program: a pointer chase, where each address comes from the previous answer, cannot have two outstanding however much hardware allows. Only reorganising the work helps.

• Ordering rules: if responses must return in order, the requester or a reorder buffer must hold early arrivals (lesson 6.6).

How real protocols chose

What breaks

A DMA engine (illustrative) was designed and tested against an on-chip memory with 3 cycles of latency, with 4 outstanding reads, which was plenty. In the product it read from external memory through a fabric with about 200 cycles of latency, and still allowed 4. It reached 2% of the link. The fix was raising its outstanding limit (and its tag count and response buffer) to cover the real latency.

Key takeaways

• One request at a time gives 1 / latency of the link; N outstanding give up to N / latency.

• Filling a link needs at least latency × rate requests outstanding.

• Tags, response buffers, target queues and program dependencies all cap outstanding requests.

Related topics

• Part 6 overview: Concurrency and Performance