Is Parallel Programming Hard, And, If So, What Can You Do About It?
kernel.org
kernel.org
That's why I chuckle a bit when parallel programming is reduced to discussions about barriers and mutexes -- paradigms such as dataflow don't need these kludges. That is, until you try to implement dataflow in a von-Neumann architecture (and today you have little choice).
We can probably agree that moving limbs isn't intrinsically "hard". But it probably would be if our biological makeup was built for photosynthesis.
Even if your dataflow application does not need synchronization, then you need to be able to reason about the fact that you have inherent asynchrony when you go to look at your results. That is, you may see this item and that item paired together - is that a valid result? The kind of reasoning required to figure that out is similar to what's required in, say, multithreaded programming.
Large scale parallel message passing apps are extremely difficult to get right. Most people just haven't done it. With that said, some of the difficulties in the past where tied to the fact that message passing was done with a weak type system, no contracts (I sent you message, but how do I know you're ever going to respond to it?), and weak support for gather/scatter.
AFAICT, not having done much at all with Erlang, it deals nicely with the type system issue, but contracts are still a problem. Gather/scatter is partially assisted in the same way that PM/FM handled it in the past (you get to write code to pull messages out of your mailbox).
My prediction is that if message passing does take off in a big way, we'll see a pretty strong backlash to shared memory with functionality, such as type ownership and data representation synthesis. Unfortunatley, most of this research is ignored in favor of the more popular functional work (which in itself is good, just not currently balanced in the language community by other types of thinking).
In fact, I made a similar argument in the conclusion of my dissertation (first full paragraph on page 96): http://people.cs.vt.edu/~scschnei/papers/scott_dissertation....
"And then got messy because they stopped using messages for some side channel communication."
... can't happen in pure-Erlang code. Of course there's nothing you can do in Erlang or Haskell that you can't do in pure C, but the problem is that if you are working in C you can't ever quite be sure that something somewhere accidentally mutated a value, when the language makes it so easy. (And let's not talk about C++.) Some of the Haskell leaders call it "wearing the hair shirt".
This is extended agreement, by the way, not a disagreement. If you are stuck in C, there are far worse things you can do that try to impose your own message-passing paradigm, just as there are an awful lot of object-oriented C programs in the world.
IMO, the good parts of object-oriented programming was applying the constraints of mulithreaded messaging passing to the single threaded world. Really clean multithreaded code tends to be extremely decoupled and treat each message is something to be decoded not blindly followed. Yet somehow that fell to the point where using lots of getter/setter are considered acceptable.
PS: That could actually be a good metric how many objects do you use that don't have a single getter or setter.
In a Von Neumann architecture (viz. your current CPU) execution is determined by the previous instruction. Data is stored in a global, randomly accessible memory space.
Synchronizing two data streams in dataflow is just a matter of having an instruction with two inputs. The very semantics of your machine tells you the node's instruction will only trigger when both its inputs are available.
Critical systems with the problems you described are often written in dataflow languages for exactly these reasons. Citing wikipedia:
Lustre is a formally defined, declarative, and synchronous dataflow programming language for programming reactive systems. [...] It is now used for critical control software in aircraft, helicopters, and nuclear power plants.
The other problem is representation of data in the programming language. Objects, which are used in a lot of programming languages, can be hard to use when it comes to parallelism. An object can only be operated on by one algorithm at a time, and to achieve parallelism, you must use concurrency (locking). You can switch to a different paradigm away from OOP (object orientated programming), to something like FP (functional programming). Since everything is a function, with data just being passed around, you can abstract a program to multiple cores in a more natural way. FP comes with its own difficulties though. This isn't to say parallel programs can't be written in OOP programs successfully, it just requires a different mindset to normal programming.
b) GPUs are still first and foremost special purpose hardware. Few applications are benefitting from moving all your data over to your graphics memory, pushing it through a broad but slow pipe and copying everything back to your CPU. You need to pull out all the low-level stops to get the most out of the hardware, which means dealing with really low-level libraries. CUDA has something like 7 types of memory locations you can declare for your data to sit in and some are calling OpenCL too abstract.
The heart of the issue is that von-Neumann architectures are really not well suited to doing parallel programming: global PC in a single random access read/write memory. Any modification you make to that model to duplicate one module will introduce some heavy concurrency issues for you to deal with. For example multi-threading gives you multiple PC in the same memory space, leading to races, deadlocks, starvation etc.
Compare this to simple SIMD. You do a parallel operation float4 + float4 without any need for concurrency or synchronization.
With well designed interfaces, parallel programming can be easier. But such interfaces abstract away the need to consider concurrency and synchronization - mostly. If you use the constructions outside of the bounds where safety is promised, then all bets are off. For example, parallelizing for loops with independent iterations with OpenMP is trivial, and you don't have to consider concurrency and synchronization. But once you provide non-independent loops, everything blows up and now those things are very important.
Synchronization and concurrency are much simpler in a system where you do have guarantees. No amount of interfaces or libraries will indeed make OpenMP in C safe, but no amount of hacks are going to make a fine-grained acyclic data flow graph deadlock or share state. The backend of the latter can pay the upfront cost of optimizing the shit away, for example no-copy optimizations, in a safe environment.
One of the biggest research effort in dataflow at MIT came in the aftermath of Multics; the ambitious SMP time-sharing OS research project that later spawned UNIX. citing: http://en.wikipedia.org/wiki/Jack_Dennis
I agree wholeheartedly, but there is a consequence that cannot be ignored: the resulting programming model is less expressive. The consequence of providing those guarantees is that there are something programmers just can't do. It's a trade-off, and I think we're still exploring how to provide a programming model that both abstracts away the complexity while still providing an expressive enough programming model to be useful in most circumstances.
Our exploration of programming models seems to be stuck in the current processor architecture, which was designed for sequential work with some stuff bolted on to make it run parallel. I could say John Backus' speech is becoming relevant again.
This is not ivory tower dreaming. The GPUs have made insane progress because they weren't tied to any computational model to start with.
In other words, not being able to do some things is often exactly what is needed to go forward. I wouldn't for the world want to introduce shared memory in Erlang, nor would I want pointer arithmetic under Java's GC.
Of course in the case of SIMD this nicely happens internally in the hardware so nothing can go wrong, but in more complicated cases, for example if you're programming CUDA you need to care about it sometimes.
I agree that an alternative hardware architecture could probably solve this, but that is taking it a bit far and doesn't help solving any immediate problems.
A dataflow architecture should be doing this in hardware -- don't issue an instruction for execution until all of its operands have been reported. The point is that it's not something the programmer needs to be explicitly concerned about.
But hardware takes long to develop (if practical at all; a hw implementation might become to slow and expensive), and even longer to be mainstream, so I don't really see changing the hardware as a solution.
There is still a need for application-level synchronization. For example, to keep the same money from being withdrawn from a bank account twice.
Unfortunately, there are lots of problems, where this is not possible. For example, for a distributed concensus problem the conflict resolution is application-specific.
"Running fast" is a subset of "moving your legs up and down."