Out-of-Order Ordering and Memory Consistency

Mechanism and evidence

Guided verification lab

Match identity before comparing order.

Step through three responses and distinguish a legal cross-ID interleave from a same-ID violation.

STEP THROUGH

STATE & OBSERVATIONLegal interleaving / 1 of 4

ID A · OLDEST EXPECTEDA0

ID B · OLDEST EXPECTEDB0

↓ Independent queues converge on the observed response

OBSERVED RESPONSE—

ready

Checkpoint 1 · Keep separate expectation queues.

OBSERVED: —
ID A HEAD: A0
ID B HEAD: B0
VERDICT: ready

Compare all 4 checkpoints

1 · Keep separate expectation queues.
OBSERVED
—
ID A HEAD
A0
ID B HEAD
B0
VERDICT
ready
2 · Response B0 arrives.
OBSERVED
B0
ID A HEAD
A0
ID B HEAD
empty
VERDICT
legal
3 · Response A0 arrives.
OBSERVED
A0
ID A HEAD
A1
ID B HEAD
empty
VERDICT
legal
4 · Response A1 arrives.
OBSERVED
A1
ID A HEAD
empty
ID B HEAD
empty
VERDICT
complete

Inspect the contract

Keep separate expectation queues.

ID A: A0 → A1
ID B: B0

The scoreboard expects A0 then A1 for ID A, and B0 for ID B. It does not impose a global FIFO on both IDs.

Evidence to inspect

Inspect the oldest expected item in each ordering domain.

Checkpoint 1 / 4

Inspect the checker Selected checkpoint pseudocode

Conceptual checker / selected checkpoint

expected[A] = [A0, A1];
expected[B] = [B0];

Example contract & limitations

Example contract. One read channel and one destination are modeled. A0 precedes A1 in ID A; B0 belongs to ID B. Per-ID matching alone does not prove architectural memory consistency or ordering across channels. Checkpoints show selected state changes, not equally spaced simulation cycles.

Read the complete walkthrough

Legal interleaving

Keep separate expectation queues.. The scoreboard expects A0 then A1 for ID A, and B0 for ID B. It does not impose a global FIFO on both IDs. Evidence: Inspect the oldest expected item in each ordering domain.
Response B0 arrives.. Compare B0 to the oldest eligible item in its own ID queue. Other IDs may interleave independently. Evidence: Retain the observed ID, expected queue head, and response sequence.
Response A0 arrives.. Compare A0 to the oldest eligible item in its own ID queue. Other IDs may interleave independently. Evidence: Retain the observed ID, expected queue head, and response sequence.
Response A1 arrives.. Compare A1 to the oldest eligible item in its own ID queue. Other IDs may interleave independently. Evidence: Retain the observed ID, expected queue head, and response sequence.

Same-ID reorder

Keep separate expectation queues.. The scoreboard expects A0 then A1 for ID A, and B0 for ID B. It does not impose a global FIFO on both IDs. Evidence: Inspect the oldest expected item in each ordering domain.
Response A1 arrives.. A1 arrives while A0 is still the oldest expected response for ID A. Report the order violation without consuming A0. Evidence: Retain the observed ID, expected queue head, and response sequence.
Response B0 arrives.. Compare B0 to the oldest eligible item in its own ID queue. Other IDs may interleave independently. Evidence: Retain the observed ID, expected queue head, and response sequence.
Response A0 arrives.. Compare A0 to the oldest eligible item in its own ID queue. Other IDs may interleave independently. Evidence: Retain the observed ID, expected queue head, and response sequence.

Related implementation: Compare the oldest expected transaction for the returning ID

protected mac_item expected_buckets[int][$];

function void mac_scoreboard::predict(mac_item tr);
  expected_buckets[tr.id].push_back(tr);
endfunction

function void mac_scoreboard::write(mac_item act);
  mac_item exp;

  if (!expected_buckets.exists(act.id) ||
      expected_buckets[act.id].size() == 0) begin
    uvm_report_error("SCB_OOO", "Unexpected response ID");
    return;
  end

  exp = expected_buckets[act.id].pop_front();
  if (!act.compare(exp))
    uvm_report_error("SCB_MISMATCH", "Data mismatch for response ID");
endfunction

Across-ID order no longer matters. Each actual response selects and advances only its own ordered expected stream.

Legal interleaving, checkpoint 1: Keep separate expectation queues.. Inspect the contract.

Understand the failure

ID-aware reconstructionArrival order may change; the legal ordering domain may not.

