Lambda the Ultimate

The compare and swap instruction is not a scalable solution to coordinating the many cores.

That is the point of the paper. They expand on the point in a little bit more detail.

Transactional memory (which is recommended in the paper) is not a scalable solution to coordinating the many cores.

Do you have any sources for that statement?

Because I don't quite buy you argument about eventual consistency either.

I looked to use EC for collaborative diagram drawing purposes, it doesn't work right from the box. You still need complex rules, etc. I didn't tried to apply it to memory architectures, though, but I am sure I won't get far.

Where did Hewitt make an argument about eventual consistency?

I confused Casual Consistency and Eventual Consistency.

It is true that transactions need to be kept small, otherwise you'll start running into issues of starvation, convoying, priority inversion, or inefficiency (high rework ratio). But developers can do a great deal with just small transactions...

I gave transactions a try a while back. The trouble I had with them is that transactional semantics don't compose or integrate in a convenient way with IO effects (sensors, actuators, foreign services), streaming data (e.g. audio and video stream synchronization), and observer patterns.

I don't think it's entirely fair to say that they "recommend" TM. They only mention TM at the very end, and it's not really the point of the paper:

As we go forward, we will also need to take into account the evolution of hardware support for synchronization. Today's primary construct, the CAS operation, works on a single memory location. Future architectures will most likely support synchronization techniques such as transactional memory, allowing threads to instantaneously read and write multiple locations in one indivisible step. Perhaps more important than the introduction of new features like transactional memory is the fact that the relative costs of synchronization and coherence are likely to change dramatically as new generations of multicore chips role out. We will have to make sure to consider this evolution path carefully as we set our language and software development goals.

Actually modern processors have become vastly more efficient at executing compare-and-swap instructions. With more cores on the same die and sharing the same L2 and/or L3 caches, many CAS operations can be done directly in the cache. And of course if the processor already has exclusive ownership of that line in its L1 cache then it's essentially a store operation.

But of course CAS is only as scalable as the application's architecture. If your application uses CAS on a few rarely-contended locations in order to allocate large blocks of non-overlapping work to different workers, then one could argue convincingly that CAS scales well. But if your application's behavior is based on a large number of CAS's on highly contended locations, obviously it is not going to scale well. But given that, even if you weren't using CAS and your application has a lot of updates to shared cache lines, you suffer severe penalties due to cache coherence.

I don't understand your comment at all. How can you tell whether programs have the same behavior without a language definition telling you how programs are allowed to behave?

A memory model is a critical part of the definition for parallel programs. Even a message passing model needs to guarantee that values received are the same as values sent, that there will be no closed causal loops in the message order (as a result of speculation), and so on.

When you talk about possible schedules of parallel thread it sounds like you are only considering interleavings of statements in order. That assumes sequential consistency, which hardware designers discarded years ago in the quest for speed. A number of the figures concern results that are impossible under any sequential order, but standard processors may none the less produce.

The main result from recent years is that if synchronization is explicitly marked, and enough to keep the non-synchronization parts from racing, then hardware can keep using current tricks and giving current performance, while still promising sequential consistency at the language level.

I'm not sure where you thought I claimed that we could write programs at all without a language definition - I can't see that in anything that I wrote. Language semantics provide both a definition of what a program means, and limit the possible behaviours. Where evaluations can occur in parallel there needs to be a definition of how the alternative values can be reconciled. This can occur in every read and write operation, arbitrating over a shared resource, or it can happen explicitly in determining the possible orderings of communication. One technique makes it difficult to formalise language semantics (including the consistency of results) in a composable manner. This paper explicitly makes that argument although they refuse to consider the alternative.

A number of the figures concern results that are impossible under any sequential order, but standard processors may none the less produce.

Actually the case that they point out is not possible under any sequential order is also not producible by any known processor (as the authors point out). It seems unlikely that speculated traces within a core would ever be propagated to other cores, which is the justification for that particular scenario.

The idea that sequential consistency has been abandoned is a strange one. If anything designers are falling back on simpler in-order execution cores. Many simple cores are currently outpacing a few complex cores in most cases. The best example of throwing complex designs at the problem is the latest generations of Intel cores - but they go to quite extreme lengths to guarantee consistency. Do you have specific examples in mind?

The idea that sequential consistency has been abandoned is a strange one. If anything designers are falling back on simpler in-order execution cores.

I don't understand your point. I may have misunderstood your comment or even part of the subject paper, but it seems that you are conflating the lack of several machine-level optimization techniques (e.g. value and branch prediction) with sequential consistency. It is clearly not the case, as for example the memory model of ARM machine code is weaker than Intel's (see page 2).

Even if this were true, next-generation ARM cores available today do feature out-of-ordrer execution and speculative execution.

Many simple cores are currently outpacing a few complex cores in most cases.

I find this assertion highly doubtful and fail to see what it has to do with memory models; the micro-architectural evolution of processors in consumer electronics devices does not side with you.

The best example of throwing complex designs at the problem is the latest generations of Intel cores - but they go to quite extreme lengths to guarantee consistency. Do you have specific examples in mind?

Which "consistency" are you talking about? I do agree that they indeed work very hard to recover a relatively strong memory model in the presence of extremely aggressive micro-architectural tricks, but neither x86(-64) nor IA64 guarantees sequential consistency.

Let's take the issue of out-of-order despatch versus in-order. The former achieves much higher performance on single threaded code at the expense of a much more complex circuit. In order to effectively implement the latter requires speculation / prediction to push available work earlier in the execution trace. As a result of this a reorder buffer is required to maintain sequential consistency for the outside world. This reordering can be made simpler by weakening the definition of consistency to allow some results to be pushed back out in an order that doesn't match the original code.

