Memory Ordering

Module 12 · Chapter 12.1 · Ordering and Consistency

Project thread — Modules 10–11 gave per-line coherence. This module widens to ordering across lines. 12.1 draws the coherence-versus-consistency line; 12.2 is how the home orders transactions.

1. Learning Outcomes

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

• State that CHI guarantees a single order per address — coherence.
• State that CHI does not, by default, order accesses to different addresses — weak consistency.
• Distinguish coherence (per-line) from consistency (cross-line).
• Explain why cross-address ordering requires a barrier.
• Diagnose the message-passing bug from missing cross-address ordering.
• Implement a representative ordering model in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

This is the chapter where coherence stops being enough. Everything in Modules 10 and 11 guaranteed that accesses to a single line appear in one order — a read returns the latest write to that line. But real software cares about the order between accesses to different lines: write the data, then set the flag; the reader sees the flag, then expects the data. That cross-line order is a different guarantee, and CHI, like most modern systems, does not provide it by default.

The gap between per-address coherence and cross-address ordering is the source of the most notorious multi-core bugs — code that works on a strongly-ordered machine and breaks on a weakly-ordered one, or works in testing and fails under load. Understanding that CHI orders within an address but not across addresses, and that crossing that gap requires an explicit barrier, is the foundation of the entire ordering module and of writing correct concurrent code on CHI-based systems.

3. Key Terms

4. Previous Chapter Connection

Modules 10 and 11 built coherence: the states, the directory, the guarantee that a read returns the latest write to a given line. Every mechanism — snoops, invalidation, the sharer set — enforced order within one address. That is exactly as far as coherence goes.

This chapter names what coherence does not cover: the order between accesses to different addresses. The single-writer-multiple-reader guarantee (Chapter 11.6) is per-line — it says nothing about how one line's accesses interleave with another's. So the coherence you have is a per-address total order, and this module is about the cross-address order layered on top — which CHI leaves weak, to be tightened only by explicit barriers. 12.1 draws that line; the rest of Module 12 works within it.

5. Core Concept — ordered within an address, not across

CHI provides a strong guarantee per address and a weak one across addresses.

• Per address: one total order. All accesses to a single line appear in one consistent order to all agents — the coherence order (Modules 10, 11). A read returns the latest write to that line.
• Across addresses: no default order. Two accesses to different lines may be observed in either order by another agent. A write to A followed by a write to B may be seen, elsewhere, as B-then-A.
• Coherence versus consistency. Coherence is the per-line guarantee (given). Consistency is the cross-line ordering model (weak by default in CHI, as in ARM architectures).
• Barriers tighten it. To force a cross-address order — "the write to A is observed before the write to B" — an agent must issue an explicit barrier (DMB / DSB) between them. Without one, no cross-address order is promised.

The synthesis:

CHI guarantees a single order per address — coherence, free — but no order across addresses by default — weak consistency. Accesses to one line are totally ordered; accesses to different lines may be observed reordered. To enforce a cross-address order, an agent issues a barrier. Coherence is per-line; consistency is cross-line, and cross-line ordering is the programmer's responsibility, not a default.

6. Engineering Mental Model — two independent conveyor belts

Picture each memory address as its own conveyor belt, carrying that address's accesses in order.

• On one belt (one address), items ride in a strict sequence — everyone watching that belt sees the same order. That is coherence: per-belt, per-address ordering, guaranteed.
• Between different belts, there is no synchronization. An item you place on belt A and then an item on belt B may arrive at an observer in either order — the belts run independently at their own speeds.
• If you need "the A item is seen before the B item," you cannot rely on having placed them in that order; you must add a gate that holds B's belt until A's item has passed. That gate is a barrier.

Each belt is ordered; the belts are not ordered relative to each other. Coherence keeps each belt honest; only a barrier ties two belts together.

7. Engineering Diagram — the message-passing reordering

Read the last two messages: the consumer sees the flag set but reads stale data, because the producer's two writes — to different addresses — were not ordered. Each address was coherent on its own; the pair was not. A barrier between the producer's writes would have fixed it.

8. Coherence versus Consistency

The two guarantees, distinguished.

The rule to carry: coherence gives you a total order per address for free; consistency — the order across addresses — is weak by default and must be tightened with barriers. A common confusion is to expect coherence to imply cross-address ordering; it does not. Two lines are each individually coherent while their accesses interleave freely relative to each other, unless a barrier says otherwise.

9. Why Cross-Address Ordering Needs a Barrier

The reason the ordering module exists deserves its own statement.

• Weak order is the default for performance. Not ordering unrelated accesses lets the system pipeline, buffer, and reorder them freely — a large performance win. CHI, like ARM, defaults to weak.
• Most accesses do not need ordering. Independent data structures, unrelated variables — their relative order does not matter, so ordering them by default would be pure waste.
• When order matters, it is explicit. The cases that need cross-address order — synchronization, handoffs, message passing — are marked by the programmer with a barrier, which the hardware honours.
• The barrier is the contract. A barrier says "everything before me is ordered before everything after me." Without it, the hardware is free to reorder — and will, for speed.

