A requester has four reads outstanding. A response arrives carrying a word of data. Which of the four reads is it for? If responses always came back in order the answer would be "the oldest", but the four reads went to different targets, and the fastest one answered first. Without a label on the response, the requester cannot tell.

How do responses find their requests, and how many labels does a requester need?

The obvious answer, and why it breaks

The obvious answer is to rely on order: responses come back in the order requests went out. That works with one target and a single path. With several targets of different speeds, or a fabric with several paths, forcing responses into request order means holding fast responses until slow ones arrive, so the slowest target sets everyone's latency. The alternative is to label each request and let the response carry the label back.

The idea: a tag per outstanding request

• Each request carries a tag. The response echoes it.

• The requester keeps a table indexed by tag: what was asked, and where the answer should go.

• A tag is in use from request until its last response; it must not be given to another request while in use, or two outstanding requests would be indistinguishable.

• A free list holds the tags not in use. A new request takes one; a final response returns it.

Three labels that look alike

Specifications use "tag", "ID" and "transaction ID" loosely, but there are three different kinds of label, and they match responses in different ways. Before writing a requester or a scoreboard, find out which one you have.

A unique tag allows full reordering between every pair of requests, and needs one tag per outstanding request. An ordering ID lets a requester keep many requests in flight on a few IDs, at the price of ordering among those that share one. Real protocols often combine them: a PCIe completion is matched by Requester ID plus Tag, and an AXI interconnect widens IDs with the port number so responses can be routed back. The rest of this lesson, and DCLink, use unique tags; lesson 15.5 shows how a scoreboard differs for each.

How many tags?

Tags cap the number of outstanding requests, so by Little's law:

Illustrative: one read per cycle at 1 GHz, worst-case round trip 300 ns
Tags needed:  1e9 per second x 300e-9 s  = 300  ->  9 tag bits (512 tags)
With 6 bits (64 tags):  at most 64 / 300 ns = 213 million reads per second (21% of the rate)

Size for the worst round trip you need full throughput at, not the typical one: tags are held for the whole round trip of the slowest response.

Build it: a tag allocator with a free list

This is DCLink step 5's allocator, with DCLink's 2-bit tag field: 4 tags. The requester wants to send 8 reads back to back; the target answers each after its own latency, so completions come back out of order, at most one per cycle. The checker fails if a tag is ever given out while still in use.

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
47
48
49
50
51
52
53
54
55

// DCLink step 5: a tag allocator with a free list. The requester has 4 tags (the
// 2-bit tag field). A request may go only when a tag is free; it takes the tag at
// the head of the free list. The target answers out of order (each request has its
// own latency, and at most one completion returns per cycle); a completion returns
// its tag to the tail of the free list. The
// checker makes sure no tag is ever given out while it is still in use.
module tb;
  logic clk = 0;
  always #5 clk = ~clk;
  initial begin $dumpfile("wave.vcd"); $dumpvars(0, tb); end

  // Free list: a 4-entry FIFO of tags, full after reset
  logic [1:0] fl [0:3];
  logic [1:0] rp = 0, wp = 0;
  logic [2:0] free_cnt = 4;
  initial begin fl[0] = 0; fl[1] = 1; fl[2] = 2; fl[3] = 3; end

  // Requests: from cycle 1 the requester wants to send 8 requests back to back
  int sent = 0;
  int cyc = 0;
  wire       req = (cyc >= 1) && (sent < 8) && (free_cnt != 0);
  wire [1:0] tag = fl[rp];
  // Target: request k is answered after lat[k] cycles
  int lat [0:7];
  initial begin lat[0] = 6; lat[1] = 2; lat[2] = 4; lat[3] = 1; lat[4] = 3; lat[5] = 5; lat[6] = 2; lat[7] = 1; end
  int        due [0:3];              // cycle at which the request holding each tag completes
  logic [3:0] busy = 0;
  logic       cpl;
  logic [1:0] cpl_tag;
  // One completion per cycle: the lowest busy tag that is due (a later one waits a cycle)
  always_comb begin
    cpl = 0; cpl_tag = 0;
    for (int i = 3; i >= 0; i--) if (busy[i] && due[i] <= cyc) begin cpl = 1; cpl_tag = 2'(i); end
  end

  int errors = 0, completed = 0;
  always @(posedge clk) begin
    cyc <= cyc + 1;
    if (req) begin
      if (busy[tag]) errors++;                           // tag still in use: a bug
      busy[tag] <= 1; due[tag] <= cyc + lat[sent];
      rp <= rp + 1; sent <= sent + 1;
    end
    if (cpl) begin
      busy[cpl_tag] <= 0; fl[wp] <= cpl_tag; wp <= wp + 1; completed++;
    end
    free_cnt <= free_cnt - req + cpl;
  end
  initial begin
    #300;
    if (errors == 0 && completed == 8) $display("PASS: 8 requests completed out of order with 4 tags; no tag was reused while in flight");
    else $display("FAIL: errors %0d completed %0d", errors, completed);
    $finish;
  end
endmodule

The free list is a FIFO of tag numbers: a request takes the head, a completion appends its tag at the tail, so tags are reused in the order they were freed.

Watch it run

How to read it, slot by slot:

• Slots 0 to 3: four requests take tags 0, 1, 2 and 3 (tag), and free_cnt counts down 4, 3, 2, 1.

• Slot 3: the first completion arrives (cpl), for tag 1, not tag 0: request 1 had the shortest latency. A tag is taken and one returned in the same cycle, so free_cnt stays at 1, and in slot 4 the fifth request reuses tag 1.

• Slots 4 and 5: tag 3 completes in slot 4 and the sixth request takes it in slot 5, leaving no free tags (free_cnt 0 in slot 6).

• Slot 6: all four tags are in use and req is low: the requester must wait. Tag 0 completes in slot 6, and the seventh request takes it in slot 7. Read cpl_tag only in slots where cpl is high.

How real protocols chose

What breaks

• Running out of tags: the requester stalls with the link idle, the opening problem of lesson 6.3 in disguise. The symptom is throughput that stops rising when latency rises.

• Reusing a tag too early (illustrative): an allocator that freed a tag on the first of several completions for a split read (lesson 6.8) handed it to a new request, and the old read's remaining data was delivered to the new one. Free a tag only on the last response.

• Lost completions: a tag whose completion never arrives is never freed; after enough losses the requester stops. A timeout that reclaims tags, with an error, prevents a silent leak.

Key takeaways

• Each outstanding request carries a tag that its response echoes; a tag is reserved until the last response.

• Tags needed ≥ request rate × worst round trip; fewer tags cap throughput.

• A free list hands out tags; assert none is reused while in use and none leaks.

Related topics

• Part 6 overview: Concurrency and Performance