Streaming Ordering

Chapter 9.2 got messages across the link with their boundaries intact. It said nothing about when — specifically, nothing about whether a packet handed to the transport after another packet may arrive before it.

That question sounds like it should have a short answer, and it does not. "Is the link ordered?" is not a well-formed question, because ordering is never a property of a link — it is a property of a relationship between two specific items. Two packets from the same message must not pass one another. Two packets from unrelated protocol streams almost certainly may. Everything interesting is between those cases.

This chapter is about asking the question correctly, and about the hardware that answers it.

1. The One-Sentence Model

Ordering is defined over an ordering domain, not over "all traffic." The first question is never "is it ordered?" but "which items are required to observe one another?"

Once the domain is named, the hardware follows almost mechanically: items within a domain go through a structure that cannot reorder them, and the scheduler is constrained to pick only from the front of each. Get the domain wrong and every downstream decision — the queue structure, the arbiter, the scoreboard — is wrong in a way that still looks reasonable.

2. Establish the Domain Before Anything Else

Candidate ordering domains, in increasing strictness:

The engineering question is never "which is best" — it is which one does the protocol I am carrying actually require, and the answer is usually narrower than instinct suggests. Ordering is expensive, and ordering you do not need is expense with no return: it buys head-of-line blocking (§7) and buys nothing.

Over-ordering is a performance bug that passes every correctness test. It is also nearly invisible, because nothing ever fails — the link is simply slower than it should be, for a structural reason no waveform shows.

3. The Two Ways to Enforce Order

Worth separating, because they lead to different hardware and different verification.

Structural ordering. Items pass through something that physically cannot reorder them — a FIFO, and a scheduler that only ever takes from the front. There is no order field anywhere; order is a consequence of the data structure. Cheap, and it proves itself.

Explicit ordering. Items carry an identifier, and the receiver uses it to restore order — sequence numbers plus a reorder buffer. More state, tolerates a reordering path in between, and needs the receiver to hold items until their predecessors arrive.

Which you need depends on whether anything between the two endpoints can reorder. If the transmit side is FIFO-ordered and the link delivers in order, structural ordering is sufficient and an explicit sequence field is pure cost. If retry can deliver a replayed packet after a later one (§10), or if multiple paths exist, structural ordering is not enough.

Do not assume a sequence field exists on the wire. Chapter 9.4 examines what the reliability mechanism actually retains and identifies; for this chapter, treat any sequence value in the RTL as internal to the implementation or to the testbench, not as a UCIe packet field.

4. Per-Stream Queues

The natural structure once the domain is per stream:

// Illustrative streaming RTL — not UCIe normative naming or encoding.
localparam int NUM_STREAMS = 4;
localparam int Q_DEPTH     = 8;
localparam int Q_PTR_W     = $clog2(Q_DEPTH);
localparam int Q_CNT_W     = $clog2(Q_DEPTH + 1);
 
stream_packet_t  sq_mem   [NUM_STREAMS][Q_DEPTH];
logic [Q_PTR_W-1:0] sq_wr_q [NUM_STREAMS];
logic [Q_PTR_W-1:0] sq_rd_q [NUM_STREAMS];
logic [Q_CNT_W-1:0] sq_cnt_q[NUM_STREAMS];
 
logic [NUM_STREAMS-1:0] sq_nonempty;
logic [NUM_STREAMS-1:0] sq_full;
 
