Out-of-Order Checking

Scoreboards · Module 18 · Page 18.6

The Engineering Problem

In-order checking pairs outputs to expected positionally via a FIFO — correct only if the DUT produces outputs in input order (Module 18.5). But many DUTs legally complete transactions out of order: a multi-channel block, a cache (a hit returns before an earlier miss), a variable-latency pipeline, an AXI interconnect (responses can return in any order across IDs). For these, the Nth output is not the Nth input's result — positional pairing would flood false mismatches on legal reordering (the 18.5 DebugLab). So you need a different pairing: match each output to its expected by something other than position. That something is a key — an identifier (a transaction ID, a tag) that travels with the transaction and says which input this output is for. But keyed pairing brings its own complications: missing keys (an output for no expected), duplicate keys, and — the sharp one — ID reuse (a limited ID space means an ID is reused once its prior transaction completes, so a naive key→expected map collides). The problem this chapter solves is out-of-order pairing: matching by key, with an associative array, handling the cases.

Out-of-order checking pairs each observed output with its expected by a matching key (an ID), not by position — so it tolerates legal reordering. The predictor inserts expected into an associative array keyed by the ID; on each observed output, the scoreboard looks up the expected with the same ID, compares it (data checking, Module 18.4), and removes the entry. Because the pairing is by key lookup (not position), legal reordering does not cause mismatches (output with id=2 matches expected id=2, whatever order it arrives). It must handle the cases: a missing key (output with no matching expected → extra/wrong), a leftover at end of test (expected never matched → drops), and — critically — ID reuse: when IDs are reused (a limited space, like AXI IDs), a naive single-entry map collides (a reused ID overwrites an outstanding one), so you need a per-ID queue (a FIFO per key) to hold multiple outstanding same-ID transactions, matched in order within the ID. This chapter is out-of-order checking: the associative-array pattern, tolerating reordering, the cases, and ID reuse.

How does out-of-order checking pair each output with its expected by a matching key (via an associative array) so it tolerates legal reordering — and why does ID reuse force a per-ID queue rather than a single-entry-per-key map?

Motivation — why keyed pairing, and why IDs get reused

Out-of-order checking exists because legal reordering needs a pairing that survives it — and the reality of limited ID spaces forces per-ID queues. The reasons:

