4 ms·
The Alpha had an incredibly weird memory model that could create this behavior: Assume: p=&a, a=1, b=0 Thr. 1 | Thr. 2 b = 1 | memory_b
by zozbot234 7y ago
The Alpha had an incredibly weird memory model that could create this behavior:
Assume: p=&a, a=1, b=0
Thr. 1 | Thr. 2
b = 1 |
memory_barrier | i = *p
p = &b |
The result can be i = 0
Even though p=&b happens after b=1 in Thread 1, it is seen as happening before it by Thread 2. This is basically because the b=1 part might get ignored by Thread 2 unless that thread also goes through a memory barrier of its own. When the i = \*p is executed, Thr. 2 might read p from main memory as written by Thr. 1, but then still rely on the old b=0 value sitting in its cache. It's hard to describe that as being "superior", but maybe it enabled some performance optimizations in the common case that made it worthwhile.
- ajross 7y agoI'm not sure I understand your example. The Alphas had a pretty standard MESI cache architecture and a very typical cache coherence behavior. It's true that individual CPUs require barriers to enforce ordering, which is not true on x86 (where the architecture guarantees consistent ordering or memory operations between all entities on the bus, and spends significant die area to do that). But honestly x86 is the odd architecture here -- almost no one else felt that was a good tradeoff. (In hindsight, x86 was right, of course.) Where Alpha was weird was in its floating point implementation (two versions on chip! to support the crazy VAX formats that no one cared about even at the time) and its alignment requirements (the hardware, not really atypically, couldn't make a misaligned load, but actually "could" by trapping into a microcode handler that was 10x slower, leading to mysterious insane performance regressions).
- wbl 7y agoWhy should the hardware do something software can take care of just as well was the design philosophy here.
- ajross 7y agoBecause when it doesn't, it leads to "insane" results like the one upthread. Reasoning about memory barriers is outrageously hard, and asymptotic software quality is outrageously expensive. At the end of the day an x86 kernel is going to have fewer race conditions than one for a traditional architecture, and that's worth something. This is a lesson that software folks have been pushing with tools like static typing and memory lifetime analysis. The same applies at the hardware level.
- zozbot234 7y agoYou "just" need a memory barrier on every ptr indirection (including array indexing, etc.) that might go through something that's being shared among multiple threads. The more interesting question is whether requiring that additional barrier buys more performance in the typical case where you're not touching shared data.
- BeeOnRope 7y ago> The more interesting question is whether requiring that additional barrier buys more performance in the typical case where you're not touching shared data. Probably yes, i.e., there was some hardware reason for it. You can find one explanation [1] floating about that explains the effect was due to the cache banking design, with separate invalidation queues for each bank. Presumably that was better in some respect than the alternative designs available to implementors. That said, the difference is probably fairly small and if Alpha were around today they would almost certain want to abandon that particular reordering since they are the only one doing it and there would be a lot of pressure on them to make it fast (this comes up in all sorts of non-trivial scenarios like double checked locking, reads of final fields in Java, etc). That's generally the pattern, I think: if you are the odd man out with the weakest model, and you aren't the dominant player, you will have a lot of pressure to at least offer fast ways of lining up with the stronger models. So even if a weak model is a better design point in a vacuum, it might not be true when real-world implementation pressures are considered. --- [1] http://lse.sourceforge.net/locking/wmbdd.html http://lse.sourceforge.net/locking/wmbdd.html
- pm215 7y agoThe Alpha did have a memory model that was weaker in some respects than pretty much every other RISC CPU. I'm not clear on the details, but I think that one of them is described in https://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt in the 'GUARANTEES' section -- if you do "Q = LOAD P; D = LOAD *Q" then on Alpha and only on Alpha extra barriers are required to ensure that the second memory access (whose address depends on the result of the first load) really does get issued in-order after the first.
- waterhouse 7y agoI've seen it mentioned in several memory model texts that, while ARM's model is more "relaxed" than x86, the DEC Alpha's model is even more relaxed. For example: [1] says "The venerable DEC Alpha is everybody’s favorite example of a weakly-ordered processor. There’s really no mainstream processor with weaker ordering", and [2] says "Some CPUs (such as i386 or x86_64) are more constrained than others (such as powerpc or frv), and so the most relaxed case (namely DEC Alpha) must be assumed outside of arch-specific code." [1] adds, specifically, "[data dependency ordering means that] if you write A->B in C/C++, you are always guaranteed to load a value of B which is at least as new as the value of A. The Alpha doesn’t guarantee that." [1] https://preshing.com/20120930/weak-vs-strong-memory-models/ https://preshing.com/20120930/weak-vs-strong-memory-models/ [2] https://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt
- jcranmer 7y agoThe example isn't explained well in general, IMHO. Suppose thread 1 executes the following code: x = 1; store_fence(); p = &x; At a hardware level, it's guaranteed that the cache coherency traffic to update the value of p is going to happen after the traffic to update the value of x. So it's natural to assume that means that anyone who sees that p == &x must have to see that x == 1 as a result of this traffic. And for most architectures you'd be correct. But you would be wrong on Alpha. Alpha has two cache banks, and there is no coordination between them (in the absence of memory barriers). So if p and x reside in different cache banks, it's possible for a thread to load the value of p (observing that it is &x), and then load the value of *p and fail to see the assignment of x = 1--if the cache bank that contains x is somewhat overloaded on processing the bus traffic, for example. Incidentally, you can't actually take advantage of the opportunity to avoid the memory barrier in this scenario on everyone-but-Alpha in the C++11 memory model, because it turns out that figuring out how to specify the (hardware) data dependency matters for ordering purposes in a source language is a lot trickier than it might appear. memory_order_consume (added for this purpose) is lowered to memory_order_acquire in all compilers I'm aware of.
- dragontamer 7y ago> This is basically because the b=1 part might get ignored by Thread 2 unless that thread also goes through a memory barrier of its own. Note: without a memory barrier on BOTH sides, your code is factually wrong anyway and is open to memory-ordering issues. With the modern "acquire-release" memory model, you need a release-barrier in Thread#1, and an acquire-barrier in Thread#2, for code to be fully correct. Acquire and Release barriers, also known as "half barriers", weren't invented in the time of DEC Alpha. But DEC Alpha's full barrier ("mb") would make the code correct.
- BeeOnRope 7y agoI am not sure what you mean by "factually wrong": the whole point of the example is on no other platform is a memory barrier required on the RHS. Even on ARM and POWER, very weak models, an address dependency orders the reads. This is the 'MP+dmb/sync+addr′' litmus test in 4.1 in [1]. This type of dependency, which doesn't need a barrier to work, is why C++ invented the whole convoluted "consume" ordering in the memory model, pretty much doubling the size and complexity of the model. --- [1] https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf
- dragontamer 7y ago> I am not sure what you mean by "factually wrong": the whole point of the example is on no other platform is a memory barrier required on the RHS. Think about the C++ code and how the compiler could implement your code. Thread 1: b = 1; memory_barrier(); p = &b; Thread 2: *p = (whatever); ... i = *p; A slight change, but lets say Thread2 has the p = (whatever) a bit earlier. The compiler could cache p inside of a register, and may NEVER read p from memory and update it in time! The memory barrier in thread2 is still needed so that the COMPILER knows that its register state is potentially stale. Even today, with half-barriers and a stronger memory model, the compiler can't read the mind of the programmer.
- BeeOnRope 7y agoBased on that reply, I am going to assume you are not familiar with how these litmus tests are written, or more generally with how hardware memory models are discussed (hint: this is just C-like pseudocode showing the order of accesses to discuss hardware reordering so saying "what if this is cached in a register by the compiler" is a non sequitur: there isn't any compiler involved here). So I don't think I can usefully continue this branch of the conversation, sorry. That said, if you want some good reading on the topic I recommend Cambridge memory model group reference I linked above. In fact, all of the Cambridge stuff is good: they got the x86 memory model right (correctly described), even before Intel did! FWIW, the OP was spot on: this is a canonical example of a reordering the Alpha does (did) that no one else does. It comes up over and over when you talk about memory models. It's almost a meme: "that's the one that Alpha did..."