# Difference between PRAM and machine model in dynamic multithreading

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?

• I guess one difference is that in the PRAM, you assume that you have an unlimited number of processors available (and factor this in by modeling the total amount of work performed), whereas in the dynamic multithreading model, you model the efficiency as a function of the number of processors available. Maybe that actually answers the question…?-) May 30 '14 at 12:09
• Why do you think there cannot be infinite procs in Cilk? The $T_\infty$ measure is just that, and it is an integral part of DM. May 31 '14 at 13:54
• This is a related question that may help answer the original one. Does someone know if the following is true: Given an EREW algorithm with n processors and t time, there exists a dynamic multithreaded algorithm with O(tn) work and O(t log n) span. (And why not CREW/CRCW?). It seems to me that one can simulate each EREW instruction by spawning it to all the n processors. On the other hand, there exists Cole's EREW sorting algorithm with n processors and O(log n) time, but the best multithreaded algorithm I've seen is Leiserson's O(n log n) work and O(log^3 n) span. Gonzalo Navarro Aug 11 '17 at 2:43
• @GonzaloNavarro: You cannot simulate EREW algorithms just like that because many of them (including most EREW sorting algorithms) rely on synchronicity of the processors so that they can have pipelined stages that don't collide. As stated in an answer, dynamic multithreading does not assume processor synchronicity. Jun 26 at 20:52

## 2 Answers

Dynamic multithreading (like Cilk) does not involve processors working synchronously (in lockstep), for instance. PRAM is (sort of) SIMD, while DM is (sort of) MIMD. Notice that there are async PRAM models, but none seem to have gathered enough pull. Notice also that DM assumes logical parallelism, while PRAM is very much explicit parallelism, and that PREM machines (unlile DM) don't really exist beyond the lab.

Update:

This answer was based on the assumption that DM was a programming model and the fact that PRAM is a computing model, but Dervin pointed out that DM is also a computing model which is correct.

• This is wrong. DM is not a programming model. It is a computing model. CilkPlus (and indeed any task-parallel environment such as TPL and parts of OpenMP) are programming models that implement DM (if they implement a workstealing scheduler). Jun 1 '14 at 17:14
• @Dervin I was going to disagree with you but after checking Akkary & Driscoll original paper, i see you are right. Thanks for pointing the error. I +1 to your answer BTW. Jun 1 '14 at 17:43