CHI Ordering Rules

Module 12 · Chapter 12.6 · Ordering and Consistency

Project thread — 12.1–12.5 built the ordering concepts and barriers. This chapter catalogues the spec's ordering rules. 12.7 places CHI in the consistency-model landscape.

1. Learning Outcomes

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

• List the categories of CHI ordering rules — per-address, ordered streams, device, barrier.
• Distinguish ordered request streams (kept in order) from unordered ones (may reorder).
• State that device-type memory is more strongly ordered than normal memory.
• Apply the reading discipline — rely only on the ordering the rules grant.
• Diagnose the bug of assuming an unordered stream is ordered.
• Implement a representative ordering-rule model in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

The barriers of the last chapters are tools; the ordering rules are the contract that says when you need them. CHI's ordering guarantees are not a single blanket statement — they are a catalogue of specific rules, each granting a particular ordering under particular conditions. Some ordering is free (same address), some is opt-in per stream (ordered requests), some depends on the memory type (device regions), and some requires a barrier (normal-memory cross-address). To reason about ordering correctly, you must read the catalogue, not guess.

The discipline is precise and consequential. Every ordering your code relies on must be granted by a rule; if it is not, the interconnect is free to reorder, and your assumption becomes an intermittent bug. The most common trap is treating an unordered request stream as if it kept program order — a natural but unfounded assumption. This chapter is the reference for what CHI actually promises about order, so you rely on grants, not hopes.

3. Key Terms

4. Previous Chapter Connection

Chapters 12.1–12.5 built the ordering concepts: per-address versus cross-address (12.1), how the home serializes (12.2), and the barriers (12.3–12.5). Those were the mechanisms; this chapter is the specification's catalogue of the guarantees they add up to.

Like the "read the spec" chapters for state tables (10.6) and the directory model (11.6), 12.6 is about reading CHI's ordering rules precisely rather than assuming. It collects the guarantees — per-address ordering, ordered versus unordered request streams, device-type ordering, barrier-enforced cross-address order, completion order — into one reference, and imposes the discipline every spec demands: rely only on what is granted. The barriers of 12.3–12.5 are the tools the rules point you to when the ordering you need is not free.

5. Core Concept — a catalogue of granted orderings

CHI's ordering is a set of specific rules, each granting an order under conditions; anything not granted is not guaranteed.

• Per-address: always ordered. Accesses to the same address are ordered by coherence — the free, universal guarantee (Chapters 12.1, 12.2).
• Ordered versus unordered streams. CHI marks request streams: an ordered stream's requests (from a source to an endpoint) are kept in issued order; an unordered stream's may be reordered by the interconnect for performance.
• Device memory: stronger order. Device-type regions carry stronger ordering than normal memory — accesses to them are not freely reordered, because device side effects depend on order.
• Barrier-enforced cross-address. For normal memory across different addresses, ordering is not free — it must be requested with a barrier (Chapters 12.3–12.5).
• The discipline. Rely only on an ordering a rule grants. An unstated ordering — an unordered stream assumed ordered, a normal cross-address pair assumed ordered — is not guaranteed.

The synthesis:

CHI's ordering is a catalogue of specific grants: per-address ordering is always given (coherence); ordered request streams keep issued order while unordered ones may reorder; device memory is more strongly ordered than normal memory; and cross-address normal-memory ordering must be requested with a barrier. The reading discipline: rely only on what a rule grants — an ordering the catalogue does not promise is one the interconnect may break.

6. Engineering Mental Model — a shipping contract's fine print

CHI's ordering rules are the fine print of a shipping contract.

• The contract does not say "everything arrives in the order you sent it." It says specific things: "items to the same destination arrive in order"; "priority shipments keep their order"; "standard shipments may be re-sequenced for efficiency"; "hazardous goods are handled in strict order."
• A shipper who reads only the headline — "we deliver your goods" — and assumes standard shipments stay in order will be surprised when two of them arrive swapped. The contract permitted it.
• The careful shipper reads the clauses and relies only on what each grants: uses priority (ordered) shipping where order matters, or adds an explicit sequencing instruction (a barrier), and never assumes an ordering the contract did not promise.

