Ordering Violations

Module 18 · Chapter 18.8 · CHI Debugging

Project thread — 18.7 debugged credit issues. 18.8 debugs ordering violations and closes the module; 19.1 opens interview mastery.

1. Learning Outcomes

By the end of this chapter you should be able to:

• Define an ordering violation — two events observed in a protocol-forbidden order.
• Recognize the symptom — software observing an impossible order (a barrier not holding).
• Read the signature — an inversion (B before A when A must precede B).
• Identify the violated ordering rule and the two events.
• Classify the root cause — unserialized same-address, reordered stream, or dropped barrier.
• Implement a representative ordering-inversion detector in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Ordering violations are the subtlest debugging family because the data can be perfectly correct — the bug is in when events become visible relative to each other. Software relies on ordering guarantees: a barrier orders what precedes it before what follows; same-address accesses appear in program order; a response follows its request. When one of these is violated, a program sees an impossible order — a load returns a value that "should not be visible yet," or a barrier fails to hold — and breaks in ways that look like a software bug but are a hardware ordering failure.

The debug turns on recognizing that ordering is a relationship, not a value. The symptom is an impossible order; the signature is an inversion — two events A and B where B is observed before A even though the protocol requires A to precede B. The diagnosis is to identify which ordering rule was violated (which precedence is required), find the two events, and check the mechanism that should have enforced their order (Module 12). Learning to spot an inversion and map it to the unenforced constraint turns a baffling "impossible" symptom into a specific ordering bug. This chapter closes the debugging module with that skill.

3. Key Terms

4. Previous Chapter Connection

This chapter debugs the ordering and consistency mechanisms of Module 12. The root causes are ones you built: same-address serialization (Chapter 12.2, enforced by the address hazard of Chapter 16.1), ordered streams (Chapter 12.6), and barriers (Chapter 12.3). An ordering violation is when one of these mechanisms fails to enforce a precedence it should.

It is the debug counterpart of the consistency discussion in Chapters 12.6–12.7. There, the point was that CHI provides a weakly-ordered model with specific guarantees (per-address order, barriers); software written to that model relies on those guarantees. Here, the failure is a guarantee not delivered — an inversion the model forbids — and the debug traces it to the mechanism that should have enforced it. It also connects to Chapter 16.1: a same-address ordering violation is often the visible symptom of the directory-race or missing-hazard bug debugged there. Closing the module, this chapter completes the eight failure families — from lost ownership (data) to ordering (consistency) — that account for nearly every CHI coherence bug.

5. Core Concept — find the inversion, map it to the rule

An ordering violation is an inversion — two events observed in a forbidden order; the diagnosis is to identify the required precedence, find the two events, and check the mechanism that should have enforced it.

• Ordering is a relationship. The bug is not a wrong value but a wrong relative order — event B observed before event A when the protocol requires A to precede B.
• The symptom is an impossible order. Software sees something the model forbids: a barrier that does not hold, a load returning a not-yet-visible value, a response before its request.
• The signature is an inversion. On the trace, the later-required event (B) appears before the earlier-required event (A) — an inversion of the required precedence.
• Map the inversion to the rule. Identify which ordering rule requires A before B (same-address, barrier, request-response), then check the mechanism that should have enforced it — the unenforced one is the bug.

The synthesis:

An ordering violation is an inversion — event B observed before A when the protocol requires A to precede B — so software sees an impossible order (a barrier not holding, a not-yet-visible value). The diagnosis identifies the required precedence (which rule demands A before B), finds the two events, and checks the mechanism that should have enforced it — same-address serialization (12.2/16.1), ordered stream (12.6), or barrier (12.3). The unenforced constraint is the bug.

6. Engineering Mental Model — a recipe step done out of order

Think of a recipe where some steps must happen before others — "preheat the oven before you put the dish in."

• The recipe encodes required precedences: A (preheat) must precede B (insert dish). Doing them in order gives the right result.
• An ordering violation is doing B before A — inserting the dish before the oven is hot. The ingredients are all correct (no data bug), but the order was wrong, so the result is ruined.
• The symptom is an impossible-looking outcome: the dish is raw where it should be cooked — a result that "shouldn't happen" if the steps were followed.
• To debug, you do not re-check the ingredients — you check the timeline: which step happened when, and find the pair where a step that must come first actually came second. That inversion — and the missing "wait for the oven" enforcement — is the bug.

