The Atomic Transaction

Module 7 · Chapter 7.3 · CHI Transaction Model

Project thread — 7.1 read (data pulled, closed by CompAck); 7.2 write (data pushed after a DBID grant). This chapter fuses both into one indivisible operation performed at the home. 7.4 does the snoop transaction.

1. Learning Outcomes

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

• Explain that a CHI atomic performs its read-modify-write at the home, not at the requester.
• State why executing at the point of serialization makes the operation atomic for free.
• Name the four atomic families — AtomicStore, AtomicLoad, AtomicSwap, AtomicCompare (CAS).
• Trace a CAS: operands sent under a DBID grant, result returned as CompData.
• Contrast a CHI atomic with an emulated read-modify-write, and see why the latter races.
• Implement a representative home-side CAS compute unit in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Atomics are how software builds locks, counters, and lock-free data structures. Every mutex acquire, every reference-count decrement, every compare-and-swap loop bottoms out in an atomic operation, and CHI is where those operations actually happen in hardware. If you build or verify a CPU, an accelerator, or an interconnect, you will meet them.

The key idea is where the work is done. The naive way to make an operation atomic is to grab the line, compute in the requester, and write it back — but that opens a window another agent can exploit. CHI closes the window by doing the compute at the home, in one serialized step. Understanding that is the difference between an atomic that is truly indivisible and an emulation that silently loses updates under contention. This chapter is about where atomicity comes from.

3. Key Terms

4. Previous Chapter Connection

Chapters 7.1 and 7.2 built the two halves this chapter fuses. The read returned data as CompData, closed by CompAck. The write required a DBID grant before the requester could send data. Each moved data one direction.

An atomic moves it both ways in one transaction: the requester sends operands (like a write — so it needs a DBID grant), and the home returns a result (like a read — CompData, closed by CompAck). But the defining move is new: the home does not just store the operands or fetch a line — it computes, at the point of serialization. The read taught completion, the write taught the grant; the atomic adds the compute-at-the-home that makes the whole thing indivisible.

5. Core Concept — the compute lives at the home

An atomic transaction performs a read-modify-write on a memory location without any other agent observing or altering an intermediate state. CHI achieves this not with a lock but with location: it runs the operation at the home, the point where all accesses to that address are already serialized.

• Request. The Request Node (RN) sends a REQ naming an atomic opcode — say AtomicCompare — targeting the Home Node (HN), and allocates a tracker with its TxnID.
• Grant and operands. The HN returns a DBID (like a write); the RN sends the operands on DAT, tagged with the DBID. For a CAS the operands are two: the compare value and the swap value.
• Compute at the home. The HN reads the current memory value, applies the operation in one indivisible step at the serialization point, and writes the result back to memory. Nothing else touches the location during this step.
• Return and close. The HN returns the original value as CompData (like a read); the RN answers with CompAck. For a CAS, the RN compares the returned value to its compare value to learn whether the swap took.

The synthesis:

A CHI atomic is a read-modify-write executed at the home. The requester ships operands (write-style, under a DBID grant) and receives the prior value (read-style, as CompData). Because the compute happens at the point of serialization, the operation is indivisible by construction — there is no window for another agent, and no lock is needed. The atomic is the fusion of the write's grant and the read's return, with a compute in the middle.

6. Engineering Mental Model — the transaction happens at the teller's window

You want to update your bank balance atomically — "if it is still 100, make it 150."

• The wrong way: ask the teller to read your balance onto a slip, walk away, do the math yourself, and come back to write the new balance. Between reading and writing, someone else could change the balance — your write would clobber theirs, or theirs yours.
• The CHI way: hand the teller a single instruction — "if the balance is 100, set it to 150, and tell me what it was." The teller (the home) reads, checks, and writes at the counter, all at once, while no one else can touch your account. You get back the old balance and know whether the change took.

The atomicity is not in a lock you hold; it is in who does the work and where. The teller owns the ledger and serializes access to it, so doing the whole operation there leaves no gap.

