Transaction Ordering

Module 12 · Chapter 12.2 · Ordering and Consistency

Project thread — 12.1 gave the per-address order guarantee. This chapter shows how the home produces it by serializing conflicts. 12.3 opens barriers.

1. Learning Outcomes

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

• Explain how the home serializes conflicting transactions to the same line into one order.
• State that each conflicting transaction observes the state its predecessor left.
• Distinguish conflicting transactions (same line, serialized) from independent ones (parallel).
• Connect this serialization to the per-address order of Chapter 12.1.
• Diagnose the order inversion when conflicting transactions run concurrently.
• Implement a representative transaction serializer in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Chapter 12.1 said accesses to one line appear in a single order. This chapter is how — and the how matters, because it is where concurrency meets coherence. When two cores race for the same line, the home must decide who goes first, make the second see the first's result, and never let them blur together. That decision, made per line, is what turns a chaos of simultaneous requests into the clean per-address order software relies on.

The mechanism is serialization at the home, and its failure is subtle and severe. If conflicting transactions to one line are allowed to overlap, they interleave — one reads or acts on a line the other has half-changed — and the coherence order becomes ambiguous. This is the engine behind lost updates and torn reads under contention. Understanding transaction ordering is understanding how a coherent system stays coherent when many agents hit the same line at once — and how it fails when the serialization slips.

3. Key Terms

4. Previous Chapter Connection

Chapter 12.1 established the guarantee: accesses to one address appear in a single order. Chapter 7.6 showed the home as the point of serialization holding a line's ordering until CompAck. This chapter combines them: it is how the home produces the per-address order when many transactions arrive for one line at once.

Where 7.6 tracked one transaction's ordering hold, 12.2 is about several conflicting transactions and the total order the home imposes across them — first this one, then that one, each seeing the last's effect. Independent transactions (different lines, possibly different homes, Chapter 11.2) do not conflict and run in parallel. So the per-address order of 12.1 is not free-standing; it is manufactured by this serialization, and the cross-address freedom of 12.1 is the parallelism of independent transactions.

5. Core Concept — serialize conflicts, parallelize the rest

The home imposes a total order on transactions that conflict (same line) and lets independent ones run in parallel.

• Conflicts serialize. Two transactions to the same line cannot run together — the home orders them: transaction 1, then 2, then 3. Each takes effect in that order.
• Each sees its predecessor. A conflicting transaction observes the line as its predecessor left it — the home does not start the next until the previous has committed its effect (held to CompAck, Chapter 7.6). So the order is not just an ordering of starts but of effects.
• Independent transactions parallelize. Transactions to different lines cannot conflict, so the home runs them concurrently — different lines, often different homes (Chapter 11.2), full parallelism.
• This produces the per-address order. The single order the home imposes on a line's conflicting transactions is the coherence order of Chapter 12.1. Per-address ordering is the output of this serialization.

The synthesis:

The home serializes conflicting transactions to one line into a single total order, and each observes the state its predecessor left — the home holds each transaction's ordering until it commits before starting the next. Independent transactions to different lines run in parallel. This serialization is what produces the per-address coherence order of Chapter 12.1. Conflicts one at a time; independents at once.

6. Engineering Mental Model — a single-lane bridge per road

Each memory line is a single-lane bridge; each road (different line) has its own.

• On one bridge, cars cross one at a time, in an order the toll booth (the home) sets. Car 2 crosses only after car 1 is fully across — it sees the bridge as car 1 left it. That is serializing conflicts.
• The toll booth never lets two cars onto the same bridge at once; that would be a collision — the order would be undefined, the cars entangled. So it holds car 2 until car 1 clears.
• Different bridges (different lines) operate independently — cars cross them in parallel, no coordination needed, because they cannot collide.

One bridge, one car at a time, in a set order; many bridges, all busy at once. The toll booth per bridge is the home per line — serializing its own bridge's traffic while every other bridge flows freely.

