In the first edition of Introduction to Algorithms (Cormen et al., MIT Press, 1990), the discussion of parallel algorithms is based on the PRAM model. In the second edition, parallelism has been eliminated, but in the third edition (Cormen et al., MIT Press, 2009), the topic is reintroduced, but with a dynamic threading model (based on Cilk). The chapters are very different, for sure, and the models seem to be, as well, at least superficially. But I'm wondering: What are the differences in the underlying computational model or abstract machine here?
Their underlying model is still a shared-memory RAM machine with multiple processors. How is this different from the PRAM? Is it the case, perhaps, that they are in fact using the same underlying model, but approaching it differently? The threading is certainly handled differently in the classic PRAM algorithms – more in line with static threading, where you manually schedule which threads/processes are to run on which processors, rather than simply express concurrency/potential parallelism and have some automatic scheduler use the processors available. But still: Are there more fundamental differences?
In their chapter notes (3rd ed., Chapter 27), Cormen et al. write, “Prior editions of this book included material on […] the PRAM (Parallel Random Access Machine) model.” This seems to indicate that they do not view their dynamic multithreading as being built on this model. Is this so? If so, what differences am I missing?