Read the clauses, rely on the grants. Assuming an ordering the contract does not state is how goods arrive out of sequence and no one is liable.

7. Engineering Diagram — the ordering-rule categories

Read each box as a grant: per-address (always), ordered stream (kept), device (strong), barrier (on request). The unordered box is the trap — it grants no order. An access's guaranteed ordering is the union of whichever boxes apply; outside them, nothing is promised.

8. The Ordering Rules

The catalogue, itemized.

The rule to carry: read each access against the catalogue and take only the ordering a rule grants. Same-address and device accesses are ordered; an ordered stream keeps its order; an unordered stream and a normal cross-address pair are not ordered unless a barrier says so. The one to watch is unordered — the default for many request streams — which grants nothing, so relying on its issue order is relying on an ordering the spec does not promise.

9. Ordered versus Unordered Streams

The distinction most easily missed deserves its own statement.

• Ordered streams keep their order. CHI can mark a request stream ordered; its requests, from a given source to a given endpoint, are observed in issued order. This is a real, usable guarantee — for it, no barrier is needed.
• Unordered streams may reorder. By default, request streams may be unordered — the interconnect is free to reorder them for performance (different homes, different paths, Chapter 11.2).
• The marking is the contract. Whether a stream is ordered is a property of the request, not an accident of timing. Rely on order only for a stream actually marked ordered.
• Do not infer order from issue. Two requests issued in sequence on an unordered stream carry no ordering promise between them — the interconnect may swap them.

The point to carry:

"I issued A before B, so A is ordered before B" is the single most common false assumption about a weakly-ordered interconnect, and CHI's ordered/unordered stream distinction is exactly where it fails. Issue order is a property of the sender; observed order is a property of the system, and the system only preserves it when a rule says so — an ordered stream, the same address, a device region, or a barrier. On an unordered stream to normal memory across addresses, none of those apply, so the interconnect may reorder freely. Reading the catalogue is the habit of checking, for every ordering you depend on, which rule grants it — and treating "none" as "reorderable."

10. Reading the Rules — three accesses

Classify three access pairs against the catalogue.

1. Two accesses to the same address. Rule: per-address — ordered. Rely on it (coherence).
2. Two requests on an ordered stream. Rule: ordered stream — kept in issued order. Rely on it.
3. Two requests on an unordered stream, different addresses, no barrier. Rule: none grants order — the interconnect may reorder them. Do not rely on their issue order.
4. Two accesses to a device region. Rule: device memory — strongly ordered. Rely on it.
5. Cross-address normal memory with a DMB between. Rule: barrier — ordered by the DMB. Rely on it.

Items 1, 2, 4, 5 are granted orderings — safe to depend on. Item 3 is not granted — depending on it is the DebugLab. The catalogue tells you which is which; assumption does not.

11. RTL / Hardware View — an ordering-rule model

Whether two accesses are ordered is a lookup against the catalogue: same address, ordered stream, device, or a barrier — else not ordered. Representative.

// Representative CHI ordering-rule model (educational).
// Two accesses are guaranteed ordered if a RULE grants it: same address (coherence),
// an ORDERED request stream, DEVICE memory, or a barrier between them. Otherwise --
// an unordered stream / normal cross-address with no barrier -- NOT ordered.
module chi_order_rules (
  input  logic same_address,    // same-address (coherence)
  input  logic ordered_stream,  // the request stream is marked ordered
  input  logic device_memory,   // device-type region (strongly ordered)
  input  logic barrier_between,  // a barrier separates the accesses
  output logic ordered,         // an ordering rule grants their order
  output logic reorderable       // no rule grants it -> may be reordered
);
  // Ordered if ANY granting rule applies.
  assign ordered     = same_address || ordered_stream || device_memory || barrier_between;
  // Otherwise the interconnect may reorder (e.g. unordered stream, normal cross-address).
  assign reorderable = !ordered;
