The Fundamental Shift in Synchronization Costs with Relaxed Memory Consistency — Epoche C1
A four-instruction program that tells the whole story Two processor cores share two memory locations, $x$ and $y$, both initially zero. Core 0 runs two instructions: store $1$ to $x$, then load $y$ into a register $r_1$. Core 1 runs the mirror image: store $1$ to $y$, then load $x$ into $r_2$. Run this on any x86 server and you will eventually observe the outcome $r_1 = r_2 = 0$, in which each core's load appears to have happened before the other core's store. On a machine that enforced sequential consistency that outcome would be impossible. Everything in this essay follows from why it is impossible there, why it happens here, and what it costs to forbid it. The impossibility is provable in three lines from Lamport's 1979 definition. A machine is sequentially consistent if the result of any execution is the same as if the operations of all cores were executed in some single sequential order, and the operations of each core appear in that order in the order its program specifies. Suppose $r_1 = 0$. Then core 0's load of $y$ came before core 1's store to $y$ in that single order. Suppose also $r_2 = 0$; then core 1's load of $x$ came before core 0's store to $x$. Adding the two program orders, which the definition requires the sequence to respect, gives $$ W_x \prec R_y \prec W_y \prec R_x \prec W_x, $$ a cycle. No total order contains a cycle, so the outcome is excluded. Nothing about hardware enters the argument; it is a statement about what orders exist. Why real hardware permits it, and what "relaxed" names Every current x86 processor places its stores in a first-in-first-out store buffer before they become visible to other cores, and allows a later load to a different address to be satisfied from cache while an earlier store is still in that buffer. Core 0's load of $y$ therefore executes while its store to $x$ is still private, and symmetrically for core 1, so both loads return zero. This is the model called total store order, or TSO, given a precise mathematical formulation by Sewell and colleagues in 2010; the formulation matters because before it existed the vendor documentation was ambiguous enough that compiler writers disagreed about what was permitted. TSO relaxes exactly one ordering: store followed by load to a different address. Release consistency, defined by Gharachorloo and colleagues in 1990, relaxes far more. It divides memory operations into ordinary accesses and two kinds of synchronising access — an acquire , which is a read that gains permission to enter a region of code, and a release , which is a write that relinquishes it. Ordinary accesses may be reordered freely among themselves; what is required is that all accesses issued before a release be visible before the release itself takes effect, and that no access after an acquire take effect before the acquire. The original version of this essay listed transactional memory alongside release consistency as a relaxed consistency model. That is a category error and correcting it matters for the rest of the argument. A consistency model is a contract about which orderings of memory operations a machine may exhibit. Transactional memory, introduced by Herlihy and Moss in 1993, is a concurrency-control mechanism: it groups operations into units that either take effect entirely or not at all. A machine may implement transactional memory over TSO, over release consistency, or over sequential consistency; the two choices are orthogonal. The cost analysis for transactional memory is genuinely different in kind, and is treated separately below. The claim that sequential consistency forces stalls, and why it is only half true The original essay stated that under sequential consistency a load cannot proceed until the preceding store is globally visible. That describes the obvious implementation, not the model, and the difference is the largest thing the original assumed without argument. Return to the definition: the requirement is that the execution produce the same result as if there were a single order. A core may therefore execute its loads early, speculatively, provided it can detect any case in which doing so would have been observable and undo it. The detection mechanism already exists in any cache-coherent machine: if a core has speculatively read a line and an invalidation for that line arrives before the load retires, some other core wrote it, and the speculation is unsafe. Squash the instruction and re-execute. If no invalidation arrives, no other core could have observed the reordering, and the execution is indistinguishable from a sequentially consistent one. Adve and Gharachorloo's 1996 tutorial surveys this family of techniques, together with prefetching, as the standard way to close much of the gap between sequential consistency and relaxed models. So the honest position is narrower than the original's. Sequential consistency does not require serialisation; it requires that violations be undetectable, and speculation buys that at the price of rollback hardware and of a squash whenever contention is real rather than merely possible. Relaxed models buy it by declaring the reordering legal, which needs no rollback machinery and no squashes. The advantage is real but it is an advantage over a sophisticated implementation, not over a stalling one. The cost model, corrected The original essay claimed that the cost of a critical section moves from a linear dependence on the number of memory operations, written $O(N \cdot L_{\max})$, to a constant dependence on the two fence operations. The first half is right for a naive implementation; the second half is wrong, and the correct statement is more interesting. Fix notation. Let $N$ be the number of shared-memory accesses inside a critical section, $L$ the latency of an access that must cross to another cache or to memory, $t$ the latency of an access that hits in the local cache, and $T_{\mathrm{acq}}$ and $T_{\mathrm{rel}}$ the costs of the acquire and the release. On