Pipelining, outstanding transactions, latency and throughput
Tell latency from throughput with numbers, see why one transaction in flight wastes the bus, and know how many must be outstanding before the clock, and only the clock, sets the rate.
- Lesson
- P1.5
- Time
- 30 min
- Runs on
- Your browser
- Check
- 5 questions
A memory controller answered every read 40 ns after taking it. The team doubled the bus clock from 100 MHz to 200 MHz and measured the copy loop again: 10 % faster. The initiator issued one read, waited for its data, then issued the next, so each read cost the 40 ns of the memory plus one cycle of turnaround. At 200 MHz that is 45 ns per read instead of 50 ns, and no clock on earth would make it much better.
| Clock | Memory latency | Reads in flight | Time per read | Reads per µs |
|---|---|---|---|---|
| 100 MHz | 4 cycles (40 ns) | 1 | 5 cycles = 50 ns | 20 |
| 200 MHz | 8 cycles (40 ns) | 1 | 9 cycles = 45 ns | 22 |
| 200 MHz | 8 cycles (40 ns) | 9 or more | 1 cycle = 5 ns | 200 |
The clock doubled and the rate barely moved. The number of reads in flight is what moved it.
Latency and throughput are two numbers
Latency is how long one transaction takes: the cycles from the edge where the target takes the request to the edge where the initiator takes the response. Throughput is how many transactions complete per unit of time. On the link in this lesson the target answers 3 cycles after taking a request, so the latency is 3.
The two numbers are related only through the number of transactions in flight. With one in flight, every request waits for the previous response, and the throughput is one transaction per latency plus the turnaround: here one every 4 cycles. With enough in flight, the throughput becomes one per cycle whatever the latency.
Bandwidth turns that rate into bytes. A link that moves one beat per cycle carries beats × width × clock: a 64-bit link at 200 MHz moves 1.6 GB/s at best. The achieved bandwidth is that peak times the fraction of cycles that carry a beat. An initiator with one read in flight on a 4-cycle target reaches a fifth of it.
One in flight
A request token flies out, a response token flies back; the lit slot is the request in flight.
- Cycle 1
Request 0 is taken. The target now holds one request in flight.
- Cycle 2
The initiator waits. With a window of one, nothing else may start.
- Cycle 4
Response 0 arrives, three cycles after the request. Only now can request 1 start.
- Cycle 5
Request 1 is taken, four cycles after request 0.
- Cycle 12
Response 2 at cycle 12. Three transactions in twelve cycles: one response every four cycles.
Three of every four cycles carry nothing. The link is idle while the initiator waits for a response it has already asked for.
Every idle cycle here is a cycle where the target could have been working on another request. The target is pipelined inside: it has three stages and each could hold a different request. With one in flight, two of them are always empty.
Pipelining: start the next before the last is done
A pipelined link lets the initiator issue a new request while earlier ones are still being answered. The request of transaction N+1 overlaps the response of transaction N. Nothing about the target changes; only the initiator stops waiting.
Requests leave every cycle; the lit slots are the requests in flight; responses return in the same order.
- Cycle 1
Request 0 is taken, exactly as before.
- Cycle 2
Request 1 is taken one cycle later. The initiator did not wait for response 0.
- Cycle 3
Three requests in flight. The target answers each one three cycles after taking it.
- Cycle 4
Response 0 at cycle 4: the same latency as the serial run.
- Cycle 6
Response 2 at cycle 6. Three transactions in six cycles instead of twelve. The throughput doubled; the latency did not move.
Pipelining never shortens a transaction. It fills the cycles between them.
Most buses are built for this. AHB overlaps the address phase of one transfer with the data phase of the previous one. AXI puts requests and responses on separate channels, so an initiator may have many of each in flight. Wishbone adds a pipelined mode, Avalon-MM a pipelined read with a data-valid signal, and TileLink allows several requests in flight per link.
Outstanding transactions and the tag
A transaction is outstanding from the edge where its request is taken until the edge where its response is taken. The initiator decides how many may be outstanding at once: its window. The bench prints, for each window, how many cycles eight requests took.
| Window | Cycles for 8 requests | Rate | What sets the limit |
|---|---|---|---|
| 1 | 32 | one per 4.0 cycles | latency plus turnaround |
| 2 | 17 | one per 2.1 cycles | latency plus turnaround, shared by two |
| 4 | 11 | one per 1.3 cycles | the target: one request per cycle |
| 8 | 11 | one per 1.3 cycles | the target: one request per cycle |
Measured on the bench with a latency of 3. Past a window of four the limit has moved from the latency to the clock, and a bigger window buys nothing.
The rule of thumb falls out of the table: to keep a link busy, the window must cover the latency plus the turnaround. With latency 3 that is 4 requests in flight; with the 8-cycle memory of the opening story it is 9.
Once two requests are in flight, a response must say which request it answers. That is the tag (AXI calls it an ID). When a target answers in order, the tag is implied by the count, and many simple buses rely on that. When a target may answer out of order, the tag is the only thing that keeps a scoreboard honest, which is the subject of P1.7.
The window also costs something at the initiator: a table of outstanding requests, one entry per tag, so that the response can be matched to the request that caused it. A CPU with 16 outstanding reads keeps 16 entries of address and destination register.
Where you will meet it
Latency and throughput are the two numbers every performance review asks for, and the window is the knob that connects them. A DMA engine, a cache, a NoC router and a PCIe endpoint all have a maximum number of outstanding requests, and that number alone often explains a disappointing bandwidth.
Asked in interviews: pipelining and outstanding transactions
What is the difference between latency and throughput?
Latency is the time one transaction takes from request to response. Throughput is how many transactions complete per unit time; with several in flight it can be high while the latency stays the same.
What is a pipelined bus?
One where the initiator issues the next request before the previous response has returned, so request N+1 overlaps response N. The latency of each transaction is unchanged; the idle cycles between them disappear.
What does "outstanding" mean?
A transaction whose request has been taken but whose response has not yet returned. The number of outstanding transactions an initiator allows is its window.
How many transactions must be in flight to saturate a link?
Enough to cover the latency plus the turnaround: a target with latency L that takes one request per cycle needs about L+1 in flight. Beyond that the clock sets the rate.
Why does a response carry an ID?
With more than one request in flight, the response must name the request it answers. In-order targets can imply it by counting; out-of-order ones cannot.
Try it
The initiator runs eight requests with one in flight, then eight with four. Run it and compare the two lines: the latency is 3 in both, the cycles are not.
Then set window = 2 and window = 8, and change the target's latency to 6 to see how large the window must grow before the clock sets the rate again.
window 1: 8 requests in 32 cycles, latency 3 each, one response every 4.0 cycles window 4: 8 requests in 11 cycles, latency 3 each, one response every 1.3 cyclesRead included file: pipe_target.sv
// pipe_target.sv: a target that answers every request LATENCY cycles after taking it (read-only).
// Requests arrive on req_valid/req_ready with an id. The response to a request taken at edge k is
// offered on rsp_valid/rsp_id so that an initiator holding rsp_ready high takes it at edge
// k + LATENCY. The target keeps up to CAPACITY requests in flight and lowers req_ready while full.
module pipe_target #(parameter int LATENCY = 3, parameter int CAPACITY = 8) (
input logic clk,
input logic rst_n,
input logic req_valid,
input logic [7:0] req_id,
output logic req_ready,
output logic rsp_valid,
output logic [7:0] rsp_id,
input logic rsp_ready,
output int in_flight
);
localparam int STAGES = LATENCY - 1; // the response FIFO is the last stage
localparam int LAST = (STAGES > 0) ? STAGES - 1 : 0;
logic sv [LATENCY];
logic [7:0] sid [LATENCY];
logic [7:0] fifo [CAPACITY];
int wr = 0, rd = 0, held = 0;
wire accept = req_valid && req_ready;
wire done = rsp_valid && rsp_ready;
wire arrive = (STAGES == 0) ? accept : sv[LAST];
wire [7:0] arrive_id = (STAGES == 0) ? req_id : sid[LAST];
assign req_ready = (in_flight < CAPACITY);
assign rsp_valid = (held > 0);
assign rsp_id = fifo[rd];
always_ff @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
in_flight <= 0; wr <= 0; rd <= 0; held <= 0;
for (int i = 0; i < LATENCY; i++) sv[i] <= 0;
end else begin
if (STAGES > 0) begin
sv[0] <= accept; sid[0] <= req_id;
for (int i = 1; i < STAGES; i++) begin sv[i] <= sv[i-1]; sid[i] <= sid[i-1]; end
end
if (arrive) begin fifo[wr] <= arrive_id; wr <= (wr + 1) % CAPACITY; end
if (done) rd <= (rd + 1) % CAPACITY;
held <= held + (arrive ? 1 : 0) - (done ? 1 : 0);
in_flight <= in_flight + (accept ? 1 : 0) - (done ? 1 : 0);
end
end
endmodule
Read included file: pipe_tasks.svh
// pipe_tasks.svh: the initiator side of the request/response link, as tasks (read-only).
// `window` is the most requests the initiator keeps in flight. run_requests(n) issues n requests
// numbered from 0, waits for every response and prints one summary line: the cycles from the
// first request to the last response, the latency of each request, and the resulting rate.
int cycle = -1;
int window = 1;
int issued = 0, completed = 0, max_in_flight = 0;
int first_edge = -1, last_edge = -1, sum_latency = 0;
int taken_at [256];
always @(posedge clk) begin
cycle = cycle + 1;
if (rst_n && rsp_valid && rsp_ready) begin
completed = completed + 1;
sum_latency = sum_latency + (cycle - taken_at[rsp_id]);
last_edge = cycle;
end
if (in_flight > max_in_flight) max_in_flight = in_flight;
end
task automatic run_requests(input int n);
int total;
issued = 0; completed = 0; max_in_flight = 0; sum_latency = 0; first_edge = -1;
for (int i = 0; i < n; i++) begin
while (issued - completed >= window) begin @(posedge clk); #1; end
req_valid = 1; req_id = i[7:0];
do @(posedge clk); while (!req_ready); // taken at this edge
#1 taken_at[i] = cycle; issued = issued + 1; req_valid = 0;
if (first_edge < 0) first_edge = cycle;
end
while (completed < n) begin @(posedge clk); #1; end
total = last_edge - first_edge + 1;
$display("window %0d: %0d requests in %0d cycles, latency %0d each, one response every %0d.%0d cycles",
window, n, total, sum_latency / n, (10 * total / n) / 10, (10 * total / n) % 10);
endtask
Check yourself
Remember
- Latency is the cycles from request to response of one transaction. Throughput is how many complete per unit time. They are linked only through the number in flight.
- With one transaction outstanding, the rate is one per latency plus turnaround. The target's pipeline stages sit empty.
- A pipelined link issues request N+1 while response N is still on its way. The latency of each transaction is unchanged; the idle cycles disappear.
- To saturate a link, keep about latency plus one requests outstanding. Beyond that, the width and the clock set the bandwidth: beats × width × clock.
- With more than one request in flight, every response needs a tag. In-order targets can imply it; out-of-order targets cannot.
Practice
- The throughput that never rose Debug · Medium