The point to carry:

Weak consistency is a deliberate trade: order nothing across addresses by default (fast), and let software declare the few orderings it actually needs (correct). The hardware cannot know which cross-address orders matter — only the programmer does — so the responsibility is delegated, and the barrier is how it is expressed. This is why memory ordering is a programming concern on CHI: coherence is automatic, but cross-address consistency is opt-in, one barrier at a time. A concurrent algorithm is correct on CHI only if every cross-address order it depends on is backed by a barrier.

10. Reading the Order — message passing done right

Fix the message-passing pattern with barriers.

1. Producer writes data. Write data @A.
2. Producer barriers. A DMB ensures the data write at A is observed before anything after it.
3. Producer writes flag. Write flag @B. Because of the barrier, any observer that sees the flag set must also see the data written.
4. Consumer reads flag. Read flag @B → set.
5. Consumer barriers, then reads data. A DMB ensures the flag read is ordered before the data read, so reading the set flag guarantees the subsequent data read sees the new data — not stale.

With the barriers at steps 2 and 5, the cross-address order (data before flag; flag before data-read) is enforced, and the handoff is correct. Remove them and each address is still coherent, but the pair is unordered — the stale read of the DebugLab.

11. RTL / Hardware View — an ordering model

The guarantee reduces to a rule: two accesses are ordered if they are to the same address (coherence) or a barrier separates them. Representative.

// Representative memory-ordering model (educational).
// Two accesses are guaranteed ordered if they target the SAME address (coherence)
// OR a barrier separates them. Accesses to DIFFERENT addresses with no barrier
// are NOT ordered -- they may be observed in either order.
module chi_ordering_model (
  input  logic same_address,     // the two accesses target the same line
  input  logic barrier_between,  // a barrier (DMB/DSB) separates them
  output logic ordered,          // their relative order is guaranteed
  output logic needs_barrier      // cross-address: a barrier is required to order
);
  // Same-address is always ordered (coherence); else a barrier is needed.
  assign ordered       = same_address || barrier_between;
  // Cross-address ordering is only guaranteed via a barrier.
  assign needs_barrier = !same_address && !barrier_between;
endmodule

The same behavior in Verilog-2001:

// Representative memory-ordering model (Verilog-2001).
module chi_ordering_model (
  input  same_address,
  input  barrier_between,
  output ordered,
  output needs_barrier
);
  assign ordered       = same_address || barrier_between;
  assign needs_barrier = !same_address && !barrier_between;
endmodule

And in VHDL:

