Two persons stand on a railway embankment at points A and C, exactly 500 meters apart. Lightning strikes precisely in the center of them, at point B, 250 meters away from both:
<--A----------B----------C-->
Presuming both persons are stationary, does the event (lightning strikes) occur “at the same time” from the perspective of the two persons? In our simplistic one dimensional model, the answer is Yes, precisely because the point of the lightning strike, B, is equidistant from A and C.
The person at point C may just as well be responsible for generating the event, by using some form of light rod instead of a lightning bolt supplied by nature. If the person at C lights such a rod, would the event still occur “at the same time” for both persons? Clearly No, because it will take some amount of time for the event’s occurrence to travel the distance from C to A, specifically the time it takes for light to travel 500 meters. Whereas for C it happens nearly instantaneously.
Practically speaking, this amount of time it takes for the light to travel to A will of course be so minute as to be nearly immeasurable, but nevertheless there are two separate times t and t’, the former being the actual time the rod is lit at C, and the latter being the time at which it is perceived at A. This is commonly referred to as relativity of simultaneity, introduced as Lorentz’s local time in the late 1800's and further formalized by Einstein's special theory in 1905.
Now imagine that a new person is placed at point B, equidistant from A and C, where the original lightning struck. If the person at C lights his rod, will the person at B observe the event before the person at A does? Most certainly. It takes less time for light to travel 250 meters than it does 500 meters.
Let us extend our working example a bit. Imagine again three persons, one at point A, one at point B, and another at point C. Those at B and C hold their own light rods. The person at C lights a rod, and in response to seeing C’s rod lighting, the person at B also lights a rod. The question is, must the person at A witness the light emanating from C’s rod prior to witnessing the light emanating from B’s rod? Unless the person at B’s response is truly instantaneous (which we assume is practically impossible), or unless he can see into the future (which we also assume is impossible), clearly the answer is Yes. Because the rod at B was lit in response to witnessing C’s lighting of the rod, some amount of time must have passed during the response, and the person at A will thus see C’s lighting first (or at the very least simultaneously, assuming near-impossible instantaneous response). We say B’s lighting is causally dependent on C’s lighting.
The main point here is that time is an illusion. There is no global time clock. Instead, events are not only distinguished by some monotonically increasing time value t, but also by a location which is defined by three-space coordinates. This is Minkowski’s four-dimensional space. One event occurring at coordinates { x=0, y=0, z=0, t=99 } may not appear to be simultaneous with some other event at coordinates { x=42, y=42, z=42, t=99 }, depending on the observer's location, even though both events occur at time t = 99.
Perception is relative. There is no global total ordering, only a local (relative) one.
A similar phenomenon is true of multiprocessors. In fact, nearly everything said above applies equally to them, provided that you replace “persons” with “processors”, and lighting of rods with writes to memory and witnessing of the light with reads from memory.
Multiprocessor architects must cope with the increasing bottleneck on a central memory unit, particularly due to shared memory programming. One common means of doing so is to increase the distance between processing elements and the memory units they use, padding this distance with ample levels of cache. Some processor A may have a local memory (cache) that is separate from some other processor C’s, and A’s writes to it will be visible to A before C, for example. And if some processor B sits in between them, it may notice such writes before C does. Locality matters.
Of course, memory ordering models are meant to eliminate such distances from the programmer’s mind, at least to some degree. They provide a set of rules governing the timing and ordering of events. But there is just no denying the laws of physics. My claim is that a proper ordering model ought to obey what can be derived from the special theory of relativity: no more, no less. That is, the fundamental laws of how events occur and are correlated in the real world should be mimicked. This means only two things, as far as I can tell:
- An event stream (writes) originating from a source must appear to happen in order.
- Causality is respected, in that when C causes B, it is implied that A must see C followed by B.
This turns out to be stronger than some models, but also weaker in some regards. Distance and latency are first class, embellished, and allowed. There is some cost to ensuring events leaving a locale do so in order, and that events arriving into a locale also do so in order. Given coarse enough locales, however, this cost ought to be amortized over the cost of inter-locale communication.
Notice that sequential consistency is explicitly discouraged. The ordinary store-followed-by-load ordering that I've written about many times is legal. Considering this phenomena in the context of light rods and relativity makes it clear why. Imagine that the persons at A and C light their rods simultaneously. If the person at A immediately, after lighting the rod, looks to the right to see if C has lit the rod, the answer will be No; and similarly, if the person at C immediately, after lighting the rod, looks to the left to see if A has lit the rod, the answer will also be No. Although the real reason has to do with gross details like store buffers and cache coherency, the elegant reason supported by the model is that it takes time for light to travel the distance between A and C.
I also want to point out that “memory ordering model” commonly refers to individual loads and stores, at a very low level, but just as well applies to a higher-level model such as might be found in an actor-oriented (message passing) programming language. People often believe memory ordering and interleaving goes away magically with message passing models. This is simply not true, even if instruction-level interleaving is eliminated. The granularity merely coarsens, but the problem still remains the same.
Despite the lack of sequential consistency, implementing such a model can pose challenges, due to restrictions on optimizations like pipelining and out of order execution. (Hey, at least we needn’t worry about processors moving about at different velocities, as in the more interesting parts of special relativity.) But I believe it is necessary. This price paid will be rewarded with a system that human beings can be taught to reason about as they do in the real world. Remember: I am not just talking about memory models in the traditional sense, where people are tempted to sweep the problem under the rug of "only super-developers doing lock-free programming need a model"; it matters for higher level concurrency orchestration patterns too. In the end, let us not forget: correctness and understandability trump performance optimizations for all but the most low-level systems developers, which make up less than 1% of the development population.
1. Relativity: The Special and General Theory. http://en.wikisource.org/wiki/Relativity:_The_Special_and_General_Theory
2. Time, Clocks, and the Ordering of Events in a Distributed System. http://research.microsoft.com/en-us/um/people/lamport/pubs/time-clocks.pdf