meaning of "memory ordering obeys causality"?

Question

I'm very new to multiprocessor programming.

In article about x86 memory model.

In a multiprocessor system, memory ordering obeys causality (memory ordering respects transitive visibility).

Please, help

Answer 1

Obeying causality means that if thing A causes another thing B, and if you observe that B has happened, then you will also observe that A has happened. Consider the following code:

x = 0
y = 0

thread 1        thread 2

  x = 10          r1 = y   // #1
  y = 25          r2 = x   // #2

Assuming that all reads and writes are individually correct (i.e. atomic at the instruction level with no tearing, e.g. by using relaxed atomics in C++), consider what thread 2 thinks of the world at point #1.

• if r1 is zero, then we know nothing. The execution of thread 1 could be anywhere; it might not have started yet, or it might already have completed but the changes aren't visible yet.

• However, if r1 is 25, then by causality we know that r2 must be read as 10, because the only way that r1 could have read 25 is if thread 1 had executed both statements already, and the strong memory ordering of x86 guarantees that the effects of previous (causally preceding) stores are visible.

Note that this is not a general feature of all hardwares. In popular contemporary memory models (such as those of C++11, C11, Java and Go), we would say that the in above operations, the store y = 25 has "release ordering" and the load r1 = y has "acquire ordering", and the two operations "synchronize".

Answer 2

On modern processors, a read from memory occurs long before the processor executes an instruction that requires the value. The job of the prefetcher, it ensures the processor won't be stalled waiting for the very slow memory read to complete. And a write to memory happens long after the processor executed an instruction that updated the value. The job of the writeback buffer, it ensures that the processor can continue to execute instructions and doesn't have to wait for the very slow memory write to complete.

This can cause ordering problems, the prefetcher might read memory of variable B before reading variable A but the processor might actually use A before B. Same story for the writeback buffer, it could perform the memory write in a different order than the processor executed the updates.

Things will then go wrong when another thread uses those same values, it could see a stale value for A but an updated value for B even though the program updated A before B. That's a bug that's nearly impossible to diagnose, it is causality violation. An expensive word that just means "this makes no freaking sense!", the more typical exclamation when you see this happening when you debug your multi-threaded program.

The x86 and x64 architectures have a strong memory model, it promises that these kind of ordering problems do not occur. Other architectures, like ARM and Itanium, are weak and require explicit ordering instructions. A weak memory model is desirable because it can be faster and requires less power. Only processor designers like them, programmers hate them. But it is very rarely something you'd ever explicitly take a dependency on, you use the synchronization primitives provided by your language runtime or operating system to ensure good mental health.