A video decoder reads frame data from memory with many reads outstanding, and the memory system returns them in whatever order its banks happen to finish. The decoder must process the data in order: block 0, then block 1. The data for block 5 has arrived; block 1's has not. Block 5 needs somewhere to wait, and the decoder needs to know when block 1 finally turns up.

How does a receiver put out-of-order responses back in order, and how big must that buffer be?

The obvious answer, and why it breaks

The obvious answer is to process data as it arrives. That only works when the consumer does not care about order. When it does, early responses must be held until every earlier one has arrived, and the holding area has to be large enough for the worst reordering, or the receiver must stop accepting responses, which is dangerous in its own way.

The idea: a slot per outstanding request

• Number requests in order as they are sent: 0, 1, 2, …. A reorder buffer (ROB) has a slot for each request that may be outstanding; request n uses slot n mod size.

• A response is written into its request's slot whenever it arrives.

• The output looks only at the slot of the oldest outstanding request (the head). When that slot is filled, its data leaves and the head moves on.

• A new request may be sent only if its slot is free, so the ROB size also limits how many requests are outstanding.

Build it: a 4-entry reorder buffer

Eight responses arrive one per cycle in the order 2, 0, 3, 1, 5, 4, 7, 6. The ROB releases them in order; the checker fails if anything leaves out of order.

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
38
39
40
41
42
43
44
45
46

// A 4-entry reorder buffer. Requests are issued in order and numbered 0, 1, 2, ...;
// request n uses ROB slot n mod 4. Responses come back out of order and are written
// into their slot. The output takes the slot of the oldest outstanding request only
// when it is filled, so data leaves in request order.
module tb;
  logic clk = 0;
  always #5 clk = ~clk;
  initial begin $dumpfile("wave.vcd"); $dumpvars(0, tb); end

  // Response stream: (valid, sequence number) per cycle, out of order
  logic       rsp_vld;
  logic [2:0] rsp_seq;
  int cyc = 0;
  always_comb begin
    rsp_vld = 1; rsp_seq = 0;
    case (cyc)
      1: rsp_seq = 2;  2: rsp_seq = 0;  3: rsp_seq = 3;  4: rsp_seq = 1;
      5: rsp_seq = 5;  6: rsp_seq = 4;  7: rsp_seq = 7;  8: rsp_seq = 6;
      default: rsp_vld = 0;
    endcase
  end

  logic [3:0] filled = 0;
  logic [2:0] data [0:3];
  logic [2:0] head = 0;                         // oldest outstanding sequence number
  wire        out_vld = filled[head[1:0]];
  wire [2:0]  out_seq = data[head[1:0]];

  int errors = 0, delivered = 0;
  always @(posedge clk) begin
    cyc <= cyc + 1;
    if (out_vld) begin
      if (out_seq != head) errors++;            // must leave in request order
      head <= head + 1; delivered++;
    end
    // a slot freed and refilled in the same cycle: the write wins
    if (rsp_vld) begin filled[rsp_seq[1:0]] <= 1; data[rsp_seq[1:0]] <= rsp_seq; end
    if (out_vld && !(rsp_vld && rsp_seq[1:0] == head[1:0])) filled[head[1:0]] <= 0;
  end
  initial begin
    #150;
    if (errors == 0 && delivered == 8) $display("PASS: 8 responses arrived out of order and left the ROB in order 0..7");
    else $display("FAIL: errors %0d delivered %0d", errors, delivered);
    $finish;
  end
endmodule

The output is combinational from the head slot; the only subtle line handles a slot being emptied and refilled by a new response in the same cycle.

Watch it run

How to read it, slot by slot (out_seq is meaningful only where out_vld is high):

• Slots 0 and 1: response 2 arrives (rsp_seq 2), then response 0. Response 2 cannot leave: request 0 is older.

• Slot 2: response 0 is in its slot, so it leaves (out_vld, out_seq 0). Response 3 arrives in the same slot.

• Slot 3: the head is now request 1, which has not arrived: nothing leaves. Response 1 arrives.

• Slots 4 to 10: 1 leaves, then 2 and 3, which were waiting, then 4 to 7 as each arrives in time. Eight responses in, eight out, in order 0 to 7.

Sizing and placement

The deadlock risk

A ROB that allocates slots at request time can always accept every response it asked for. A design that instead accepts responses only when it has room "at the moment" can deadlock: the ROB is full of early responses waiting for an older one, the older one is stuck in the fabric behind those same responses' siblings, and the fabric cannot deliver it because the ROB will not accept anything. The rule: a requester must be able to accept every response it has requested, without first needing another response. Allocating at request time guarantees it.

What breaks

A DMA engine (illustrative) shared one response buffer between two read streams, and reordered within it. Under heavy traffic the buffer filled with early responses for stream A while stream A's oldest response sat behind stream B's responses in the interconnect, and stream B's responses could not enter the full buffer. Both streams stopped. Giving each stream its own slots, reserved at request time, removed the deadlock.

Key takeaways

• A reorder buffer holds early responses in per-request slots and releases them from the head, in order.

• Size it by Little's law in whole responses, and place it at the requester that needs order.

• Reserve a slot when the request is sent, so every requested response can always be accepted.

Related topics

• Part 6 overview: Concurrency and Performance