7. Engineering Diagram — an AtomicCompare (CAS)

Read top to bottom: request, grant, operands out, compute at the home, original value back, close. The read-modify-write never leaves the home.

8. The Atomic Opcode Families

CHI defines four families; they differ in what they compute and what they return.

The rule to carry: AtomicStore is fire-and-forget arithmetic on memory (a lock-free counter increment); AtomicLoad is the same but tells you the prior value; AtomicSwap exchanges unconditionally; AtomicCompare is the conditional one — the CAS that lock-free algorithms are built on. All four share the same handshake shape; only the compute and the return differ.

9. Compute at the Home — why atomicity comes free

The reason CHI atomics need no lock is worth stating on its own.

• The home already serializes the address. Every access to a given line funnels through its home node (Chapter 4.7). The home processes them in an order; there is no simultaneous access to serialize against.
• Doing the RMW there is one step. When the read, the modify, and the write all happen inside the home's handling of a single transaction, no other transaction is interleaved with it. There is no intermediate state for another agent to see or overwrite.
• Contrast with requester-side RMW. If the requester read the line, computed, and wrote it back as separate transactions, another agent could modify the line in the gap — the classic lost-update and ABA races. The atomic exists precisely to remove that gap.
• Contrast with LL/SC and bus locks. Load-linked/store-conditional detects the race and retries, which storms under contention; a bus lock blocks everyone. Near-memory compute neither retries nor blocks — it just serializes, which the home was doing anyway.

The point to carry:

Atomicity is a property of where the operation runs, not a lock you acquire. Run the read-modify-write at the point of serialization, and indivisibility is automatic — the home cannot interleave another transaction into the middle of its own single step. CHI atomics scale under contention because they add no retries and no blocking: the serialization that already exists is the atomicity.

10. Transaction Walkthrough — a CAS that succeeds

RN0 runs CAS(addr, compare=100, swap=150) on a location homed at HN, currently holding 100.

1. REQ. RN0 allocates TxnID 9 and sends AtomicCompare: SrcID 0, TgtID = home.
2. Grant. HN returns DBIDResp with DBID 4 — send the operands here.
3. Operands. RN0 sends compare=100, swap=150 on DAT, tagged DBID 4.
4. Compute at home. HN reads memory: 100. It equals the compare value, so HN writes 150 to memory — all in one serialized step. It captures the original, 100.
5. Return. HN sends CompData = 100 (the original) to RN0.
6. Close and interpret. RN0 sends CompAck. It compares the returned 100 to its compare value 100 — equal, so the swap succeeded; memory is now 150.

Had another agent's write landed "between" the read and write, it could not have — the home did all of step 4 indivisibly. If memory had held 101, HN would have left it unchanged and returned 101; RN0 would see 101 ≠ 100 and know the CAS failed.

11. RTL / Hardware View — a home-side CAS compute

The heart of an atomic is the compute the home performs. For CAS it is one combinational block: compare the current value, select the next value, and return the original. Representative and combinational — the indivisibility comes from the home applying it as a single serialized step, not from the logic itself.

// Representative home-side Compare-and-Swap compute (educational).
// The home reads mem_old, compares it to cmp, writes swp only on a match, and
// returns the ORIGINAL value. Atomicity comes from the home applying this as ONE
// serialized step at the point of serialization — not from this combinational logic.
module chi_cas_compute #(parameter W = 32) (
  input  logic [W-1:0] mem_old,     // current memory value
  input  logic [W-1:0] cmp,         // compare operand
  input  logic [W-1:0] swp,         // swap operand
  output logic [W-1:0] mem_new,     // value written back to memory
  output logic [W-1:0] ret_val,     // original value returned to requester
  output logic         success      // did the swap take?
);
  assign success = (mem_old == cmp);
  assign mem_new = success ? swp : mem_old;   // swap only on match
  assign ret_val = mem_old;                    // always return the original
endmodule

The same behavior in Verilog-2001:

