<p>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.</p>

CC BY-SA 3.0
2014-05-31T13:47:07.903Z
2014-05-31T16:40:53.580Z
2014-05-31T16:40:53.580Z
Dervin Thunk
<p>Update:</p>

<p>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.</p>

CC BY-SA 3.0
2014-06-01T17:14:38.443Z
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).
Dervin Thunk
CC BY-SA 3.0
2014-06-01T17:43:30.930Z
@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.
labotsirc
CC BY-SA 3.0
2014-06-01T15:54:35.147Z
2014-06-01T17:47:45.153Z
2014-06-01T17:47:45.153Z
labotsirc
<p>In the first edition of <em>Introduction to Algorithms</em> (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 <a href="http://supertech.csail.mit.edu/cilk/" rel="nofollow noreferrer">Cilk</a>). 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?</p>
<p>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?</p>
<p>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?</p>

CC BY-SA 3.0
2014-05-30T12:09:38.230Z
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…?-)
Magnus Lie Hetland
CC BY-SA 3.0
2014-05-31T13:54:58.307Z
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.
Dervin Thunk
CC BY-SA 3.0
2017-08-11T02:43:28.253Z
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
Gonzalo Navarro
CC BY-SA 4.0
2021-06-26T20:52:57.823Z
@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.
user21820
<ds.algorithms>
Difference between PRAM and machine model in dynamic multithreading
Magnus Lie Hetland
# Difference between PRAM and machine model in dynamic multithreading

(Asked by: username_0 on 2014-05-30)

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](http://supertech.csail.mit.edu/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?

**Tags:** ds.algorithms

> **Comments:**
> **username_0**: 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…?-)  
> **username_1**: 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.  
> **username_2**: 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. username_2  
> **username_3**: @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.  

---

## 2 answers

### Answer by username_1 on 2014-05-31. Score: 3

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.


---

### Answer by username_4 on 2014-06-01. Score: -1

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.

> **Comments:**
> **username_1**: 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).  
> **username_4**: @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.  

---