The precedence is the ordering rule; the swapped steps are the inversion; the missing "wait" is the unenforced mechanism. You debug the timeline of events, not the data — an inversion of a required precedence is the fingerprint.

7. Engineering Diagram — the ordering inversion

The write A precedes the barrier, which requires A to be ordered before the load B after it — yet B observed the old value, as if it happened before A. That is the inversion. The barrier failed to enforce A before B. The debugger sees B observe a value that A should have already made visible.

8. Waveform Signature

The signature is b_seen rising before a_seen while the required precedence is A before B — the inversion signal flags the window where B was observed but A had not been. A later-required event appearing before its earlier-required predecessor is an ordering violation, and the rule (A before B) names which mechanism failed.

9. Diagnosis Path

The methodical inversion trace.

The rule to carry: the required precedence names the mechanism, and the mechanism names the bug. Once you identify which rule demands A before B — a barrier (12.3), same-address order (12.2), or request-response — you know which mechanism was supposed to enforce it, and the bug is that mechanism failing: a dropped barrier, an unserialized same-address pair (the 16.1 hazard), or a reordered stream (12.6). The inversion is the symptom; the unenforced mechanism is the root cause. This is why ordering debug is a rule-first trace — the rule points straight at the logic to inspect.

10. Tracing an Ordering Violation — a worked trace

A program uses a barrier to publish data — write the data, barrier, set a flag — but a consumer reads the new flag and the old data.

1. Symptom: impossible order. The consumer saw the flag set (after the barrier) but the old data (before the barrier) — an order the barrier should make impossible.
2. The rule. The barrier requires the write (A) before it to be ordered before everything after it — including the consumer's load (B) of the data. So A must precede B.
3. The events. A = the producer's data write; B = the consumer's data load. The barrier sits between the write and the flag set.
4. Inversion. B (the load) observed the old value — as if it happened before A (the write) took effect. B before A: an inversion of the required precedence.
5. Mechanism. The barrier should have ordered A before B (Chapter 12.3), but the trace shows it did not propagate the ordering — the barrier was effectively dropped at some point in the fabric.
6. Root cause and fix. The barrier's ordering was not enforced on the path to the consumer (a Chapter 12.3 bug — a dropped/un-propagated barrier). Enforce the barrier so A is ordered before B; the consumer then sees the new data with the new flag.

The impossible order traced through the inversion to a dropped barrier. The DebugLab formalizes this.

11. Detector View — an ordering-inversion detector

Record that the earlier-required event was seen; flag the later event observed before it. Representative.

// Representative ordering-inversion detector (educational).
// For a required precedence A-before-B, record when A is observed; a VIOLATION is B
// observed while A has NOT yet been seen (an inversion). Bind A/B to the two events of
// the ordering rule (barrier: pre-write vs post-load; same-address: first vs second).
module chi_order_check (
  input  logic clk, rst_n,
  input  logic a_event,       // event A occurred (the one that must be FIRST)
  input  logic b_event,       // event B occurred (the one that must be SECOND)
  output logic a_seen,         // A has been observed
  output logic inversion       // B observed before A -> ordering violation
);
  logic a_seen_q;
  assign a_seen = a_seen_q;
  // Inversion: B happens while A has not yet been seen -> the required order is broken.
  assign inversion = b_event && !a_seen_q;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) a_seen_q <= 1'b0;
    else if (a_event) a_seen_q <= 1'b1;   // remember A was observed
  end
endmodule

The same behavior in Verilog-2001:

// Representative ordering-inversion detector (Verilog-2001).
module chi_order_check (
  input  clk, rst_n, a_event, b_event,
  output a_seen,
  output inversion
);
  reg a_seen_q;
  assign a_seen    = a_seen_q;
  assign inversion = b_event & ~a_seen_q;   // B before A -> violation
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) a_seen_q <= 1'b0;
    else if (a_event) a_seen_q <= 1'b1;
  end
