memory-model/Documentation/explanation.txt

19   11. CACHE COHERENCE AND THE COHERENCE ORDER RELATION: co, coi, and coe
608 CACHE COHERENCE AND THE COHERENCE ORDER RELATION: co, coi, and coe
611 Cache coherence is a general principle requiring that in a
615 ordering which all the CPUs agree on (the coherence order), and this
619 To put it another way, for any variable x, the coherence order (co) of
622 comes first in the coherence order; the store which directly
626 You can think of the coherence order as being the order in which the
630 coherence order, that is, if the value stored by W gets overwritten,
633 Coherence order is required to be consistent with program order.  This
636 	Write-write coherence: If W ->po-loc W' (i.e., W comes before
640 	Write-read coherence: If W ->po-loc R, where W is a store and R
642 	which comes after W in the coherence order.
644 	Read-write coherence: If R ->po-loc W, where R is a load and W
646 	W in the coherence order.
648 	Read-read coherence: If R ->po-loc R', where R and R' are two
651 	coherence order.
656 Wikipedia, sequential consistency per variable and cache coherence
657 mean the same thing except that cache coherence includes an extra
660 Any reasonable memory model will include cache coherence.  Indeed, our
661 expectation of cache coherence is so deeply ingrained that violations
675 write-write coherence rule: Since the store of 23 comes later in
676 program order, it must also come later in x's coherence order and
689 If r1 = 666 at the end, this would violate the read-write coherence
692 coming earlier in the coherence order (in this case, x's initial
712 would violate the read-read coherence rule: The r1 load comes before
714 comes later in the coherence order.
726 occur on the same CPU (internal coherence order, or coi) and stores
727 that occur on different CPUs (external coherence order, or coe).
731 related by po.  Coherence order is strictly per-location, or if you
732 prefer, each location has its own independent coherence order.
743 the coherence order.
757 The value loaded from x will be 0 (assuming cache coherence!), and it
794 store falls in the location's coherence order.  In particular, it must
910 maintaining cache coherence and the fact that a CPU can't operate on a
933 	Plain-coherence: This requires that plain memory accesses
935 	the operational model's rules regarding cache coherence.
940 "rcu" and "plain-coherence" axioms are specific to the LKMM.
948 According to the principle of cache coherence, the stores to any fixed
960 "coherence" axiom expresses this by requiring the union of these
968 cache coherence demands.
995 problem is that the position of CPU 0's store in x's coherence order
1003 there must not be any stores coming between W' and W in the coherence
1141 violation of the read-write coherence rule.  Similarly, if we had
1146 W' before W in the coherence order.  It would effectively cause W to
1147 overwrite W', in violation of the write-write coherence rule.
1150 violating the write-write coherence rule by requiring the CPU not to
1263 they execute on different CPUs, and W comes before W' in the coherence
1276 cache coherence.  The relation is called prop, and it links two events
1278 the first event in the coherence order and propagates to C before the
1304 event, because P1's store came after P0's store in x's coherence
1438 store is coherence-later than E and propagates to every CPU and to RAM
1457 Thus W, which comes later than E in the coherence order, will
1467 coherence order, contradicting the fact that E ->coe W.  If E was a
2659 called the "plain-coherence" axiom because of their resemblance to the
2660 rules used by the operational model to ensure cache coherence (that
2663 fall in the coherence order):
2673 	load must read from that store or one coherence-after it).
2678 	the second must come after the first in the coherence order).