-- Representative memory-ordering model (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_ordering_model is
  port (
    same_address    : in  std_logic;
    barrier_between : in  std_logic;
    ordered         : out std_logic;
    needs_barrier   : out std_logic
  );
end entity;
 
architecture rtl of chi_ordering_model is
begin
  ordered       <= same_address or barrier_between;
  needs_barrier <= (not same_address) and (not barrier_between);
end architecture;

All three order two accesses when they share an address (coherence) or a barrier separates them, and flag needs_barrier for the cross-address case with no barrier. The DebugLab is exactly that unflagged case shipped as code.

12. Verification View — same-address ordered, cross-address needs a barrier

The properties that capture the guarantee: same-address is ordered, cross-address needs a barrier.

// Bind to chi_ordering_model.
// 1. Same-address accesses are always ordered (coherence).
property p_same_address_ordered;
  @(*) same_address |-> ordered;
endproperty
 
// 2. Cross-address accesses are ordered ONLY if a barrier separates them.
property p_cross_needs_barrier;
  @(*) (!same_address) |-> (ordered == barrier_between);
endproperty
 
// 3. needs_barrier flags an unordered cross-address pair.
property p_needs_barrier_def;
  @(*) needs_barrier == (!same_address && !barrier_between);
endproperty

The system point, beyond the checks:

Coherence and consistency answer different questions, and conflating them is the root of a whole class of concurrency bugs. Coherence answers "for this line, what is the latest value?" — a per-address total order the hardware maintains automatically. Consistency answers "across different lines, in what order do accesses appear?" — and CHI's answer is whatever is fastest, unless you say otherwise. The two are orthogonal: a system can be perfectly coherent (every line individually ordered) yet weakly consistent (lines unordered relative to each other), and CHI is exactly that. So reasoning about a concurrent program on CHI means checking, for every cross-address dependency, that a barrier backs it — because the hardware guarantees the per-line order and nothing more.

• What it proves: same-address is ordered; cross-address ordering requires a barrier.
• What it does not prove: the barrier's specific semantics — that is DMB (12.4) and DSB (12.5).
• Bug signature: code relying on an ordered cross-address pair with no barrier — needs_barrier set.

13. Testbench — same-address versus cross-address

Drives the ordering cases and checks the guarantee.

module tb_chi_ordering_model;
  logic same_address, barrier_between, ordered, needs_barrier;
  int errors = 0;
 
  chi_ordering_model dut (.*);
 
  task automatic check(input logic sa, bb, input logic exp_ord, exp_nb, input string name);
    same_address = sa; barrier_between = bb; #1;
    if (ordered !== exp_ord || needs_barrier !== exp_nb) begin
      errors++; $display("FAIL %s: ordered=%0b nb=%0b", name, ordered, needs_barrier);
    end else $display("PASS %s: ordered=%0b nb=%0b", name, ordered, needs_barrier);
  endtask
 
  initial begin
    check(1'b1, 1'b0, 1'b1, 1'b0, "same address, no barrier -> ordered (coherence)");
    check(1'b0, 1'b1, 1'b1, 1'b0, "cross address, barrier    -> ordered");
    check(1'b0, 1'b0, 1'b0, 1'b1, "cross address, NO barrier -> NOT ordered (needs one)");
    check(1'b1, 1'b1, 1'b1, 1'b0, "same address, barrier     -> ordered");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS same address, no barrier -> ordered (coherence): ordered=1 nb=0
PASS cross address, barrier    -> ordered: ordered=1 nb=0
PASS cross address, NO barrier -> NOT ordered (needs one): ordered=0 nb=1
PASS same address, barrier     -> ordered: ordered=1 nb=0
ALL TESTS PASSED

14. DebugLab — message passing without a barrier

producer:  Write data @A = NEW;  Write flag @B = 1   (no barrier between)
consumer:  Read flag @B -> 1;    Read data @A -> ???  (no barrier between)
CHI orders each ADDRESS but not the PAIR:
  observer may see: flag@B = 1  BEFORE  data@A = NEW committed
  consumer reads flag=1, then data@A = OLD  -> stale handoff

15. Common Mistakes

• Assuming cross-address program order. Assumption: writes are observed in order. Bug: stale handoff (the DebugLab). Prevention: a barrier between cross-address accesses that must be ordered.
• Confusing coherence with consistency. Assumption: coherence orders everything. Bug: cross-line reordering. Prevention: coherence is per-line; consistency is cross-line.
• Barrier on the producer only. Assumption: one side suffices. Bug: the reader still reorders. Prevention: barriers on both producer and consumer.
• Over-barriering. Assumption: barrier everything to be safe. Bug: lost performance. Prevention: barrier only where cross-address order matters.
• Relying on timing. Assumption: the writes are far apart, so ordered. Bug: reordering under load. Prevention: order with a barrier, not timing.
• Testing on a strong machine. Assumption: it works in test. Bug: fails on a weak system. Prevention: reason to the weak model.

16. Engineering Checklist

• Rely on per-address coherence — a single order for one line — for free.
• Do not assume any order across different addresses.
• Insert a barrier wherever a cross-address order matters.
• Barrier both sides of a handoff — producer and consumer.
• Distinguish coherence (per-line, given) from consistency (cross-line, opt-in).
• Reason to the weak model, not to a strong machine or timing.

17. Key Takeaways

• CHI guarantees a single order per address — coherence — for free.
• It does not, by default, order accesses to different addresses — weak consistency.
• Coherence is per-line; consistency is the cross-line ordering model.
• Cross-address ordering must be enforced with an explicit barrier.
• The message-passing pattern (data-then-flag) breaks without barriers — a set flag with stale data.
• Order within an address for free; across addresses with a barrier; the model here is representative.

18. Quick Revision

Memory ordering. CHI provides a single total order per address — that is coherence, given by Modules 10–11: all accesses to one line appear in one consistent order, and a read returns the latest write to that line. It does not, by default, order accesses to different addresses — that is consistency, and CHI (like ARM) is weakly ordered: two writes to two lines, or two reads, may be observed in either order by another agent. The distinction is coherence (per-line, free) versus consistency (cross-line, weak). Weak order is a deliberate performance trade — order nothing unrelated by default — so any cross-address order a program needs must be declared with an explicit barrier (DMB/DSB). The canonical failure is message passing: a producer writes data at A then a flag at B, a consumer reads the flag then the data — but without barriers the two cross-address writes are observed out of order, so the consumer sees a set flag and stale data. Coherence within an address is automatic; cross-address ordering is the programmer's, one barrier at a time. Representative model; 12.2 covers how the home orders in-flight transactions.

Coming Next

Chapter 12.2 — Transaction Ordering. Memory ordering was about how accesses are observed; transaction ordering is about how the home serializes them. Chapter 12.2 covers how CHI orders simultaneous in-flight transactions — how the home establishes a single order for conflicting transactions to the same line so each sees the effect of its predecessor, and how independent transactions to different lines proceed in parallel — the mechanism beneath the per-address order this chapter relied on.