// Representative home-side Compare-and-Swap compute (Verilog-2001).
module chi_cas_compute #(parameter W = 32) (
  input  [W-1:0] mem_old,
  input  [W-1:0] cmp,
  input  [W-1:0] swp,
  output [W-1:0] mem_new,
  output [W-1:0] ret_val,
  output         success
);
  assign success = (mem_old == cmp);
  assign mem_new = success ? swp : mem_old;
  assign ret_val = mem_old;
endmodule

And in VHDL:

-- Representative home-side Compare-and-Swap compute (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_cas_compute is
  generic ( W : integer := 32 );
  port (
    mem_old : in  std_logic_vector(W-1 downto 0);
    cmp     : in  std_logic_vector(W-1 downto 0);
    swp     : in  std_logic_vector(W-1 downto 0);
    mem_new : out std_logic_vector(W-1 downto 0);
    ret_val : out std_logic_vector(W-1 downto 0);
    success : out std_logic
  );
end entity;
 
architecture rtl of chi_cas_compute is
  signal hit : boolean;
begin
  hit     <= (mem_old = cmp);
  success <= '1' when hit else '0';
  mem_new <= swp when hit else mem_old;   -- swap only on match
  ret_val <= mem_old;                      -- always return the original
end architecture;

All three return the original value and write the swap only on a match. The requester reads success by comparing the returned value to its compare operand. The DebugLab shows why this must run as one home-side step, not two requester-side transactions.

12. Verification View — CAS semantics and the original value

The properties that define CAS: the swap happens exactly on a match, memory is unchanged on a miss, and the returned value is always the original.

// Bind to chi_cas_compute.
// 1. On a match, memory becomes the swap value; on a miss, memory is unchanged.
property p_cas_write;
  @(*) mem_new == ((mem_old == cmp) ? swp : mem_old);
endproperty
 
// 2. The value returned to the requester is always the ORIGINAL memory value.
property p_returns_original;
  @(*) ret_val == mem_old;
endproperty
 
// 3. success is asserted exactly when the compare matched.
property p_success_iff_match;
  @(*) success == (mem_old == cmp);
endproperty

The system point, beyond the checks:

These properties describe the compute, but the atomicity is not in them — it is in the home applying the compute as a single serialized step. That is why the return value is the original: the requester needs to know the state the location was in at the instant of the operation, and only the home can report that, because only the home saw that instant without interleaving. A requester-side emulation cannot make this guarantee — between its read and its write, the "original" it saw may already be stale. The atomic's correctness is half compute, half placement.

• What it proves: the CAS compute — swap-on-match, unchanged-on-miss, original returned.
• What it does not prove: the indivisibility itself — that is architectural, from the home's serialization, not from combinational logic.
• Bug signature: an atomic emulated as a separate read then write — a stale "original" and a lost update.

13. Testbench — CAS hit and miss

Drives the compute for a matching and a non-matching compare, checking the write, the return, and success.

module tb_chi_cas_compute;
  localparam W = 32;
  logic [W-1:0] mem_old, cmp, swp, mem_new, ret_val;
  logic success;
  int errors = 0;
 
  chi_cas_compute #(.W(W)) dut (.*);
 
  task automatic check(input logic [W-1:0] m, c, s,
                       input logic [W-1:0] exp_new, exp_ret, input logic exp_ok,
                       input string name);
    mem_old = m; cmp = c; swp = s; #1;
    if (mem_new !== exp_new || ret_val !== exp_ret || success !== exp_ok) begin
      errors++; $display("FAIL %s: new=%0d ret=%0d ok=%0b", name, mem_new, ret_val, success);
    end else $display("PASS %s: new=%0d ret=%0d ok=%0b", name, mem_new, ret_val, success);
  endtask
 
  initial begin
    // Hit: mem 100 equals compare 100 -> swap to 150, return 100, success.
    check(32'd100, 32'd100, 32'd150, 32'd150, 32'd100, 1'b1, "CAS hit  (100==100 -> 150)");
    // Miss: mem 101 != compare 100 -> unchanged 101, return 101, no success.
    check(32'd101, 32'd100, 32'd150, 32'd101, 32'd101, 1'b0, "CAS miss (101!=100 -> 101)");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS CAS hit  (100==100 -> 150): new=150 ret=100 ok=1
PASS CAS miss (101!=100 -> 101): new=101 ret=101 ok=0
ALL TESTS PASSED

14. DebugLab — emulating an atomic with a read then a write

mem = 5
A: Read  -> 5
B: Read  -> 5              (A has not written yet)
A: compute 6, Write 6      mem = 6
B: compute 6, Write 6      mem = 6   <-- should be 7

15. Common Mistakes

• Emulating an atomic with read + write. Assumption: a read/write pair is atomic. Bug: lost update / ABA (the DebugLab). Prevention: use one atomic transaction.
• Ignoring the returned original value. Assumption: a CAS reports success directly. Bug: acting on the wrong outcome. Prevention: compare the returned value to your compare operand.
• Confusing the families. Assumption: all atomics return a value. Bug: waiting for a return AtomicStore never sends. Prevention: AtomicStore returns nothing; AtomicLoad/Swap/Compare return the original.
• Sending operands before the DBID. Assumption: operands follow the request. Bug: dropped operands (the write's grant-before-data, Chapter 7.2). Prevention: wait for the DBID.
• Assuming compute is at the requester. Assumption: the requester does the math. Bug: mis-modeled latency and coherence. Prevention: the home computes, near memory.
• Retrying half an atomic. Assumption: replay just the write. Bug: torn operation. Prevention: retry the whole atomic transaction.

16. Engineering Checklist

• Pick the family by need: AtomicStore (no return), AtomicLoad/Swap (return original), AtomicCompare (conditional).
• Send operands under a DBID grant — two operands (compare, swap) for CAS.
• Expect the original value back as CompData (except AtomicStore); close with CompAck.
• For CAS, decide success by comparing the returned value to your compare operand.
• Never emulate an atomic with a separate read and write.
• On a failed CAS, retry the whole atomic, not a partial write.

17. Key Takeaways

• A CHI atomic performs its read-modify-write at the home — the point of serialization — as one indivisible step.
• Atomicity comes free from serialization: no bus lock, no LL/SC retry storm, and it scales under contention.
• An atomic fuses the write's DBID grant (operands out) with the read's CompData return (original value back).
• Four families: AtomicStore (no return), AtomicLoad, AtomicSwap (return original), AtomicCompare (CAS).
• Emulating an atomic with a separate read and write reopens the lost-update / ABA window — use one atomic.
• Compute at the home, send operands after the DBID, judge CAS by the returned value; the model here is representative.

18. Quick Revision

The atomic transaction. A CHI atomic runs a read-modify-write at the home, the point of serialization, so it is indivisible by construction — no other agent can interleave, and no lock is needed. It fuses the two prior transactions: the requester sends operands under a DBID grant (write-style, Chapter 7.2) and receives the original value as CompData, closed by CompAck (read-style, Chapter 7.1). Four families: AtomicStore applies an op with no return; AtomicLoad applies it and returns the original; AtomicSwap exchanges unconditionally; AtomicCompare is the CAS — if memory equals the compare operand, write the swap operand — and success is read from the returned value. Emulating an atomic with a separate read and write reopens the lost-update / ABA window the atomic exists to close, because the home can serialize another access in the gap. Compute at the home, operands after the DBID, judge by the returned value. Representative model; 7.4 does the snoop transaction.

Coming Next

Chapter 7.4 — The Snoop Transaction. Reads, writes, and atomics are all initiated by a requester. The snoop runs the other way — the home initiates it, reaching into a cache to fetch, invalidate, or downgrade a line on another transaction's behalf. Chapter 7.4 walks the snoop end to end — how the home issues a SnpShared, SnpUnique, or SnpClean, how the snooped node responds with or without data, and how the snoop transaction nests inside the read and write flows you have just traced.