A simple core that executes in-order trivially matches the definition of sequential consistency - as it produces the results exactly in the order that the code specifies they can be retired in that order without any extra work. When designers move from a single-core to many cores a tradeoff arises: use fewer cores that attempt to execute each thread faster, or spend that silicon budget on a larger number of simple cores and rely on a larger number of threads to achieve throughput. Examples of the later approach can be seen in most GPUs today that use hundreds of in-order cores rather than 4-8 complex cores as we can see the latest x86 lineup. The comparison is not exact as GPUs also amortise the cost of control-flow by arranging these simple cores into vector units.

If you go down the route of lots of simple cores then at some point the issue of how to merge results from different threads in a consistent view still arises - but in a different place. Rather than a guarantee on consistency from the order in which individual results were retired back to memory it becomes the responsibility of an external memory control (or cache hierarchy) to arbitrate access between the different units. This is the same problem of determining what output a particular program (spread across multiple cores) will produce under the different possible scheduling / parallel overlaps of the individual computations. It may well be that this arbitration / retirement is not normally referred to as sequential consistency in which case my terminology may have been confusing.

In the case of the x86 chips I was actually talking about the translation between the semantics of the x86 instruction set within each individual core and the real operations being scheduled on the architecture underneath. There is a layer of complex circuitry to ensure that the data-flow architecture underneath produces results that are consistent with the single thread's view of what it is doing. I can't say anything further about that particular point as it relies on some currently unpublished work.

So in summary - my terminology is probably very confusing, but I was referring to the process of merging results from separate parallel processes into a sequence that is consistent with the semantics of the original program. My claim at the start was that viewing the consistency problem as being a set of constraints on the transformations that can legally be performed on the program seems to be a more complex view than asking how we can define the semantics of the language on a given piece of hardware so that it produces the same results. I would suggest that this observation follows from the author's problems in making the former view work.

Rather than a guarantee on consistency from the order in which individual results were retired back to memory it becomes the responsibility of an external memory control (or cache hierarchy) to arbitrate access between the different units. This is the same problem of determining what output a particular program (spread across multiple cores) will produce under the different possible scheduling / parallel overlaps of the individual computations

There is a case that happen in practice with weak memory models -- so in everyday CPUs now -- where the output of two programs running in-order in parallel is not the output of any interleaving / scheduling of the individual in-order computations. It's the "Decker's algorithm" case is cited in the paper : consider X and Y are initially 0, then execute (X = 1; r1 = Y) || (Y = 1; r2 = Y). On most multicore hardware available today, you can get r1=0, r2=0 as a result.
This comes from the cache hierarchy : rather than writing directly to the common memory, which incurs costly synchronizations, hardware thread rather write in their own write buffer which is eventually synchronized. When reading they check the local write buffer first, then the main memory. In the example, none of the write where committed to the main memory when the read took place.

I don't understand whether you consider these situations or not. There is no assumption of complex reordering of instructions by the processor. Everything is executed in-order, but the memory hierarchy produces non-sequentially-consistent result -- and the observable effect is the same as if the read and write were swapped, as the read takes place before the other thread's write is observable; which is why certain people describe the effect of weak memory models as instructions reordering.

PS : if you want to test for some weird test results on your machine, you may try the diy tool developed by Jade Algave and Luc Maranget. The example above is the very first in the documentation. I just tested, and on my machine the output above (both 0) happened 42 times out of 10^6.

Yes I would say that is covered. I take it that is the same Dekker that invented Dekker splits in floating-point algorithms? Figure 4 in the paper was the case that doesn't show up on current hardware.

Viewing the problem as arbitration happening on the outside, rather than reordering of events on the inside, doesn't change anything. They are two different descriptions of the same phenomena. Which one is more appropriate depends on what you are trying to prove, and which way makes it easier to do so.

In the case of (X=1; r1=Y) || (Y=1; r2=X) happening you could treat both of the processes as atomic events that read from some memory (or intermediate buffer) and write to some memory (or intermediate buffer). In the buffered case both pairs of operations could overlap in time and thus operate on 'stale' data, producing the r1=0, r2=0 case as a result. This leads to three possible interleavings L;R, or R;L, or L||R (that is both processes buffer the contents of memory and then execute at the same time).

The description in the paper covers the three sequentially consistent interleavings (which are L;R, R;L and also L0;R0;L1;R1) and introduces something with the same effect as L||R by describing a store buffer. The above description should make it obvious that the same effect can be produced using a read buffer infront of both pieces of code.

If you break down the memory into explicit (non-shared) buffers and make explicit the filling of these buffers then these kinds of effects are easier to model. This claim is well-known in the CSP community and is the basis for the argument that CSP-style semantics that make these steps explicit are more composable than descriptions of processes using shared-memory semantics. (and of course there is a whole separate body of claims for an asynchronous message passing style as well).

In both cases a model is being defined to reason about what effects different forms of parallel execution can have on a program and how to expose that model to the programmer in the language semantics. The paper makes the case that a model of shared-memory that exposes all of the warts and weirdness is simply too much for the programmer to understand - but that the solution lies in defining a weaker memory model that only exposes some of the problems. Given that an alternative model exists that precisely shows where these problems crop up it seems a strange approach to me.

Even a message passing model needs to guarantee that values received are the same as values sent

Well, it doesn't _need_ to guarantee this, and practically speaking it can't if you're sending messages over an unreliable network.

It could specify that the chance of undetected random corruption must be below some threshold, though.