7. Engineering Diagram — serializing two conflicting transactions

Read the order: RN0's ReadUnique completes (it becomes the owner) before the home starts RN1's — so RN1's transaction sees RN0 as the current owner and snoops it. The home held RN1 behind RN0. Overlap them and RN1 would act on the line before RN0 finished — the DebugLab.

8. Conflicting versus Independent Transactions

The two cases the home handles differently.

The rule to carry: the home serializes transactions that conflict and parallelizes those that do not. Conflict is defined by the line — same line, serialize; different line, independent. Serialization is what makes a line's accesses appear in one order; independence is what lets the system scale across lines. The two together are exactly the per-address order and cross-address freedom of Chapter 12.1.

9. Each Transaction Sees Its Predecessor

The property that makes the order meaningful deserves its own statement.

• Order of effects, not just starts. Serialization is only useful if a transaction sees the result of the one before it — an order of committed effects, not merely of issue.
• So the home holds each until it commits. The home does not begin the next conflicting transaction until the previous has committed its effect (to CompAck, Chapter 7.6). The predecessor's ownership and data are settled before the successor observes them.
• The successor snoops the new owner. After RN0's ReadUnique, RN0 owns the line; RN1's transaction, ordered next, snoops RN0 — the successor acts on the predecessor's outcome.
• This chains a consistent history. Transaction N sees the state left by N−1, which saw N−2, and so on — a single, consistent per-line history.

The point to carry:

Transaction ordering is not just picking a sequence; it is ensuring each transaction observes the settled result of the one before it. A total order of starts would be meaningless if the effects overlapped — the second transaction might read the line mid-change. The home therefore serializes effects: it commits one conflicting transaction fully before the next observes the line, so each successor builds on a definite predecessor. That chaining is what turns a set of racing requests into the single, coherent per-line history that Chapter 12.1's guarantee describes.

10. Reading the Order — two racers for one line

RN0 and RN1 both ReadUnique line L (initially owned by memory).

1. Both request. RN0 and RN1 send ReadUnique for L — a conflict. The home must order them.
2. Home orders RN0 first. The home picks RN0 as first (by arrival, arbitration — its choice), and holds RN1.
3. RN0 completes. RN0's transaction runs to completion: it becomes the owner (UD), and sends CompAck. Its effect is committed.
4. Home starts RN1. Only now does the home begin RN1's transaction. RN1's snoop targets RN0 — the current owner — invalidating it and taking the line.
5. RN1 completes. RN1 becomes the owner; the line's history is RN0 then RN1, each seeing the last.

The line ended up owned by RN1, having passed through RN0 — a single, ordered history. Had the home started RN1 at step 2 (concurrently with RN0), RN1 might have snooped memory (not RN0) and both could believe they owned the line — the DebugLab.

11. RTL / Hardware View — a transaction serializer

The home's core ordering logic per line: at most one conflicting transaction active; the next starts only after the previous commits. Independent lines are unaffected. Representative.

// Representative per-line transaction serializer (educational).
// Conflicting transactions (same line) run ONE AT A TIME: a new one must WAIT
// while a prior conflicting transaction is still active, and starts only after it
// commits. Independent transactions (different lines) do not conflict -> parallel.
module chi_txn_order (
  input  logic new_req,        // a new transaction wants to start
  input  logic same_line,      // it targets the same line as an active transaction
  input  logic prev_active,    // a conflicting transaction is still in flight
  input  logic prev_committed, // the prior conflicting transaction has committed
  output logic conflict,       // this is a same-line conflict
  output logic must_wait,      // it must be held until the prior commits
  output logic can_start        // it may start now
);
  // A conflict exists when a new same-line request meets an active one.
  assign conflict  = new_req && same_line && prev_active;
  // It must wait until the prior conflicting transaction commits.
  assign must_wait = conflict && !prev_committed;
  // It may start if it does not conflict, or the prior has committed.
  assign can_start = new_req && !must_wait;