endmodule

The same behavior in Verilog-2001:

// Representative CHI ordering-rule model (Verilog-2001).
module chi_order_rules (
  input  same_address, ordered_stream, device_memory, barrier_between,
  output ordered, reorderable
);
  assign ordered     = same_address || ordered_stream || device_memory || barrier_between;
  assign reorderable = !ordered;
endmodule

And in VHDL:

-- Representative CHI ordering-rule model (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_order_rules is
  port (
    same_address    : in  std_logic;
    ordered_stream  : in  std_logic;
    device_memory   : in  std_logic;
    barrier_between : in  std_logic;
    ordered         : out std_logic;
    reorderable     : out std_logic
  );
end entity;
 
architecture rtl of chi_order_rules is
  signal ord : std_logic;
begin
  ord <= same_address or ordered_stream or device_memory or barrier_between;
  ordered     <= ord;
  reorderable <= not ord;
end architecture;

All three grant order when any rule applies — same address, ordered stream, device, or barrier — and flag reorderable when none does. The DebugLab is relying on an ordering when reorderable is set.

12. Verification View — order comes only from a rule

The properties that pin the catalogue: order is granted by a rule, and an unordered normal cross-address pair is reorderable.

// Bind to chi_order_rules.
// 1. Any granting rule guarantees order.
property p_rule_grants_order;
  @(*) (same_address || ordered_stream || device_memory || barrier_between) |-> ordered;
endproperty
 
// 2. With no granting rule, the pair is reorderable (NOT ordered).
property p_no_rule_reorderable;
  @(*) (!same_address && !ordered_stream && !device_memory && !barrier_between) |-> reorderable;
endproperty
 
// 3. An unordered-stream normal cross-address pair with no barrier is reorderable.
property p_unordered_cross_reorderable;
  @(*) (!same_address && !ordered_stream && !device_memory && !barrier_between)
       |-> !ordered;
endproperty

The system point, beyond the checks:

An ordering catalogue is a specification technique for making a weak default usable: instead of ordering everything (slow) or nothing (unusable), CHI orders a well-defined set of cases and lets the programmer opt into more. The value is entirely in the precision of the boundary — knowing exactly which accesses are ordered and which are free to move. So reasoning about ordering on CHI is a classification exercise: for each dependency, find the rule that grants it, and if none does, treat the accesses as reorderable and add a barrier or use an ordered stream. The failures come not from the rules being wrong but from not reading them — assuming the strong-ordering intuition of a simpler machine on a system whose whole design is to reorder what it is allowed to.

• What it proves: order comes only from a granting rule; unordered cross-address pairs are reorderable.
• What it does not prove: the specific consistency model built on these rules — that is Chapter 12.7.
• Bug signature: code relying on order for a pair with reorderable set — an ungranted ordering.

13. Testbench — granted versus reorderable

Drives the rule combinations and checks whether order is granted.

module tb_chi_order_rules;
  logic same_address, ordered_stream, device_memory, barrier_between;
  logic ordered, reorderable;
  int errors = 0;
 
  chi_order_rules dut (.*);
 
  task automatic check(input logic sa, os, dm, bb,
                       input logic exp_ord, input string name);
    same_address = sa; ordered_stream = os; device_memory = dm; barrier_between = bb; #1;
    if (ordered !== exp_ord || reorderable !== !exp_ord) begin
      errors++; $display("FAIL %s: ordered=%0b reorderable=%0b", name, ordered, reorderable);
    end else $display("PASS %s: ordered=%0b", name, ordered);
  endtask
 
  initial begin
    check(1'b1, 1'b0, 1'b0, 1'b0, 1'b1, "same address -> ordered (coherence)");
    check(1'b0, 1'b1, 1'b0, 1'b0, 1'b1, "ordered stream -> ordered");
    check(1'b0, 1'b0, 1'b1, 1'b0, 1'b1, "device memory -> ordered");
    check(1'b0, 1'b0, 1'b0, 1'b1, 1'b1, "barrier -> ordered");
    check(1'b0, 1'b0, 1'b0, 1'b0, 1'b0, "unordered stream, normal, no barrier -> REORDERABLE");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS same address -> ordered (coherence): ordered=1
PASS ordered stream -> ordered: ordered=1
PASS device memory -> ordered: ordered=1
PASS barrier -> ordered: ordered=1
PASS unordered stream, normal, no barrier -> REORDERABLE: ordered=0
ALL TESTS PASSED

14. DebugLab — assuming an unordered stream is ordered

requests on an UNORDERED stream, different normal-memory addresses:
  issue: req @A then req @B
  no rule grants order: not same address, stream not ordered,
                        not device, no barrier
interconnect routes @A and @B to different homes/paths -> may reorder
observer sees: @B before @A  -> issue order NOT preserved
code assumed issue order == observed order -> broken

15. Common Mistakes

• Assuming an unordered stream is ordered. Assumption: issue order holds. Bug: reordering (the DebugLab). Prevention: mark it ordered or add a barrier.
• Treating issue order as observed order. Assumption: sent-first means seen-first. Bug: broken ordering. Prevention: observed order comes from a rule.
• Ignoring the ordered/unordered marking. Assumption: all streams are ordered. Bug: reordered requests. Prevention: rely on order only for ordered streams.
• Forgetting device-memory ordering. Assumption: device is like normal memory. Bug: reordered side effects. Prevention: device regions are strongly ordered.
• Assuming cross-address normal order. Assumption: different lines stay ordered. Bug: reordering (Chapter 12.1). Prevention: a barrier for cross-address order.
• Guessing instead of reading. Assumption: intuition suffices. Bug: an ungranted ordering. Prevention: read the catalogue.

16. Engineering Checklist

• For each ordering you depend on, find the rule that grants it.
• Rely on per-address and device-memory ordering where they apply.
• Use an ordered stream where you need requests kept in issued order.
• Treat unordered streams as reorderable — do not assume issue order.
• Add a barrier for cross-address normal-memory ordering.
• Never assume an ordering the catalogue does not grant.

17. Key Takeaways

• CHI's ordering is a catalogue of specific rules — rely only on what a rule grants.
• Per-address accesses are always ordered (coherence); device memory is strongly ordered.
• Ordered request streams keep issued order; unordered streams may be reordered.
• Cross-address normal-memory ordering must be requested with a barrier.
• Assuming an unordered stream is ordered — treating issue order as observed order — is a bug.
• Read the rules; rely on grants; the model here is representative.

18. Quick Revision

CHI ordering rules. CHI's ordering is a catalogue of specific grants, and the discipline is to rely only on what a rule grants. Per-address accesses are always ordered (coherence). Request streams are marked ordered — requests kept in issued order — or unordered — which the interconnect may reorder for performance. Device-type memory is strongly ordered (its side effects depend on order). And cross-address ordering of normal memory is not free — it must be requested with a barrier (DMB/DSB). An access's guaranteed order is the union of whichever rules apply; anything outside them is not guaranteed. The trap is the unordered stream, the default for many requests: issuing A before B on it grants no order between them, because issue order is not observed order — observed order comes only from a rule (same address, ordered stream, device, barrier). Assuming an unordered stream keeps its order is depending on an ordering the spec never promised, and the interconnect reorders freely. Read the catalogue; for each dependency, find the rule; if none, add one. Representative model; 12.7 places CHI in the consistency-model landscape.

Coming Next

Chapter 12.7 — Consistency Models. The ordering rules are the mechanism; the consistency model is the contract software sees. Chapter 12.7 closes the module by placing CHI in the landscape of memory consistency models — sequential consistency, total store order, and weakly-ordered — showing that CHI provides the coherence and ordering primitives for a weakly-ordered model, and why software must program to that model, using barriers, rather than assume a stronger one.