7.5Non-Atomic Bus

Every protocol so far leaned on Atomic Transactions. That atomicity buys simplicity and costs performance: an atomic bus is the unpipelined processor of interconnects.

7.5.1–7.5.2 Three buses

An atomic bus’s throughput is capped by request+response latency — DRAM latency, in the worst case. A pipelined bus pipelined bus A non-atomic bus whose responses arrive in the same order as their requests. defined in Chapter 7 — open in glossary overlaps them (responses in order); a split-transaction bus split-transaction bus A non-atomic bus whose responses may arrive out of request order; responses must carry the identity of the request or requestor. defined in Chapter 7 — open in glossary lets a low-latency response overtake a slow one. (Atomic transactions can still be enforced on a pipelined bus with a same-block lookup table — the SGI Challenge did — but this section drops the property entirely.)

7.5.3 The system model

Split request bus and response bus, operating independently; each controller connects to both (memory issues no requests). Crucially, each controller’s incoming queues are processed in strict FIFO order, regardless of message type or address — if the head request stalls, everything behind it waits. That discipline preserves the total order; its side effects drive everything below.

7.5.4 The stalling protocol

Dropping Atomic Transactions makes new transitions possible: requests can now arrive for a block whose transaction is mid-flight. The key insight for reasoning about them: the transaction was ordered at its request, so a block in IM^D is logically M — an owner without data. This protocol’s answer: stall such requests until the data arrives (deadlock-safe, since the un-stalling Data travels the response network, which stalls can’t block):

Stalling creates a strange new possibility — a requestor can see the response to its request before processing the request itself, because its own request is FIFO-queued behind a stalled one. Step through the book’s two-block scenario (Table 7.19):

That’s what the new X^A states are for: data in hand, transaction not yet in effect, block logically in its old state (IM^A ignores others’ requests; IM^D must answer them).

One more redesign: NoData is gone. The LLC now augments each block with an owner field, updated on every ownership-changing transaction — so a PutM from a non-owner is recognized at the LLC, and the II^A cache simply drops to I. (In a non-atomic system, NoData messages could be numerous and could even arrive before their PutMs.)

7.5.5 The non-stalling protocol

Stalling the head of the queue delays every request behind it — even requests for other blocks the controller could happily process. Reordering is forbidden (total order!), so the fix is to process every request, in order, by remembering deferred work in the state name: IS^D_I (“awaiting data; when it comes, take my one load, then go to I”), IM^D_S, IM^D_SI, and friends:

The memory controller still stalls — and not for laziness: a non-stalling memory in IorS^D observing GetM, then GetS, then GetM… would need transient states encoding arbitrarily long chains. There is no elegant bound smaller than the number of cores, so memory stalls and the caches don’t.

The scoreboard: nothing here is individually complicated, but the state count roughly tripled from the atomic-transactions baseline. That is the price of bus performance — and chapter 8’s directories will pay a related price for scalability.