endmodule

The same behavior in Verilog-2001:

// Representative per-line transaction serializer (Verilog-2001).
module chi_txn_order (
  input  new_req, same_line, prev_active, prev_committed,
  output conflict, must_wait, can_start
);
  assign conflict  = new_req && same_line && prev_active;
  assign must_wait = conflict && !prev_committed;
  assign can_start = new_req && !must_wait;
endmodule

And in VHDL:

-- Representative per-line transaction serializer (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_txn_order is
  port (
    new_req        : in  std_logic;
    same_line      : in  std_logic;
    prev_active    : in  std_logic;
    prev_committed : in  std_logic;
    conflict       : out std_logic;
    must_wait      : out std_logic;
    can_start      : out std_logic
  );
end entity;
 
architecture rtl of chi_txn_order is
  signal cf, mw : std_logic;
begin
  cf <= new_req and same_line and prev_active;
  mw <= cf and (not prev_committed);
  conflict  <= cf;
  must_wait <= mw;
  can_start <= new_req and (not mw);
end architecture;

All three hold a conflicting same-line transaction (must_wait) until the prior commits, and let a non-conflicting (independent-line) transaction can_start immediately. The DebugLab shows the inversion when the wait is skipped.

12. Verification View — conflicts wait, independents proceed

The properties that keep serialization sound: a conflict waits for its predecessor, an independent transaction does not.

// Bind to chi_txn_order.
// 1. A same-line conflict with an uncommitted predecessor must wait.
property p_conflict_waits;
  @(*) (new_req && same_line && prev_active && !prev_committed) |-> must_wait;
endproperty
 
// 2. A conflict may start only once the predecessor has committed.
property p_start_after_commit;
  @(*) (new_req && same_line && prev_active) |-> (can_start == prev_committed);
endproperty
 
// 3. An independent (different-line) transaction is never blocked as a conflict.
property p_independent_parallel;
  @(*) (new_req && !same_line) |-> (can_start && !must_wait);
endproperty

The system point, beyond the checks:

The home's serialization is where correctness and throughput are traded per line, not globally. It must be strict within a line — one conflicting transaction at a time, each after the last commits — because that strictness is the per-address coherence order. But it must be permissive across lines — every independent transaction in parallel — because that permissiveness is the system's scalability. A design that serialized too much (blocking independent lines) would throw away parallelism; one that serialized too little (overlapping conflicts) would throw away coherence. The art is that the two decisions are made on the same axis — do these conflict? — so a single, correct notion of conflict (same line) simultaneously delivers the ordering coherence needs and the parallelism scale needs.

• What it proves: conflicts wait for their predecessor; independents proceed in parallel.
• What it does not prove: the arbitration order among conflicts — the home is free to choose (fairness aside).
• Bug signature: a same-line conflict starting with an uncommitted predecessor — overlapping conflicts.

13. Testbench — conflicts serialize, independents parallel

Drives conflicting and independent transactions and checks the wait/start decision.

module tb_chi_txn_order;
  logic new_req, same_line, prev_active, prev_committed;
  logic conflict, must_wait, can_start;
  int errors = 0;
 
  chi_txn_order dut (.*);
 
  task automatic check(input logic nr, sl, pa, pc,
                       input logic exp_wait, exp_start, input string name);
    new_req = nr; same_line = sl; prev_active = pa; prev_committed = pc; #1;
    if (must_wait !== exp_wait || can_start !== exp_start) begin
      errors++; $display("FAIL %s: wait=%0b start=%0b", name, must_wait, can_start);
    end else $display("PASS %s: wait=%0b start=%0b", name, must_wait, can_start);
  endtask
 
  initial begin
    check(1'b1, 1'b1, 1'b1, 1'b0, 1'b1, 1'b0, "same line, prior active+uncommitted -> WAIT");
    check(1'b1, 1'b1, 1'b1, 1'b1, 1'b0, 1'b1, "same line, prior committed -> start");
    check(1'b1, 1'b0, 1'b1, 1'b0, 1'b0, 1'b1, "different line -> parallel (start)");
    check(1'b1, 1'b1, 1'b0, 1'b0, 1'b0, 1'b1, "same line, no prior active -> start");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS same line, prior active+uncommitted -> WAIT: wait=1 start=0
PASS same line, prior committed -> start: wait=0 start=1
PASS different line -> parallel (start): wait=0 start=1
PASS same line, no prior active -> start: wait=0 start=1
ALL TESTS PASSED

14. DebugLab — conflicting transactions run concurrently

RN0 ReadUnique L and RN1 ReadUnique L arrive together (conflict)
home starts BOTH concurrently (not serialized)
  RN0's transaction: snoops memory, becoming owner...
  RN1's transaction: ALSO snoops memory (RN0 not yet committed)
  -> both install the line as unique owner -> TWO owners
order between RN0 and RN1 is undefined -> coherence violation

15. Common Mistakes

• Overlapping conflicts for throughput. Assumption: parallelism is always good. Bug: order inversion (the DebugLab). Prevention: serialize same-line conflicts.
• Serializing independent lines. Assumption: order everything. Bug: lost parallelism. Prevention: independent lines run in parallel.
• Ordering starts, not effects. Assumption: sequencing issue suffices. Bug: mid-change reads. Prevention: hold each until it commits.
• Ignoring the predecessor's result. Assumption: each transaction is fresh. Bug: it misses the prior owner. Prevention: successors snoop the new owner.
• Assuming a fixed conflict order. Assumption: program order across cores. Bug: the home chooses. Prevention: rely on an order, not a specific one.
• Conflating with barriers. Assumption: serialization gives cross-address order. Bug: it does not (Chapter 12.1). Prevention: cross-address order needs a barrier.

16. Engineering Checklist

• Serialize transactions that conflict — target the same line.
• Run each conflicting transaction one at a time, the next after the prior commits.
• Ensure each successor observes the predecessor's settled effect (snoops the new owner).
• Run independent transactions (different lines) in parallel.
• Let the home choose the conflict order (arrival, arbitration).
• Recognize this serialization as the source of the per-address order.

17. Key Takeaways

• The home serializes conflicting transactions to one line into a single total order.
• Each conflicting transaction observes the state its predecessor committed — an order of effects.
• Independent transactions to different lines run in parallel — no ordering.
• This serialization produces the per-address coherence order of Chapter 12.1.
• Overlapping conflicting transactions causes order inversion — two owners, torn reads.
• Serialize conflicts, parallelize the rest; the model here is representative.

18. Quick Revision

Transaction ordering. When several transactions target the same line at once, the home serializes them into a single total order — transaction 1, then 2, then 3 — and each observes the line as its predecessor committed it. The home holds one conflicting transaction's ordering until it completes (to CompAck, Chapter 7.6) before starting the next, so the order is of committed effects, not just starts: transaction 2 snoops the owner transaction 1 became. This per-line serialization is exactly what produces the per-address coherence order of Chapter 12.1. Independent transactions to different lines cannot conflict, so they run in parallel — the cross-address freedom of 12.1. The failure to avoid: letting two conflicting same-line transactions run concurrently, so the second acts on state the first has not committed — their order is undefined, yielding inversions like two owners or a torn read. Serialize conflicts one at a time, each after the prior commits; parallelize independent lines. Representative model; 12.3 opens barrier transactions.

Coming Next

Chapter 12.3 — Barrier Transactions. Per-address order is produced by serialization; cross-address order needs an explicit barrier — and CHI carries barriers as first-class transactions. Chapter 12.3 introduces the barrier transactions that the interconnect propagates to enforce ordering the memory model does not give for free, how a barrier relates to the DMB and DSB instructions above it, and why a barrier must be honoured across the fabric to have effect — the mechanism behind the barriers Chapter 12.1 called for.