June 3, 2007

How to write parallel programs

I recently finished reading through Nicholas Carriero and David Gelernter's How to write parallel programs (available free online), a hidden gem on parallel computing published in 1990. Most books about distributed and/or parallel computing that I've come across are banal junk (no, no one needs another book about MPI) - How to write parallel programs contrasts sharply.

I suspect a major reason why parallel programming is considered difficult today is that most people don't have any conceptual feel for the space of possible parallel problem-solving approaches. Most educational material presents a fragmented view of models and paradigms; the vast majority of books focus on a single system or approach. The majority of programmers, not having delved into the breadth of the parallel computing literature, simply are not aware that there exist alternatives that may make their parallel problem-solving tasks much easier.

In light of this, the key insight of How to write parallel programs is distilling parallel programming into three distinct, conceptual paradigms for coordination in parallel problem-solving. It may come as a surprise (I promise I won't provide any more spoilers) that DCOM, CORBA, RMI or any other object-oriented "remote method call" junk is not one of them. Which brings me to a tangent where I rant about the whole idea of "remote method invocation" being beyond stupid by managing to get both message-passing in object-oriented programming and the basic assumptions about distributed systems completely wrong. More people should listen to Deutsch and Kay.

How to write parallel programs is intended to be a textbook, and that means algorithm analysis, which frequently leads to surprisingly practical insights about distributed systems, such as load-balancing considerations, dealing with IO bottlenecks, and even using time complexity analysis to (inadvertently) find faulty nodes. Examples are written in C-Linda (an implementation of Gelernter's tuplespaces). Following the arguments and doing the exercises is well worth the time.

I'm going to end this post with a request for help from the readers: I am trying to track down a copy of a paper referenced in the book: R. Abarbanel and A. Janin. Distributed object management with Linda. Research report, Apple Computer, Cupertino, CA, September 1989. If someone has a copy or can obtain one (any old-school Apple employees reading this?), please get in touch.

No comments: