Bill Clementson's Blog

Parallel Computing in Lisp - Part 4

Tuesday, January 25, 2005

I've had a bit of feedback from my previous posts (see Part 1, Part 2, Part 3) on parallel computing in Lisp. I'll cover that feedback as well as tie in a couple of related topics in this post.

Charles Stewart is bothered that I used the Wikipedia definitions for parallelism, concurrency and distribution that (in his opinion) "abolish useful distinctions that I think they ought to express". His feels that:

1. Parallelism is a property of a computation or a machine, which means that control flow occurs on parallel pathways. It is opposed to sequentiality as a property of computation or machines;
2. Concurrency is a property of programs and programming languages, which means the programming language has control constructs (or the program makes use of such) that are most naturally realised by parallel computations. It is, a little confusingly, also opposed to sequentiality as a property;
3. Parallelism and concurrency are intimately related, but it is frequently useful to distinguish them: one expresses the program view, the other the execution view. Concurrent code may be realised on a sequential machine by use of, say, time-sharing; similarly sequential code may be realised by a parallel computation by means of a behind-the-scenes program transformation, which discovers opportunity for parallelism by means of flow analysis.
4. Distribution is something else entirely: of a computation it means that it occurs in space spread out over many locations; of code it means the code expresses that data is stored or code is to be computed at several, named, locations.
5. Distribution normally entails parallelism/concurrency, but code may be concurrent without describing locations, and quantum computation allows parallelism to happen in one place. Furthermore, this entailment is not necessary: a machine that is spread out over many locations, but which is designed so that computation may occur at one sublocation only when computation is suspended at other locations, is not parallel.

"I also like these distinct definitions:

Parallelism is about solving a problem using multiple machines. For example, to render an image using a network of 100 computers.

Concurrency is about coordinating lots of things that are happening at the same time. For example, writing an IRC server.

Some problems combine both, like a database handling lots of concurrent transactions while using lots of disks and CPUs in parallel, but it's not always so.

I find this distinction useful in very many ways. For one, it says that Lisp-based research on parallel programming is some of the best work that's ever been done, and that no research on concurrent Lisp programming has been done at all!"

"Did you know that Tony Hoare's classic book Communicating Sequential Processes (CSP) used Lisp (with M-expr syntax) as a kind of "formal semantics"? The book is online here: http://www.usingcsp.com/. I love it for some reason, I think it's that it gives a nice visual metaphor for concurrent systems (it almost makes them feel mechanical - I think that's a property of synchronous message passing systems but I've never actually tried programming that way)."

"The first Cell based desktop computer will be the fastest desktop computer in the industry by a very large margin. Even high end multi-core x86s will not get close. Companies who produce microprocessors or DSPs are going to have a very hard time fighting the power a Cell will deliver. We have never seen a leap in performance like this before and I don't expect we'll ever see one again, It'll send shock-waves through the entire industry and we'll see big changes as a result.

The sheer power and low cost of the Cell means it will present a challenge to the venerable PC. The PC has always been able to beat competition by virtue of it's huge software base, but this base is not as strong as it once was. A lot of software now runs on Linux and this is not dependant on x86 processors or Microsoft. Most PCs now provide more power than is necessary and this fact combined with fast JIT emulators means that if necessary the Cell can provide PC compatibility without the PC.

It will not just attack the PC industry but expect it to be widely used in embedded applications where high performance is required. This means it will be made in numbers potentially many times that of x86 CPUs and this will reduce prices further. This will also hurt PC based vendors' desires to enter the home entertainment space as PC based solutions [Entertainment] will be more complex and cost more than Cell based systems.

This is going to prove difficult for the PC as CPU and GPU suppliers will have essentially nothing to fight back with. All they can hope to do is match a Cell's performance but even that is going to be incredibly difficult given the Cell's aggressive Cray-esqe design strategy.

Cell is going to turn the industry upside down, nobody has ever produced such a leap in performance in one go and certainly not at a low price. The CPU producers will be forced to fight back and irrespective of how well the Cell actually does in the market you can be sure that in a few short years all CPUs will be providing vastly more processing resources than they do today. Even if the Cell was to fail we shall all gain from it's legacy.

Not all companies will react correctly or in time, this will provide opportunities for newer, smaller and smarter companies. Big changes are coming, they may take years but the Cell means a decade from now the technology world is going to look very different."

"Cilk is a variant of C with features for spawning parallel computations (Cilk programs become equivalent serial C programs when the new Cilk keywords are removed). Its implementation has an effective and highly cool 'work stealing' scheduler for allocating large numbers of fine grained tasks among a smaller set of worker threads.

I don't know if Cilk would be suitable for something like a web server, but for highly parallel computational tasks programs it has done well. A team using Cilk won the ICFP'98 Programming Contest, and Cilkchess, a chess program written in Cilk, came in 4th (out of 30 programs) in the 1999 World Computer Chess Championship."

"The Mozart system provides state-of-the-art support in two areas: open distributed computing and constraint-based inference. Mozart implements Oz, a concurrent object-oriented language with dataflow synchronization. Oz combines concurrent and distributed programming with logical constraint-based inference, making it a unique choice for developing multi-agent systems. Mozart is an ideal platform for both general-purpose distributed applications as well as for hard problems requiring sophisticated optimization and inferencing abilities. We have developed applications in scheduling and time-tabling, in placement and configuration, in natural language and knowledge representation, multi-agent systems and sophisticated collaborative tools."