Out-of-Order Ordering and Memory Consistency Verification Case Study

01 · Concurrency and performance

Out-of-Order Ordering and Memory Consistency

Replace FIFO assumptions with ID-aware reconstruction, per-ID expected queues, and a memory model that checks address visibility across interleaved traffic.

Mechanism · failure · evidence · recovery

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

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.

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.

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.

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.

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 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 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.