Does a coherent load followed by a coherent store make an atomic increment?

No. Atomic RMW requires one indivisible read-and-update in X's modification order (the single order of all writes to X). Separate reads and writes can each be coherent while losing an increment. This lesson uses abstract fetch-add on aligned X and claims no ordering for accesses to other locations.

The plain exclusive-permission transfer, C0 M / 1 handing the line to C1 through H, is the four-hop trace of Three-Hop Versus Four-Hop. The new case is a forward that arrives in the middle of an RMW. Start from that lesson's checkpoint: MSI, C0 M / 1, C1 I / -, H exclusive(C0), memory = 0. H serialized C0's earlier GetM before C1's, so C0's fetch-add must finish before C1's begins. C0 performs the read half of a fetch-add (reads 1). Before its write half, Fwd-GetM(X) for C1's GetM arrives.

The lock is bounded to the one RMW: it starts at the read half and ends at the write half, with no other request or miss in between, so it cannot cause deadlock or livelock. The same rule holds an Inv that arrives while the line is locked. The wrong design answers the forward mid-RMW: C0 sends Data(1), C1 increments 1 to 2, then C0 re-acquires the line and its write half stores 1 + 1 = 2. Two increments from 1 end at 2, not 3: one is lost, although every message and every state was coherent.

Far atomics take another route: the operation is sent to H or the last-level cache and executed there, without the requester obtaining M.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

from itertools import permutations
OPS = (("C0", "R"), ("C0", "W"), ("C1", "R"), ("C1", "W"))
ORDERS = [o for o in permutations(OPS)
          if all(o.index((c, "R")) < o.index((c, "W")) for c in ("C0", "C1"))]
assert len(ORDERS) == 6

def split(order):
    x, read = 0, {}
    for core, op in order:
        if op == "R":
            read[core] = x
        else:
            x = read[core] + 1
    return x

def atomic(order):
    x, returned = 0, []
    for core in order:
        returned.append(x)
        x += 1
    return x, tuple(returned)

def cache(order, lock):
    holder, line, read, mid_rmw = None, 0, {}, set()
    for core, op in order:
        if holder != core:
            if lock and holder in mid_rmw:
                return None  # Fwd-GetM deferred: this order cannot occur
            holder = core  # GetM, Data(line) moves to this core
        if op == "R":
            read[core] = line
            mid_rmw.add(core)
        else:
            line = read[core] + 1
            mid_rmw.discard(core)
    return line

assert {split(o) for o in ORDERS} == {1, 2}
assert {atomic(o) for o in permutations(("C0", "C1"))} == {(2, (0, 1))}
assert 1 in {cache(o, lock=False) for o in ORDERS}
assert {cache(o, lock=True) for o in ORDERS} - {None} == {2}
print("PASS: split RMW and mid-RMW forwarding lose an increment, a locked line does not")

The block runs in the course checks and prints PASS. It enumerates the six interleavings of R0, W0, R1 and W1 with each core's read before its write, starting from X = 0. Split loads and stores end at 1 or 2. Indivisible fetch-adds always end at 2. A cache that answers the forward between its read and write can end at 1. With the line locked, the orders that would need a mid-RMW transfer cannot occur, and every remaining order ends at 2.

Related topics

• Shared course model

• Prerequisite: four-hop exclusive-permission transfer