The Shifting Calculus of Cache Coherence Complexity — Epoche C1
Two counters, one cache line Consider two processor cores incrementing two adjacent elements of an array of counters, count[0] and count[1] , with no synchronisation between them and no logical relation at all: the cores never touch the same variable. On a machine whose caches transfer memory in blocks of sixty-four bytes, and with eight-byte counters, both variables sit in the same block, and every increment by one core forces the block out of the other core's cache. The program is data-race-free and correct; its performance collapses. This is false sharing , and the argument of this essay is that it, rather than the two effects usually blamed, sets the scaling limit of a shared-memory multiprocessor — and that the reason can be derived rather than asserted. The terms need fixing first. A cache is a small fast memory holding recently used data close to a processor; it is organised in fixed-size units called cache lines or blocks, typically sixty-four bytes on current hardware, because fetching a whole block exploits the tendency of programs to use neighbouring addresses in quick succession and because one address tag then covers many bytes. In a multiprocessor each core has its own cache, so the same memory location can sit in several caches at once, and a cache coherence protocol is the mechanism that stops one core reading a value another core has already overwritten. Sorin, Hill and Wood, in their 2011 primer on the subject, state the requirement in the form that makes everything else follow: at every moment, for every memory location, either exactly one cache may hold it in a writable state, or any number may hold it readable and none writable. This is the single-writer/multiple-reader invariant, and the whole cost of coherence is the cost of maintaining it. The received account of where that cost comes from names two sources. The first is true sharing — cores genuinely reading and writing the same variable, so that the invariant must actually be enforced. The second is sequential consistency , the strongest and most intuitive rule about the order in which memory operations may appear to take effect. False sharing is treated as a tuning problem for later. The claim here is that the quantitative balance runs the other way, and that seeing why requires counting bytes rather than events. What the protocol costs, and one correction about how it scales The standard invalidation protocol is MESI, introduced by Papamarcos and Patel in 1984, whose four states name the possible conditions of a line in one cache: Modified (this cache has the only copy and has changed it), Exclusive (only copy, unchanged), Shared (other caches may also hold it, read-only) and Invalid (not present). The invariant above is enforced by transitions: to write a line held Shared, a core must first drive the other copies to Invalid. Here the compressed version of this essay made an error that matters for its own thesis, and it should be corrected rather than quietly patched. It modelled the cost of true sharing as a message count $M_{\mathrm{true}}$ proportional to the number of sharers, and then situated the whole discussion on a shared bus. Those two assumptions are inconsistent. A bus is a broadcast medium: every cache observes every transaction. Invalidating a line held by seven other caches therefore costs exactly one bus transaction, not seven, and the number of sharers does not appear in the traffic at all. Per-sharer message counts belong to directory protocols, in which a central record of who holds each line sends point-to-point invalidations over a switched interconnect. The essay's shared-bus argument survives the correction — indeed it is strengthened, because on a bus the cost per coherence event is nearly constant, which is precisely what makes false-sharing events as expensive as true-sharing ones. On a bus, then, the cost of an event is the cost of a transaction, and a transaction has two parts: an address-and-command phase of $a$ bytes, and, when data must actually move, a data phase of $L$ bytes, where $L$ is the line size. A read miss and a write miss both move a full line and cost $a + L$; an upgrade from Shared to Modified, where the core already has the data, costs only $a$. Nothing in this accounting knows or cares whether the core wanted one byte of the line or all of it. Sequential consistency: what it constrains, and what it does not Before the false-sharing argument can be given its due, the other supposed source of complexity must be put in its place, because the compressed essay attributed to it a cost of the wrong kind. Sequential consistency was defined by Leslie Lamport in 1979 as the requirement that the result of any execution be the same as if the operations of all processors were executed in some sequential order, and the operations of each individual processor appeared in that order in the sequence in which the program issues them. Two conditions, then: a single global order exists, and each processor's own program order is respected within it. What this costs is not extra bus traffic. It costs the freedom to overlap. Under sequential consistency a core may not let a later memory operation become visible before an earlier one has, so a store cannot be retired until the invalidations it requires have taken effect, and the following load cannot be allowed to complete first. The consequence is that coherence latency is exposed rather than hidden behind other work. Adve and Gharachorloo's 1995 tutorial on memory consistency models sets out both the definition and the standard responses — write buffers, prefetching of exclusive ownership, and speculative execution with rollback on a detected violation — which recover much of the overlap while preserving the appearance of sequential order. The compressed essay wrote the cost as $T_{\mathrm{SC}} = f(N_{\mathrm{procs}}, M_{\mathrm{true}})$, which is a placeholder rather than a model; the substantive point is that sequential consistency m