always_comb
  for (int s = 0; s < NUM_STREAMS; s++) begin
    sq_nonempty[s] = (sq_cnt_q[s] != '0);
    sq_full[s]     = (sq_cnt_q[s] == Q_CNT_W'(Q_DEPTH));
  end
 
always_ff @(posedge clk or negedge rst_n) begin
  if (!rst_n) begin
    for (int s = 0; s < NUM_STREAMS; s++) begin
      sq_wr_q[s]  <= '0;
      sq_rd_q[s]  <= '0;
      sq_cnt_q[s] <= '0;
    end
  end else begin
    for (int s = 0; s < NUM_STREAMS; s++) begin
      // Simultaneous push and pop leave the count unchanged.
      if (sq_push[s] && !sq_pop[s])      sq_cnt_q[s] <= sq_cnt_q[s] + 1'b1;
      else if (sq_pop[s] && !sq_push[s]) sq_cnt_q[s] <= sq_cnt_q[s] - 1'b1;
 
      if (sq_push[s]) begin
        sq_mem[s][sq_wr_q[s]] <= sq_wr_data;
        sq_wr_q[s] <= sq_wr_q[s] + 1'b1;      // wraps naturally at Q_DEPTH
      end
      if (sq_pop[s]) sq_rd_q[s] <= sq_rd_q[s] + 1'b1;
    end
  end
end

Architecture. Items in one domain must not reorder; items in different domains should not block each other. Separate FIFOs give both properties structurally.

State. Per stream: a memory, write and read pointers, and an occupancy count — per-stream lifetime, distinct from the per-packet contents.

Cycle behaviour. Push writes at the write pointer and advances it; pop advances the read pointer. Simultaneous push and pop leave the count unchanged and move both pointers.

Contract. The arbiter (§5) reads only sq_mem[s][sq_rd_q[s]] — the head. Nothing else may be dequeued, and that restriction is where ordering is actually enforced.

Failure. Sizing pointers as $clog2(Q_DEPTH) makes them wrap naturally only when Q_DEPTH is a power of two. With a non-power-of-two depth the pointers wrap early and silently alias, so a queue of depth 6 with 3-bit pointers reads entry 0 when it should read entry 6 — delivering a stale packet with correct framing. §8 covers this.

DV. Cover each queue empty, partially filled, and full; and cover wrap on both pointers.

5. The Arbiter Must Take Heads Only

This is where ordering is enforced, and where it is most commonly broken.

// WRONG — selecting whichever buffered packet looks most attractive.
always_comb begin
  sel_valid = 1'b0;
  for (int s = 0; s < NUM_STREAMS; s++)
    for (int e = 0; e < Q_DEPTH; e++)
      if (sq_entry_valid[s][e] && sq_mem[s][e].hdr.urgent) begin
        sel_stream = s;
        sel_entry  = e;          // any entry, not the head
        sel_valid  = 1'b1;
      end
end

This scans all buffered entries and picks by attractiveness. If stream A holds A0 followed by A1, and A1 is marked urgent, A1 transmits before A0 — a same-stream reorder produced by an arbiter that is otherwise working exactly as designed.

The correct arbiter chooses among stream heads and nothing else:

// Illustrative — round-robin over stream HEADS only.
logic [$clog2(NUM_STREAMS)-1:0] rr_ptr_q;
logic [NUM_STREAMS-1:0]         eligible;
logic [$clog2(NUM_STREAMS)-1:0] sel_stream;
logic                           sel_valid;
 
assign eligible = sq_nonempty & ~stream_blocked;   // blocked: §9
 
always_comb begin
  sel_valid  = 1'b0;
  sel_stream = rr_ptr_q;
  // Search from the round-robin pointer, wrapping — first eligible head wins.
  for (int i = 0; i < NUM_STREAMS; i++) begin
    automatic int s = (int'(rr_ptr_q) + i) % NUM_STREAMS;
    if (!sel_valid && eligible[s]) begin
      sel_stream = ($clog2(NUM_STREAMS))'(s);
      sel_valid  = 1'b1;
    end
  end
end
 
// The selected packet is ALWAYS the head of its queue — not a choice.
assign tx_packet = sq_mem[sel_stream][sq_rd_q[sel_stream]];
 
always_ff @(posedge clk or negedge rst_n) begin
  if (!rst_n)         rr_ptr_q <= '0;
  else if (tx_fire)   rr_ptr_q <= (sel_stream == ($clog2(NUM_STREAMS))'(NUM_STREAMS-1))
                                    ? '0 : sel_stream + 1'b1;
end

Architecture. The arbiter's freedom must be exactly one dimension — which stream — and never which packet within a stream. Making the head the only addressable entry turns ordering from a rule that must be obeyed into a structure that cannot be violated.

State. A round-robin pointer, advanced past the stream just served so no stream monopolises.

Cycle behaviour. Combinational selection over eligibility; the pointer advances on a successful transfer.

Contract. Ordering within a stream is guaranteed by construction. Fairness across streams is a separate property (§11) that this pointer provides and the ordering rule does not.

Failure. The wrong version above. Note it is not a stupid mistake — it is what you get by extending a working single-stream design with priority, and every individual line reads correctly.

// Illustrative — only a stream head may be transmitted.
property p_only_head_transmitted;
  @(posedge clk) disable iff (!rst_n)
    tx_fire |-> (tx_packet == sq_mem[sel_stream][sq_rd_q[sel_stream]]);
endproperty
 
// Illustrative — the read pointer advances by exactly one per transfer.
property p_rd_ptr_advances_by_one;
  @(posedge clk) disable iff (!rst_n)
    (tx_fire && (sel_stream == s)) |=>
      (sq_rd_q[s] == $past(sq_rd_q[s]) + 1'b1);
endproperty

6. Legal Interleaving Versus Illegal Bypass

The distinction, made concrete. Stream A offers A0, A1, A2; stream B offers B0, B1.

Legal — every one of these preserves per-stream order:

A0 B0 A1 B1 A2        round-robin
A0 A1 A2 B0 B1        A drained first
B0 B1 A0 A1 A2        B drained first
A0 B0 B1 A1 A2        uneven service

Illegal — under per-stream ordering:

A1 A0 ...             A1 passed A0 — same-stream bypass
A0 A2 A1 ...          A2 passed A1 — same-stream bypass

The pattern is simple once seen: relative order within a letter must be preserved; interleaving between letters is free. An arbiter constrained to heads produces only the legal set, and cannot produce the illegal set at all.

7. Head-of-Line Blocking Is the Price

Per-stream ordering has a cost, and it is not optional.

If A0 cannot be transmitted — its destination is backpressuring, its resources are unavailable, it is awaiting a retry — then A1 cannot pass it, even though A1 might be perfectly ready. That is head-of-line blocking, and it is not a bug: it is the ordering guarantee being honoured.

What is a design choice is its scope:

Head-of-line blocking is the price of ordering, and the ordering domain sets how much you pay. A global FIFO is the cheapest structure and the most expensive stall.

This is the real argument for per-stream queues, and it is a performance argument rather than a correctness one: a global FIFO is correct for per-stream ordering — it just over-delivers, and one stalled stream takes the link down with it.

8. Pointer Wrap Is Where Order Quietly Breaks

Ordering bugs concentrate at the wrap boundary, because that is where pointer arithmetic stops being obvious.

// WRONG — pointer width does not match a non-power-of-two depth.
localparam int Q_DEPTH = 6;
logic [$clog2(Q_DEPTH)-1:0] wr_q;      // 3 bits: wraps at 8, not at 6

With Q_DEPTH = 6, $clog2(6) is 3, so the pointer counts 0–7 and wraps at 8. Entries 6 and 7 do not exist. The pointer addresses memory that was never written, and the occupancy counter — which is sized correctly — disagrees with the pointers about how many items there are. The queue delivers stale entries, in the wrong order, with perfectly valid framing.

Two safe forms:

// Illustrative — either use a power-of-two depth and let it wrap naturally...
localparam int Q_DEPTH = 8;
logic [$clog2(Q_DEPTH)-1:0] wr_q;                  // 3 bits, wraps at 8 ✓
 
// ...or wrap explicitly at the depth.
localparam int Q_DEPTH_NP2 = 6;
logic [$clog2(Q_DEPTH_NP2)-1:0] wr_np2_q;
always_ff @(posedge clk or negedge rst_n) begin
  if (!rst_n)      wr_np2_q <= '0;
  else if (push)   wr_np2_q <= (wr_np2_q == Q_DEPTH_NP2-1) ? '0 : wr_np2_q + 1'b1;
end

Why this hides so well. The bug appears only after Q_DEPTH pushes — so a directed test with three packets never sees it, and a random test sees it only at sustained high occupancy. It then presents as a reordering or duplication that correlates with load and nothing else.

// Illustrative — pointers and occupancy must agree, including across wrap.
property p_count_matches_pointers;
  @(posedge clk) disable iff (!rst_n)
    (sq_cnt_q[s] == Q_CNT_W'((sq_wr_q[s] - sq_rd_q[s]) % Q_DEPTH))
      || (sq_cnt_q[s] == Q_CNT_W'(Q_DEPTH));      // full: pointers equal
endproperty

Coverage must reach the wrap, or the assertion never runs where it matters: cover push-across-wrap, pop-across-wrap, and both in the same cycle.

9. Ordering Meets Backpressure

If stream A's consumer stalls, can stream B proceed? Only if the structure separates them.

Two readings. A1 waits at cycle 3 even though it is ready — head-of-line blocking, working as intended, because A0's ordering obligation has not been discharged. And B keeps flowing throughout, which is the entire return on per-stream queues; with one global FIFO, cycles 3 to 5 would carry nothing at all.

The stream_blocked term in §5's eligibility is what implements this, and where that signal comes from is Chapter 9.5's subject — credit-based backpressure on the streaming channel. This chapter only needs it to exist.

10. Retry Must Not Break the Ordering It Protects

The bridge to Chapter 9.4, and the subtlest interaction in the module.

Suppose A0 and A1 have both been transmitted, and A0 is found corrupt while A1 arrived cleanly. Under per-stream ordering, A1 must not become visible to the consumer before A0. If the receiver delivers A1 and then A0 arrives by replay, the consumer has observed the stream out of order — a violation produced not by the scheduler but by the recovery mechanism.

Retry cannot violate the ordering contract it is protecting. A reliability mechanism that recovers data while permuting it has not recovered anything.

Architecturally there are three families of answer, and which applies is a property of the reliability contract rather than a free choice:

Receiver holds. Later same-domain items are held, undelivered, until the older one is resolved. Costs receive-side buffering; keeps the transmitter simple.

Transmitter does not get ahead. The window of unresolved items is bounded such that reordering cannot arise. Costs throughput.

Replay from the failure point. Everything from the corrupted item onward is resent, so the receiver discards what it already had and re-receives in order. Costs bandwidth.

Which of these the UCIe streaming reliability contract uses is Chapter 9.4's question, and this chapter deliberately does not answer it. What matters here is recognising that the ordering domain constrains the reliability design — the two mechanisms cannot be specified independently, and a team that designs them in separate rooms produces exactly this bug.

11. Ordering Is Not Fairness

Two properties that are easy to conflate and are entirely independent.

Ordering is a safety property: within a domain, nothing may be observed out of sequence. An arbiter that always selects stream A and never selects stream B satisfies ordering perfectly — B's packets are in order, all zero of them.

Fairness is a liveness property: every stream with work eventually gets served. It requires progress assumptions and is provable only under them.

// Illustrative — bounded fairness, under explicit assumptions.
// Assumes: the link is operational, the downstream eventually accepts, and
// the stream is not blocked. Without those, no such property can hold.
property p_head_eventually_served;
  @(posedge clk) disable iff (!rst_n)
    (sq_nonempty[s] && !stream_blocked[s] && link_operational)
      |-> ##[1:MAX_ARB_WAIT] (tx_fire && (sel_stream == s));
endproperty

Why bounded and why the assumptions are written out. An unbounded ##[1:$] is vacuous in simulation and, without the antecedent conditions, simply false — a blocked stream legitimately never gets served. MAX_ARB_WAIT for round-robin over N streams is on the order of N grants, and stating that bound is what makes the property a real check on the arbiter rather than a statement of hope.

Why it matters in practice. A starving stream looks like a functional failure to whoever owns it, and like nothing at all to the link — no errors, no ordering violation, correct data. Fairness has to be verified deliberately because nothing else notices it.

12. Priority Fights Ordering

An architectural tension worth naming, because it comes up in every real design review.

Suppose a high-priority message is queued behind a low-priority one in the same stream. Under strict per-stream ordering it cannot bypass — the ordering rule does not have an exception for importance.

The choices are all uncomfortable:

• Accept the latency. Priority is honoured only across streams, not within one.
• Put priorities in different ordering domains — a separate stream per priority. Then bypass is legal because the two are unrelated. This is usually the right answer, and it costs queues and stream identifiers.
• Weaken the ordering domain, if the protocol genuinely does not require ordering between those message types. Requires knowing the protocol's real needs rather than assuming.

If two items must be able to pass each other, they do not belong in the same ordering domain. Priority bypass is not an exception to ordering; it is evidence the domain was drawn too widely.

That framing resolves most of these arguments, and it is a reminder that §2's question — which items must observe one another — is an architectural decision that should be made deliberately rather than inherited.

13. The Scoreboard Must Model the Right Domain

The most important verification point in the chapter, and the one where a wrong reference model does active harm.

// WRONG as a model of per-stream ordering — a single global expectation.
expected_q.push_back(pkt);              // one queue for all streams
// ... at the receiver:
if (rx_pkt != expected_q.pop_front()) error("ordering violation");

With streams interleaving legally, this reports a violation on the first legal interleave. The DUT is correct; the checker is wrong; and the team spends a day proving the RTL innocent.

The reverse error is worse. A per-stream model applied to a protocol that genuinely requires global ordering silently accepts reordering that violates the contract — and that one ships.

// Illustrative reference model — one expectation queue PER ORDERING DOMAIN.
// The domain here is the stream; if your protocol's domain is different,
// this data structure must change with it.
stream_packet_t expected[NUM_STREAMS][$];
 
// Transmit side: push in the order the SOURCE offered them.
function void on_source_accept(int sid, stream_packet_t p);
  expected[sid].push_back(p);
endfunction
 
// Receive side: the head of that stream's queue is the only legal next item.
function void on_sink_deliver(int sid, stream_packet_t p);
  if (expected[sid].size() == 0)
    error($sformatf("stream %0d: unexpected packet", sid));
  else if (p !== expected[sid][0])
    error($sformatf("stream %0d: expected %p, got %p", sid, expected[sid][0], p));
  else
    void'(expected[sid].pop_front());
endfunction

What it stores. One ordered queue per ordering domain, holding the semantic items in source order. Nothing about the transport is modelled — deliberately, so the reference cannot inherit the DUT's mistakes.

What it detects. Same-domain reordering, loss (a queue that never drains), duplication (an item delivered with an empty queue or a repeated head), and misattribution (an item arriving on the wrong stream's queue).

What it must report to be useful. Not merely "mismatch". The expected item, the actual item, the stream, the recent arbiter grants, and any retry activity in flight — because §10 means an ordering failure may be a reliability bug wearing ordering's clothes.

The rule to take away: the number of expectation queues equals the number of ordering domains. One queue means global ordering; one per stream means per-stream ordering; and choosing the wrong count produces either false failures or silent escapes.

// Illustrative streaming-ordering coverage — not UCIe-defined.
covergroup cg_ordering @(posedge clk iff tx_fire);
 
  cp_stream    : coverpoint sel_stream;
  cp_active    : coverpoint $countones(sq_nonempty) {
    bins one = {1}; bins two = {2}; bins many = {[3:NUM_STREAMS]};
  }
  cp_switch    : coverpoint (sel_stream != $past(sel_stream));  // interleaving
  cp_occupancy : coverpoint sq_cnt_q[sel_stream] {
    bins low = {[1:2]}; bins mid = {[3:Q_DEPTH-1]}; bins full = {Q_DEPTH};
  }
  cp_wrap      : coverpoint (sq_rd_q[sel_stream] == '0);        // wrap point
  cp_blocked   : coverpoint (|stream_blocked);
 
  // Was interleaving exercised with several streams genuinely active?
  x_switch_by_active : cross cp_switch, cp_active;
  // Did a wrap ever happen at high occupancy — where §8's bug lives?
  x_wrap_by_occ      : cross cp_wrap, cp_occupancy;
  // Did one stream progress while another was blocked?
  x_switch_by_block  : cross cp_switch, cp_blocked;
 
endgroup

Why x_switch_by_active matters. Alternating between streams when only one is ever non-empty is not interleaving — it is a single stream with gaps. The cross is what proves genuine concurrency was tested.

14. Debug: Data Correct, Order Wrong

1. Which ordering domain do the two packets belong to? If different streams, and the domain is per stream, there is no violation — check the scoreboard before the RTL (§13).
2. Did they enter in source order? If the enqueue order was already wrong, the bug is upstream of the queues.
3. Did the arbiter dequeue heads only? §5 — the highest-yield RTL check.
4. Do the pointers and the occupancy count agree? §8 — and specifically at high occupancy, where the wrap bug lives.
5. Is Q_DEPTH a power of two? If not, verify the wrap is explicit.
6. Did a retry occur near the divergence? §10 — a younger packet delivered while an older one awaits replay is a reliability interaction, not an arbiter bug.
7. Was one stream blocked? Then its head waiting is correct behaviour, and what you are seeing may be head-of-line blocking rather than a fault.
8. Is stream identity still attached to the right payload? A misrouted stream_id presents as an ordering error on two streams at once.
9. Did a reset or recovery clear one side's expectations and not the other's? The scoreboard and the DUT must re-baseline together.
10. Is it starvation rather than reordering? Correct order, no progress, no errors — §11.

Step 1 first, always. A meaningful fraction of reported ordering bugs are scoreboard-domain errors, and it costs one look at the reference model to rule out.

15. Common Misconceptions

"Ordering means the link is globally ordered." Ordering is a relationship between specific items. The first question is which items must observe one another (§1, §2).

"Correct payload data means ordering is correct." Ordering bugs do not corrupt bytes — every packet is intact and in the wrong place, which is why they pass data-integrity checks (§6).

"Different streams may never interleave." Interleaving across domains is free and is the entire benefit of per-stream queues; only same-domain bypass is a violation (§6).

"A global FIFO is always safest." It is correct for per-stream ordering and over-delivers, so one stalled stream blocks the link — a performance bug that passes every correctness test (§2, §7).

"A scheduler may pick any ready packet." It may pick any eligible stream, and then only that stream's head. That restriction is where ordering is enforced (§5).

"Retry is independent of ordering." A replayed packet arriving after a younger one violates the ordering the retry was protecting; the two mechanisms must be designed together (§10).

"Priority can bypass older packets." Not within an ordering domain. If two items must pass each other, they belong in different domains (§12).

"A global scoreboard works for per-stream ordering." It reports a violation on the first legal interleave. The number of expectation queues must equal the number of ordering domains (§13).

"Pointer wrap is a storage concern." A pointer whose width does not match a non-power-of-two depth aliases silently and delivers stale entries in the wrong order, only at high occupancy (§8).

"Ordering and fairness are the same." An arbiter that never serves a stream satisfies ordering perfectly. Fairness is a separate liveness property needing explicit assumptions (§11).

16. Understanding Check

17. Summary and What Comes Next

Ordering is defined over a domain, not over a link. The first question is which items must observe one another, and the answer — none, per stream, per class, or global — determines the queue structure, the arbiter's freedom, and the shape of the reference model. I could not verify UCIe's normative streaming ordering guarantee and have deliberately not asserted one; what is supported is that the Adapter multiplexes protocols and arbitrates between them, and Chapter 9.1's verified payload opacity implies the transport can only guarantee things about the objects it understands.

The hardware, once the domain is named: per-stream FIFOs make ordering possible, and head-only arbitration is where it is actually enforced — the arbiter chooses a stream, never a packet within one. Interleaving across domains is free; same-domain bypass is the only violation. Head-of-line blocking is the price, and the queue structure sets how much of it you pay: a global FIFO is correct and lets one stalled item stop everything.

Three traps: pointer wrap with a non-power-of-two depth aliases silently and only at high occupancy; priority does not get an exception — if two items must pass each other they belong in different domains; and ordering is not fairness, since an arbiter that never serves a stream satisfies ordering perfectly.

Above all, the verification rule: the number of expectation queues equals the number of ordering domains. A global model on a per-stream protocol reports failures that are not real; a per-stream model on a globally ordered protocol silently accepts violations that are. And in debug, check the scoreboard's domain before the RTL — a meaningful fraction of reported ordering bugs are modelling errors.

Ordering says which packet must be observed first. It assumes the packet arrives at all:

• 9.4 — Streaming Reliability — what a transmitter must retain so a corrupted packet can be recovered without loss, duplication, or the reordering this chapter just forbade.

Browse the full path on the UCIe tutorials index.