endmodule

And in VHDL:

-- Representative ordering-inversion detector (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_order_check is
  port (
    clk, rst_n : in  std_logic;
    a_event    : in  std_logic;
    b_event    : in  std_logic;
    a_seen     : out std_logic;
    inversion  : out std_logic
  );
end entity;
 
architecture rtl of chi_order_check is
  signal a_seen_q : std_logic := '0';
begin
  a_seen    <= a_seen_q;
  inversion <= '1' when (b_event = '1' and a_seen_q = '0') else '0';  -- B before A
 
  process (clk, rst_n)
  begin
    if rst_n = '0' then
      a_seen_q <= '0';
    elsif rising_edge(clk) then
      if a_event = '1' then a_seen_q <= '1'; end if;   -- remember A seen
    end if;
  end process;
end architecture;

All three raise inversion when B occurs while A has not yet been seen — the forbidden order, directly. Bind A and B to the two events of the violated rule, and it fires at the inversion. The DebugLab binds A to the producer's write and B to the consumer's load across a barrier.

12. Assertion View — the required precedence holds

The properties formalize the rule: A is observed before B.

// Bind to chi_order_check.
// 1. B is never observed before A (the required precedence holds).
property p_a_before_b;
  @(posedge clk) disable iff (!rst_n)
    b_event |-> a_seen;
endproperty
 
// 2. An inversion is flagged exactly when B occurs before A is seen.
property p_inversion_iff_early_b;
  @(posedge clk) disable iff (!rst_n)
    inversion == (b_event && !a_seen);
endproperty
 
// 3. Once A is seen, it stays seen (the precedence is monotone).
property p_a_seen_sticky;
  @(posedge clk) disable iff (!rst_n)
    a_seen |=> a_seen;
endproperty

The system point, beyond the checks:

Ordering violations close the module on a fitting note, because they are the family where the failure is purely relational — no value is wrong, no state is corrupt, no resource is lost; only the relationship between two events is forbidden. This makes them a distinct mode of debugging: you cannot find an ordering bug by examining any single signal, event, or transaction, because each one is individually legal — a write is a legal write, a load is a legal load; only their relative order is wrong. The detector must therefore watch a pair of events and their timing, and the assertion is a temporal precedence (b |-> a_seen), not a value check. This is the ordering counterpart of Chapter 17.2's compositional lesson: just as coherence lives in the relationship between caches, ordering lives in the relationship between events, and both need a checker positioned to see the relationship, not the parts. Stepping back over the eight families, a pattern emerges: each failure lives at a different level — a value (corruption), a state (bad transition), a resource (credit leak, lost ownership), a dependency (deadlock), or a relationship (coherence, ordering) — and effective debugging is recognizing the level from the symptom, then choosing the tool that observes at that level. Ordering is the relational level, diagnosed by watching event pairs for inversions of a required precedence.

• What it proves: B is never observed before A (the required precedence holds).
• What it does not prove: the data values are correct — that is data corruption (Chapter 18.4).
• Bug signature: inversion asserted — B observed while A has not been seen.

13. Testbench — an inversion must be flagged

Presents B before A (an inversion) and checks the detector fires, then the correct order.

module tb_chi_order_check;
  logic clk = 0, rst_n = 0, a_event, b_event;
  logic a_seen, inversion;
  int errors = 0;
 
  chi_order_check dut (.*);
  always #5 clk = ~clk;
 
  initial begin
    a_event = 0; b_event = 0;
    @(posedge clk) rst_n = 1;
 
    // INVERSION: B occurs while A has NOT been seen -> violation.
    @(posedge clk) b_event = 1;   // B first (forbidden: A must precede B)
    #1;
    if (!inversion) begin errors++; $display("FAIL inversion (B before A) NOT flagged"); end
    else $display("PASS inversion detected: B observed before A");
    @(posedge clk) b_event = 0;
 
    // Reset the check and present the CORRECT order: A then B.
    @(posedge clk) rst_n = 0;
    @(posedge clk) rst_n = 1;
    @(posedge clk) a_event = 1;   // A first
    @(posedge clk) a_event = 0;
    #1;
    if (!a_seen) begin errors++; $display("FAIL A not recorded as seen"); end
    // Now B after A -> no inversion.
    @(posedge clk) b_event = 1;
    #1;
    if (inversion) begin errors++; $display("FAIL false inversion when A preceded B"); end
    else $display("PASS correct order (A then B): no inversion");
    @(posedge clk) b_event = 0;
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS inversion detected: B observed before A
PASS correct order (A then B): no inversion
ALL TESTS PASSED

14. DebugLab — a barrier that did not order a preceding write

producer: write X = new (A);  barrier;  set flag (published after barrier)
consumer: sees flag set  -> should be guaranteed to see X = new
  -> but reads X = OLD  (as if the load happened BEFORE the write A took effect)
required precedence: A (write X) must be ordered BEFORE B (consumer load X)  [barrier]
observed: B saw OLD -> B ordered before A -> INVERSION
mechanism check: barrier ordering NOT propagated on the path to the consumer (12.3)
correct: barrier orders A before B -> consumer sees flag set AND X = new

15. Common Mistakes

• Debugging the data. Assumption: a wrong value. Bug: the data is fine, the order is wrong. Prevention: check the event order, not the value.
• Not identifying the rule. Assumption: any order is fine. Bug: the required precedence is missed. Prevention: name the rule (A before B).
• Blaming software. Assumption: a program race. Bug: a hardware ordering failure. Prevention: reproduce with correct software.
• Ignoring the barrier path. Assumption: a barrier orders everywhere. Bug: not propagated on one path. Prevention: check every path.
• Confusing with same-address. Assumption: one ordering rule. Bug: different mechanisms. Prevention: barrier vs same-address vs stream.
• Checking one event. Assumption: a single signal shows it. Bug: ordering is relational. Prevention: watch the event pair.

16. Engineering Checklist

• On an impossible order, identify the required precedence (which rule).
• Find the two events A (first) and B (second).
• Confirm the inversion — B observed before A.
• Check the mechanism that should have enforced A-before-B.
• Classify — barrier (12.3), same-address (12.2/16.1), or ordered stream (12.6).
• Bind an inversion detector to the event pair and confirm it stays low.

17. Key Takeaways

• An ordering violation is an inversion — B observed before A when A must precede B.
• The data can be correct; the bug is the relative order of events.
• The symptom is an impossible order — a barrier not holding.
• Identify the required precedence, find the events, check the mechanism.
• Root causes: unserialized same-address (12.2/16.1), reordered stream (12.6), dropped barrier (12.3).
• Ordering is relational — watch event pairs; the model here is representative.

18. Quick Revision

Ordering violations. An ordering violation is an inversion — two events observed in a protocol-forbidden order: B observed before A when the protocol requires A to precede B. Unlike every prior family, the data may be perfectly correct — the bug is the relationship between events, so each event is individually legal and only their relative order is wrong. The symptom is software observing an impossible order: a barrier that does not hold, a load returning a not-yet-visible value, a response before its request. The signature is the inversion on the trace — the later-required event appearing before its earlier-required predecessor. The diagnosis is rule-first: identify which ordering rule demands A before B — a barrier (Chapter 12.3), same-address order (Chapter 12.2, enforced by the Chapter 16.1 hazard), or request-response — then find the two events, confirm the inversion, and check the mechanism that should have enforced it. The unenforced mechanism is the root cause: a dropped/un-propagated barrier, an unserialized same-address pair, or a reordered ordered stream (Chapter 12.6). The detector watches the event pair and flags B before A. Ordering is the relational level of failure — diagnosed by watching event pairs, not single signals — completing the eight families that account for nearly every CHI coherence bug. Representative model; this closes Module 18.

Coming Next

Chapter 19.1 — What Is CHI? Modules 6–18 built CHI from coherence foundations through RTL, verification, and debugging; Module 19 turns to communicating that mastery. Chapter 19.1 opens CHI Interview Mastery at the beginner tier — introducing CHI in ninety seconds — the crisp, high-level answer that frames CHI as a scalable, packet-based, directory-coherent interconnect, the foundation every deeper interview question builds on.