• Many DUTs legally reorder. A cache (hit before earlier miss), a multi-channel block, a variable-latency pipeline, an AXI fabric — all legally complete transactions out of order. Positional pairing (in-order, Module 18.5) false-mismatches on this legal reordering.
• A key identifies which input an output is for. When order can't be relied on, each transaction carries a key (an ID, a tag) that says which input an output belongs to. Pairing by key matches an output to its expected regardless of order.
• The associative array makes keyed pairing natural. A hash map (expected[id]) inserts by key (predict) and looks up by key (on output) — O(1) pairing by ID, no positional assumption.
• IDs are a limited resource — they get reused. An ID space is finite (e.g., AXI has a bounded number of IDs). So an ID is reused: once a transaction with id=5 completes, a new transaction can also use id=5. If both are outstanding at once (the new one issued before the old completes — or the old's response is in flight), a single-entry expected[5] collides.
• A per-ID queue handles reuse (and intra-ID order). Holding a FIFO per ID (expected[id] is a queue) lets multiple outstanding same-ID transactions coexist, matched in order (which also enforces intra-ID ordering, often required by protocols like AXI: same-ID responses must come back in order).

The motivation, in one line: legal reordering needs pairing that survives it — a key (ID) that identifies which input an output is for, looked up in an associative array (not paired by position) — but because ID spaces are finite, IDs are reused, so a single-entry-per-key map collides on outstanding reuse, requiring a per-ID queue that holds multiple same-ID transactions in order.

Mental Model

Hold out-of-order checking as a coat check with numbered tickets — look up the matching number, regardless of return order, with a small stack per number if numbers repeat:

Out-of-order checking is a coat check with numbered tickets: each coat gets a numbered ticket, and when a coat comes back — in any order — you look up the matching numbered ticket, not the next one on the stack. Numbers tolerate out-of-order return. But if the cloakroom reuses numbers (a small numbered rack), you must keep a small stack of tickets per number, or a reused number would lose the earlier coat. Picture the coat check again — but now with numbered tickets (vs the stacked, order-based tickets of in-order checking, Module 18.5). Each coat (input) gets a numbered ticket (a key/ID), and you file the ticket by its number (insert into the associative array). When a coat is returned — in any order (a fastest-ready-first valet) — you read its number and look up the matching ticket (by key), not the next one on a stack. The number pairs the coat to its ticket regardless of return order — so out-of-order return is fine (it's legal for this valet). Three cases. A coat with a number you have no ticket for (a missing key): an extra or wrong coat. Leftover tickets at closing (keys never matched): lost coats (drops). And the sharp one: if the cloakroom reuses numbers (a limited numbered rack — number 5 is handed out again once that coat is returned), you can't keep just one slot per number — because two coats might both have number 5 at once (the old one's return in flight, the new one just checked in). A single slot would have the new ticket overwrite the old, losing the old coat. So you keep a small stack of tickets per number (a per-ID queue) — and when a number-5 coat returns, you take the oldest number-5 ticket (matching same-number coats in order). The numbered tickets tolerate out-of-order across numbers, and the per-number stack handles reused numbers in order within a number.

So out-of-order checking is a coat check with numbered tickets: file tickets by number (insert by key into the associative array), and look up the matching number for each returned coat (any order). It tolerates out-of-order return (the number pairs regardless of order). It handles missing numbers (extra/wrong), leftover tickets (drops), and — because numbers are reused — keeps a small stack per number (a per-ID queue) so multiple same-number coats are matched in order. Look up the number, not the next ticket — and keep a stack per number when numbers repeat.

Visual Explanation — the associative-array (key lookup) pattern

The defining picture is the keyed map: the predictor inserts expected by ID, and the scoreboard looks up by the output's ID — pairing by key, not position.

The figure shows the associative-array pattern — keyed pairing. The predictor computes the expected and inserts it into an associative array keyed by the transaction's ID (expected[id]). The output monitor observes outputs (in any order), each carrying its ID. On each observed output, the scoreboard reads the output's ID, looks up the expected with the same ID (expected[output.id]), compares it (data checking, Module 18.4), and removes the entry → match / mismatch. The crucial reading is that the pairing is by key lookup, not position: the warning-colored associative array is indexed by ID, so an output's ID directly retrieves its expected — regardless of what order the output arrived. This is the fundamental difference from in-order checking (Module 18.5): in-order pops the front (positional, FIFO); out-of-order looks up by key (associative array). The consequence is that legal reordering is tolerated — outputs arriving in any order are each matched to their correct expected (output id=2 → expected id=2, whatever order). The cases fall out of the lookup: a lookup that finds nothing (the ID is not in the map) is a missing key (an extra/wrong output); entries left in the map at end of test are drops (expected that never got a matching output). The success-colored scoreboard consumes outputs by looking up and removing their keyed expected. The diagram is the anatomy of out-of-order checking: an associative array keyed by ID, inserted by the predictor and looked up by the scoreboard per output — keyed pairing that tolerates reordering, with missing-lookup = extra and leftover = drops. The shift from position (FIFO) to key (map) is the whole idea.

RTL / Simulation Perspective — lookup by key, and the per-ID queue for reuse

In code, the scoreboard uses an associative array keyed by ID — and, to handle ID reuse, a queue per ID (FIFO per key). The code shows both.

class ooo_scoreboard extends uvm_scoreboard;
  // a QUEUE of expected PER ID (handles reuse: multiple outstanding same-ID, matched in order)
  bus_txn expected_by_id[bit [3:0]][$];      // associative array: id -> FIFO of expected
 
  // EXPECTED from the predictor: push onto the per-ID queue (keyed insert)
  function void write_expected(bus_txn e);  expected_by_id[e.id].push_back(e);  endfunction
 
  // OBSERVED output: look up by ID, pop the oldest for that ID, compare
  function void write_actual(bus_txn observed);
    if (!expected_by_id.exists(observed.id) || expected_by_id[observed.id].size() == 0) begin
      `uvm_error("SB", $sformatf("MISSING KEY: output id=%0h has no matching expected", observed.id))
      return;                                  // extra / wrong id
    end
    bus_txn expected = expected_by_id[observed.id].pop_front();  // oldest expected for THIS id
    if (!observed.compare(expected))           // data checking (Module 18.4)
      `uvm_error("SB", $sformatf("MISMATCH id=%0h: got data=%0h exp=%0h", observed.id, observed.data, expected.data))
    if (expected_by_id[observed.id].size() == 0) expected_by_id.delete(observed.id);  // tidy empty key
  endfunction
 
  // END OF TEST: any leftover expected across all IDs = DROPS
  function void check_phase(uvm_phase phase);
    int drops = 0;
    foreach (expected_by_id[id]) drops += expected_by_id[id].size();
    if (drops != 0) `uvm_error("SB", $sformatf("DROPS: %0d expected outputs never arrived", drops))
  endfunction
endclass
// ✗ a SINGLE entry per id (expected_by_id[id] = e) COLLIDES on ID reuse — overwrites the outstanding one (DebugLab)

The code shows the keyed lookup with the per-ID queue. The scoreboard holds an associative array of queues (expected_by_id[id] is a FIFO of expected for that id). write_expected pushes the predictor's expected onto the per-ID queue (keyed insert). write_actual, on each observed output, looks up by ID: if the ID is not present (or its queue is empty), it's a missing key (uvm_error — extra/wrong); otherwise it pops the oldest expected for that ID (pop_front() — matching same-ID transactions in order), compares (data checking), and tidies the empty key. check_phase (end of test) sums leftover expected across all IDs = drops. The closing ✗ comment marks the cardinal difference: a single entry per ID (expected_by_id[id] = e) collides on ID reuse — a new same-ID transaction overwrites the outstanding one, losing it (the DebugLab) — which is why the value is a queue, not a single entry. The shape to carry: out-of-order checking is insert-by-key / lookup-by-key with a per-ID queue — the predictor pushes expected onto expected_by_id[id], the scoreboard looks up by the output's id, pops the oldest for that id, and compares, with missing-key (extra) and end-of-test leftover (drops) checks. The per-ID queue (vs a single entry) is what handles ID reuse (multiple outstanding same-ID, matched in order) and intra-ID ordering (same-ID expected matched in push order). The associative array gives the keyed (order-tolerant) pairing; the per-ID queue gives the reuse-safe, intra-ID-ordered matching.

Verification Perspective — keyed pairing tolerates legal reordering

The defining property of out-of-order checking is that keyed pairing tolerates legal reordering — where positional (in-order) pairing would false-mismatch. Seeing the contrast shows why keyed pairing is necessary for an out-of-order DUT.

The figure contrasts positional and keyed pairing on a legally-reordered output stream. The DUT legally produces outputs out of order: id=2, then id=1, then id=3. With positional (in-order / FIFO) pairing, output id=2 is matched against the front expected (id=1) — a false mismatch — because it pairs by position (the 18.5 DebugLab). With keyed pairing, the scoreboard looks up each output by its ID: output id=2 matches expected id=2, output id=1 matches expected id=1 — correct, no mismatch — because it pairs by key, regardless of order. The verification insight is that keyed pairing is the only correct approach for an out-of-order DUT: when reordering is legal, the only way to pair correctly is by something that travels with the transaction and survives reordering — the key (ID). Positional pairing fails because position is exactly what reordering changes; keyed pairing succeeds because the key is invariant under reordering. The warning-colored out-of-order outputs break the default-colored positional pairing (false mismatch) but are handled by the brand-colored keyed pairing (correct match). This is the whole reason out-of-order checking exists: it replaces the position-based pairing (which reordering destroys) with a key-based pairing (which reordering can't). The trade-off (vs in-order, Module 18.5): out-of-order checking tolerates reordering by design, so it doesn't catch reordering as a bug — correct, because reordering is legal for this DUT; but if a protocol requires intra-ID ordering (AXI: same-ID responses in order), the per-ID queue re-introduces an in-order check within each ID (Figure 1's queue). The figure is the justification for keyed pairing: for a DUT that legally reorders, pair by the key that survives reordering, not the position that reordering changes — keyed pairing is correct, positional is false-mismatch. Match by the invariant (the ID), not the variant (the position).

Runtime / Execution Flow — keyed checking with reuse and the end check

At run time, out-of-order checking runs a per-output loop (lookup by key, pop the per-ID queue, compare) plus the end-of-test leftover check. The flow shows it.

The flow shows out-of-order checking's two parts with the per-ID queue. Lookup (step 1): on each output, index the associative array by the output's ID to find its per-ID queue of expected. Missing key (step 2): if the queue is empty or absent, there's no expected for this ID — an extra or wrong-ID output; report it. Compare (step 3): pop the oldest expected for that ID (matching same-ID transactions in order) and data-check the pair (Module 18.4) — pass or precise mismatch. End of test (step 4): sum the remaining expected across all IDs = drops. The runtime insight is the two layers of the structure: the associative array (keyed by ID) gives the cross-ID order tolerance (look up any ID regardless of arrival order), and the per-ID queue (FIFO per key) gives the intra-ID ordering and reuse handling (multiple outstanding same-ID matched in order). So out-of-order checking is in-order within each key, out-of-order across keys — which is exactly the semantics of many real protocols (AXI: responses for different IDs in any order, responses for the same ID in order). The per-output loop handles the bulk (lookup, pop, compare, missing-key), and the end check handles completeness (leftover = drops) — mirroring in-order checking's structure (Module 18.5) but with keyed lookup replacing positional pop. This is why out-of-order checking is in-order checking generalized: replace the single FIFO (positional) with a map of FIFOs (keyed) — the map tolerates cross-key reordering, each FIFO preserves intra-key order, and the completeness checks (missing-key, leftover) carry over. The flow is the complete out-of-order check: for each output, look up its ID's queue and pop-and-compare (or flag missing); at end, flag leftover drops — keyed, reuse-safe, intra-ID-ordered, and cross-ID-order-tolerant.

Waveform Perspective — outputs in any order, each matched by ID

Out-of-order checking is visible on a timeline: expected are inserted by ID, outputs arrive out of order, and each is looked up by its ID and matched — legal reordering causing no mismatch. The waveform shows it.

The waveform shows keyed pairing tolerating reordering. Expected are inserted by ID (for id=1, id=2, id=3 — the map holds all three). The DUT produces outputs out of order: out_id=2 first, then out_id=1, then out_id=3. Each output is looked up by its ID (lookup_hit) and matched to the expected with the same ID: out_id=2 matches expected id=2 (sb_match), out_id=1 matches expected id=1, out_id=3 matches expected id=3 — all match, despite the reordering. The crucial reading is that the arrival order (2, 1, 3) is different from the insertion order (1, 2, 3), yet every output matches — because the lookup is by ID, not position. The out_id=2 arriving first is not a problem: the scoreboard looks up expected[2] (not the front of a queue) and matches it. The picture to carry is the order-independence of keyed pairing: the ID on each output directly retrieves its expected, so the order the outputs arrive in doesn't matter — legal reordering produces no false mismatch (contrast in-order, Module 18.5, where this exact reordering would flood mismatches). The counterfactual (a missing key): if an output arrived with out_id=7 (not in the map), lookup_hit would be low and the scoreboard would flag a missing key (extra/wrong). Reading this waveform — is each output looked up by its ID and matched, regardless of arrival order? do legal reorderings cause no mismatch? — confirms the out-of-order check. The outputs arriving out of order, each matched by ID lookup with no false mismatch is the signature of out-of-order checking: keyed pairing that tolerates the legal reordering an out-of-order DUT produces — match by the ID, regardless of order.

DebugLab — the scoreboard that lost transactions on ID reuse

✗ SINGLE entry per ID → a reused ID OVERWRITES the outstanding one (collision):
  expected[e.id] = e;            // ✗ one slot per id
  // id=5 issued (expected E5a stored).  id=5 REUSED while E5a still outstanding:
  expected[5] = E5b;             //   ← OVERWRITES E5a → E5a LOST (drop), and the next id=5 output
  //   gets paired with E5b instead of E5a → mismatch.  Both failures stem from the collision.
 
✓ PER-ID QUEUE → multiple outstanding same-ID coexist, matched in order:
  expected_by_id[e.id].push_back(e);                 // a FIFO per id
  // id=5 issued: queue[5] = [E5a].  id=5 reused: queue[5] = [E5a, E5b]  (both held)
  // first id=5 output → pop E5a (oldest); second id=5 output → pop E5b → correct, in order

Common Mistakes

• A single entry per ID. When IDs are reused, a single-slot map collides — a reused ID overwrites the outstanding one; use a per-ID queue.
• Assuming IDs are unique. ID spaces are finite and reused over a run; design for reuse, not uniqueness.
• Forgetting the missing-key check. An output whose ID isn't in the map is an extra or wrong-ID output; flag it.
• Forgetting the end-of-test leftover check. Expected left across all IDs at end are drops; sum and report them.
• Ignoring intra-ID ordering. If the protocol requires same-ID responses in order, the per-ID FIFO enforces it; a plain map or set doesn't.
• Using out-of-order checking on an in-order DUT. It works but gives up catching illegal reordering as a bug; use in-order checking when the DUT is in-order.

Senior Design Review Notes

Interview Insights

Exercises

1. Trace the map. For inputs with IDs 1, 2, 3 and outputs arriving 2, 1, 3, trace the associative-array lookups and the matches.
2. Show the collision. Demonstrate how a single entry per ID loses a transaction when ID 5 is reused while outstanding, and fix it with a per-ID queue.
3. Detect the missing key. Explain what happens when an output arrives with an ID not in the map, and how it's reported.
4. Relate the two. Explain how out-of-order checking generalizes in-order checking, and what a single-ID out-of-order checker reduces to.

Summary

• Out-of-order checking pairs each observed output with its expected by a matching key (an ID), not by position — via an associative array (insert by key, look up by the output's key, compare, remove) — so it tolerates legal reordering.
• Keyed pairing is necessary for an out-of-order DUT: position is what reordering changes, but the key (ID) is invariant under reordering, so an output's ID retrieves its correct expected regardless of order (where positional pairing would false-mismatch).
• It handles the cases: a missing key (output with no matching expected → extra/wrong), a leftover at end of test (expected never matched → drops), and — critically — ID reuse.
• ID reuse forces a per-ID queue (a FIFO per key), not a single entry per ID: because ID spaces are finite and IDs are reused, a reused ID outstanding alongside its prior collides in a single-slot map (overwriting and losing it); the per-ID queue holds multiple outstanding same-ID transactions, matched in order (also enforcing intra-ID ordering).
• The durable rule of thumb: for an out-of-order DUT, pair by key (an ID) via an associative array — look up each output's expected by its ID, tolerating legal reordering — and use a per-ID queue (FIFO per key), never a single slot, because finite ID spaces mean reused IDs can be outstanding at once and would collide (drops and mismatches that correlate with throughput); the per-ID queue holds multiple outstanding same-ID transactions in order, making out-of-order checking in-order within each key and out-of-order across keys.

Next — Scoreboard Debugging: the module closes with the methodology — how to debug a scoreboard failure: telling a real DUT bug from a checker bug (predictor, reference model, pairing, or comparison), reading a mismatch report and the surrounding context, and a systematic process from a reported mismatch to its true cause.