Juxtaposed with that is the fact that the Stein-enhanced version of Introduction to Algorithms does NOT contain the chapter on parallel algorithms that the old CLR used to have. In fact, I'll probably use the chapter outline from CLR if I cover parallel algorithms at any level. I wonder what was the thinking behind removing the chapter on parallel methods, and whether this might be reversed in future editions.
Update: (that was quick! - thanks, Cliff): Tom Cormen writes in to explain the decision to remove the chapter on parallel algorithms:
Cliff Stein pointed me to this blog. Suresh asked why we removed the chapter on parallel algorithms when we wrote our second edition.I'm not surprised. It *was* true that by the time the 2nd ed arrived, PRAMs were yesterday's news: in fact, streaming and external memory methods were "hotter" at the time. It'll be interesting to see if multicore actually does spur new interest in parallel algorithms, and not just parallel architectures. In recent months I've participated in discussions about algorithm design for things like the Cell and the implied architecture of nVidia's CUDA, and it's surprising how often standard parallel algorithms methods like pointer jumping and the like are being reinvented.
The chapter on parallel algorithms in the first edition was exclusively on PRAM algorithms. We wrote the second edition mostly during the late 1990s, into early 2001. At the time, PRAM algorithms were yesterday's news, because the PRAM model was too far from what could be built realistically. We considered including algorithms for some other parallel computing model, but there was no consensus model at the time. We felt that the best decision was to just leave out parallel algorithms and use the pages for other new material.
What makes the new platforms more interesting is that there are features (especially streaming features) that make the mapping to "standard" PRAM models not so obvious. It may not merely be a mattter of shoehorning new systems into parallel models, but of extending and modifying the models themselves.
I was talking with my former roommate back in college, who is doing CPU design. He also complained about the lack of parallel algorithms (in general), as the system can easily extend to multi-core (16, 32, 64...) nowadays.
ReplyDeleteOne reason is because human beings are sequential (really?). For example, whenever I have two papers to write, I will finish none.
Cliff Stein pointed me to this blog. Suresh asked why we removed the chapter on parallel algorithms when we wrote our second edition.
ReplyDeleteThe chapter on parallel algorithms in the first edition was exclusively on PRAM algorithms. We wrote the second edition mostly during the late 1990s, into early 2001. At the time, PRAM algorithms were yesterday's news, because the PRAM model was too far from what could be built realistically. We considered including algorithms for some other parallel computing model, but there was no consensus model at the time. We felt that the best decision was to just leave out parallel algorithms and use the pages for other new material.
--Tom Cormen
In reply to anon1:
ReplyDeleteThat's a scheduling problem, not a parallelization problem :). For example, read Scheduling Algorithms for Procrastinators
So, what are the parallel computation models popular now? (I'm an outsider to algorithms...)
ReplyDeleteWell that's the thing: formal models for parallel computation exist, but are not popular right now (I should be careful about claiming that they are not popular; it's just that parallel algorithms used to be the main heart of the algorithms community). Such models are mainly PRAM variants, although in the past there have been others.
ReplyDeleteParallel architectures (i.e actual platforms) are now coming back into vogue, mostly centered around massively multicore systems, and large petaflop systems. There's also work on so-called cluster systems, with bunches of boxes hooked together (or bunches of graphics cards hooked together). Google's compute farm is a good example of this.
There are also different versions of the BSP model introduced by Valiant.
ReplyDeleteWhile the PRAM model gets it knocks, the algorithmic ideas used for PRAMs are used for many other models. The resurgence of interest in parallel algorithms comes in large measure from the next generations of multiprocessors which (modulo synchronization) are not so far from the PRAM model.
ReplyDeleteThere are two parallel algorithms textbooks that I recommend highly:
The first is Ja' Ja's excellent Introduction to Parallel Algorithms text from Addison-Wesley. About the only clever PRAM algorithmic ideas not covered there are the Lam et al algorithms for fast EREW undirected connectivity that were the basis of Trifonov's O(log n loglog n) space algorithm for the problem.
The second is Tom Leighton's Intro to Parallel Algorithms: Trees, Array, Hypercubes. This was meant to be the first volume of a two volume set, the second of which would do PRAM algorithms. This network-oriented style of parallel computing may yet be the right model for chip multiprocessors.