Per-ID expected queues absorb cross-ID reordering, while a separate memory model checks when writes become visible to reads at the architecture’s chosen observation point.

ID 0W0W1expect W0 → W1ID 3R0R1expect R0 → R1ObservedR0W0R1W1cross-ID interleave is legal

Accepted writeaddress A = 0x2AVisibility pointmemory model commits ALater readexpected A = 0x2A

compare within protocol ordering scope · never impose a global FIFO unless the architecture requires one

ID-aware response reconstruction

Protocol order is checked per ID, while shadow memory and dependency edges enforce address visibility across IDs.

Request collector: Captures ID, address, Thread_ID, Global_Order, and accept time.
pending_addrs[id]: Preserves the ordered request-address stream for each ID.
Response collector: Captures ID, data, and completion time.
expected_buckets[id]: Predictor-owned expected FIFO for each independently ordered ID.
Per-ID comparison: Pops only the bucket selected by the actual returning ID.
Shadow memory: Stores candidate visible values and pending writes by address inside the architectural outcome model.
Consistency policy: Defines preserved order, reads-from, coherence order, fences, dependencies, and the legal outcome set.

Request collector -> pending_addrs[id]
pending_addrs[id] + Response collector -> Reconstructed actual transaction
Reconstructed actual transaction + expected_buckets[id] -> Per-ID comparison
Writes -> Shadow memory
Reads -> Shadow memory -> Per-ID comparison
Consistency policy -> Shadow memory

Why it matters

High-performance fabrics such as AXI can legally complete transactions out of order.
A testbench that ignores memory-consistency rules can miss a stale read caused by a buffered or delayed write.
Correct data is not enough. Responses must obey per-ID protocol order and the architecture's selected global-visibility rules.

What is difficult

Different transaction IDs may pass one another while transactions sharing an ID must remain ordered.
Request metadata and response data often travel on independent channels and must be reconstructed by ID.
A FIFO scoreboard reports false mismatches as soon as a legal later-ID response arrives first.
Address dependencies can cross transaction IDs, so per-ID queues alone cannot prove read-after-write behavior.
Transport ordering and architectural memory consistency are different contracts. TSO and relaxed models require explicit preserved-order, reads-from, coherence-order, fence, and dependency rules rather than a looser FIFO.

Failure signatures

A same-ID response returns in the wrong order.
A response arrives for an ID with no pending request.
A legal across-ID reorder causes a false FIFO-scoreboard failure.
A read observes stale data before a previous write to the same address becomes globally visible.
A posted write is treated as visible when only its protocol response, not its memory acknowledgement, has completed.
The scoreboard applies TSO rules to a relaxed configuration or vice versa.

Compare approaches

Two viable approaches—and their cost

ID-indexed multi-queue

Maintain one expected FIFO for each transaction ID and compare within the ID that actually returned.

Strengths

Simple implementation for protocols that guarantee in-order completion within an ID.
Naturally accepts legal interleaving across different IDs.

Costs

Does not model address dependencies across IDs.
Cannot by itself prove read-after-write visibility or a global memory model.

Shadow memory and dependency graph

Track the current visible value of every address plus explicit predecessor relationships.

Strengths

Detects deep cross-ID consistency violations.
Can represent CPU-visible global ordering and posted-write state.

Costs

Computationally more expensive than per-ID queues.
Requires a precise definition of completion, visibility, and the active memory model.

Explain it in an interview

Interview answer, built from the mechanism

First separate transport order from architectural memory consistency. Use an ID-tagged transport scoreboard with one expected queue per protocol ordering domain, such as ID, channel, and destination, rather than one global FIFO.
Run request and response collectors independently. Store pending request addresses by ID, then attach the oldest same-ID address when a response returns.
For memory consistency, add an architectural outcome model that records writes, reads-from choices, coherence order, preserved program order, fences, and dependencies. Shadow memory is one value store inside that model, not the complete policy.
Represent posted writes as pending until the architecture's visibility event, then validate each observed read against the set of outcomes allowed by the selected TSO or relaxed contract.

Assign responsibilities

Component responsibility contract

Component responsibilities and required verification changes for Out-of-Order Ordering and Memory Consistency
Component	Responsibility	Required change
Transaction	Tracking tags	Carry ID, Thread_ID, and Global_Order metadata.
Monitor	Ordering metadata	Capture request acceptance and response completion times.
Scoreboard	Reordering logic	Use an associative array of expected queues indexed by ID.
Reference model	Global visibility	Track values plus reads-from, coherence order, preserved program order, fences, dependencies, and pending visibility events.
Global config	Memory-model policy	Select the explicit TSO or relaxed allowed-outcome rules, not a generic strictness level.

Build the checker

Implementation patterns

Reconstruct responses with pending addresses by IDsystemverilog

protected logic [31:0] pending_addrs[int][$];
uvm_analysis_port #(mac_item) ap;

task mac_monitor::run_phase(uvm_phase phase);
  fork
    collect_requests();
    collect_responses();
  join
endtask

task mac_monitor::collect_requests();
  forever begin
    @(posedge vif.clk);
    if (vif.req_valid && vif.req_ready)
      pending_addrs[vif.req_id].push_back(vif.req_addr);
  end
endtask

task mac_monitor::collect_responses();
  forever begin
    @(posedge vif.clk);
    if (vif.rsp_valid && vif.rsp_ready) begin
      mac_item tr = mac_item::type_id::create("tr");
      tr.id   = vif.rsp_id;
      tr.data = vif.rsp_data;

      if (pending_addrs.exists(tr.id) && pending_addrs[tr.id].size() > 0)
        tr.addr = pending_addrs[tr.id].pop_front();
      else
        uvm_report_error("MON_PROTOCOL", "Response arrived without a request");

      ap.write(tr);
    end
  end
endtask

Two collectors follow independent request and response channels. The response is joined to the oldest pending address for its own ID before publication.

Compare the oldest expected transaction for the returning IDsystemverilog

protected mac_item expected_buckets[int][$];

function void mac_scoreboard::predict(mac_item tr);
  expected_buckets[tr.id].push_back(tr);
endfunction

function void mac_scoreboard::write(mac_item act);
  mac_item exp;

  if (!expected_buckets.exists(act.id) ||
      expected_buckets[act.id].size() == 0) begin
    uvm_report_error("SCB_OOO", "Unexpected response ID");
    return;
  end

  exp = expected_buckets[act.id].pop_front();
  if (!act.compare(exp))
    uvm_report_error("SCB_MISMATCH", "Data mismatch for response ID");
endfunction

Across-ID order no longer matters. Each actual response selects and advances only its own ordered expected stream.

Delay reads behind a posted writetext

on_write_response(address):
  shadow[address].pending_write = true

on_memory_ack(address, value):
  shadow[address].value = value
  shadow[address].pending_write = false

on_read_complete(address, value):
  wait until shadow[address].pending_write == false
  compare value with shadow[address].value

A protocol response and global visibility are separate events. The reference model does not validate a dependent read until memory acknowledgement clears the pending-write state.

Stress the design

Stress recipe

Issue multiple requests on each of several IDs and randomize response latency independently by ID.
Force the earliest request to have the longest latency so later IDs must pass it.
Attempt same-ID reordering and require the checker to reject it.
Post a write, return its protocol response, then issue a read to the same address before memory acknowledgement.
Run litmus-style traces under the explicit TSO and relaxed policies and confirm only outcomes permitted by each architecture pass.

Follow-up questions

How do you handle write posting when a response arrives before data reaches memory?

Set a pending-write flag in shadow memory. Delay checking a read to that address until a memory acknowledgement clears the flag and publishes the new visible value.

How do you stress the reordering logic?

Send many IDs concurrently and make the first transaction unusually slow so later IDs complete ahead of it. Then verify legal across-ID passing and strict same-ID order.

What if the DUT supports TSO and relaxed memory models?

Select a formalized allowed-outcome policy for the active architecture. Model preserved program order, reads-from, coherence order, dependencies, and fences for that policy; do not approximate the difference by simply making a FIFO checker more or less strict.

Engineering qualifications

Engineering note

For AXI specifically, the same-ID rule is scoped by channel and destination; the protocol does not generally order reads against writes, different IDs, different masters, or different destinations. The scoreboard must encode the interface's actual ordering domain.

Per-ID queues prove transport-response ordering. They do not prove TSO or a relaxed memory model; architectural consistency needs a separate allowed-outcome model over reads-from, coherence order, dependencies, and fences.

The statement that a read must wait for all previous writes to the same address is conditioned on the selected architecture and visibility point. The page must not present one policy as universal.

The source table calls the buckets expected_q[id], while the code calls them expected_buckets[id]. The native model uses one consistent name.

Thread_ID, Global_Order, accept time, and completion time are required metadata in the source table but are not consumed by its short code sample. They remain explicit responsibilities for deeper checks.

The shown multi-queue implementation assumes in-order completion within each ID.