<p>I apologize beforehand for the blog-post format of my answer. I couldn't help myself making a small overview of the parallel computing world.</p>

<p>You can categorize parallel programming models in roughly two categories: control-flow and data-flow models.</p>

<p>The <strong>control-flow models</strong> try to make parallelism work within the context of a explicit-control program, basically every programmable computer today.  The fundamental problem being tackled is that such a 'Von Neumann architecture' was not designed for parallel execution, but efficient sequential computations.  Parallelism in such context is obtained by duplicating parts of the basic modules (memory, control, arithmetic). </p>

<p>Duplicating only arithmetic gives you SIMD instructions, all ALUs share the same Program Counter (PC) and thus always execute the same operation in parallel, albeit on different data. </p>

<p>Duplicating ALU and the PC but keeping the instruction sequencer inside the control unit gives you Out of Order (OoO) execution that yield some pipeline-parallelism. In this category you also have the Very Long Instruction Word (VLWI) and branche-prediction techniques. You rarely see this category at a software level though.</p>

<p>Going a bit further is duplicating the whole 'core' but keeping the memory shared, these are the current multicore processors that give you task (or thread) parallelism.  Sharing memory in this context gives you very, <a href="http://lambda-the-ultimate.org/node/4211">very hard and subtle concurrency issues</a>.  Parallel computations on current multicore are thus completely revolving around synchronization/concurrency problems, the careful balance of performance (no sync) and desired semantics (totally synchronized, sequential execution semantics). Examples of this is the PRAM or more popular these days the <a href="http://supertech.csail.mit.edu/cilk/">Cilk</a> ofshoots such as fork/join (<a href="http://threadingbuildingblocks.org/">IntelTBB</a>, <a href="http://download.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html">Java.Utils.Concurrency</a>). CSP and Actor models are concurrency models, but as mentioned above concurrency and parallelism become blurred in a shared-memory environment. n.b. parallelism is for performance, concurrency to maintain correct semantics.</p>

<p>Duplicating memory too gives you either networked computers that get programmed with MPI and its ilk or just strange non-Von Neumann architectures such as the network-on-a-chip processors (cloud processor, the Transputer, Tilera). Memory models such as <a href="http://en.wikipedia.org/wiki/Uniform_Memory_Access">UMA</a> or <a href="http://en.wikipedia.org/wiki/Non-Uniform_Memory_Access">NUMA</a> try to maintain the illusion of shared memory and can exist on either software or hardware level. MPI maintains the program-level parallelism and only communicates via message passing. Message passing is also used on a hardware level for communication and concurrency (Transputer).</p>

<p>The second category are <strong>data-flow models</strong>. These were designed at the dawn of the computer age as a way to write down and execute parallel computations, avoiding the Von Neumann design.  These have fallen out of vogue (for parallel computing) by the '80s after sequential performance rose exponentially. However, a lot of parallel programming systems such as Google MapReduce, Microsoft's Dryad or Intel's Concurrent Collections are in fact dataflow computational models.  At some point they represent computations as a graph and use that to guide execution.</p>

<p>By specifying parts of the models you get different categories and semantics for the dataflow model. What do you restrict the shape of the graph to: DAG (CnC, Dryad), tree (mapreduce), digraph?  Are there strict synchronization semantics (<a href="http://en.wikipedia.org/wiki/Lustre_programming_language">Lustre</a>, reactive programming]? Do you disallow recursion to be able to have a static schedule (StreaMIT) or do you provide more expressive power by having a dynamic scheduler (Intel CnC)? Is there a limit on the number of incoming or outgoing edges? Do the firing semantics allow firing the node when a subset of the incoming data is available? Are edges streams of data (stream processing) or single data tokens (static/dynamic single assignment). For related work you could start by looking at the dataflow research work of people like Arvind, K. Kavi, j. Sharp, W. Ackerman, R. Jagannathan, etc.</p>

<p><strong>Edit: For the sake of completeness.</strong> I should point out there are also parallel <strong>reduction-driven</strong> and <strong>pattern-driven</strong> models. For the reduction strategies you broadly have graph-reduction and string-reduction. Haskell basically uses graph-reduction, which is a very efficient strategy on a sequential shared-memory system. String-reduction duplicates work, but has a private-memory property that makes it better suited to being implicitly parallelized. The pattern-driven models are the parallel logic languages, such as concurrent prolog. The Actor model is also a pattern-driven model, but with private memory characteristics.</p>

<p>PS. I use the term 'model' broadly, covering abstract machines for both formal and programming purposes.</p>

CC BY-SA 3.0
2011-04-15T20:11:39.537Z
I don't understand how mapreduce forms a tree.  Could you explain?
Riko Jacob
CC BY-SA 3.0
2011-04-17T12:12:40.110Z
@Riko Jacob, lets say you map '+' to (1 2 3 4), conceptually this creates an application tree with '+' at each node and each number as leaves. reduce (or fold if you're from haskel) will collapse each node with the data from its children.
Beef
CC BY-SA 3.0
2011-04-18T20:26:56.600Z
Hm. I understand that the data-flow can be a tree. 
Why is it always a tree? Say input "a,b" gets mapped, a to (x,1),(y,2), b to (x,2), (y,5), and then reduced with '+', such that the result is (x,3) and (y,7).  In this example the connections between both inputs to both outputs, which is a $K_{2,2}$ which is not a tree.
Riko Jacob
CC BY-SA 3.0
2011-04-19T10:56:24.200Z
If you do not factor in the creation of the graph itself (e.g. mapping a,b to the key/vale pairs) you get two trees doing the reduction, with a bit of goodwill :)  Maybe it's more a k-connected or lattice graph as you said.
You're right that it is a bit more general than a simple tree. I was trying to make a distinction with more general DAG dataflow structures.
Beef
CC BY-SA 3.0
2011-04-15T14:29:54.307Z
2011-05-04T11:47:17.917Z
2011-05-04T11:47:17.917Z
Beef
<p>For message-passing architectures, a model which is quite similar to BSP but easier to deal with and with performance analysis close to what you really get on a real machine is certainly CGM or Coarse Grained Multicomputer. It was proposed by Frank Dehne, and you will find many interesting papers presenting algorithms developed in this context.</p>

<p>CGM fits coarse-grained architectures assuming p processors, each one with O(n/p) local memory and the size of the input n much larger (orders of magnitude apart) than p, i.e. p≪n. Therefore, the model maps much better than others on current architectures; it has been studied extensively.
The model is based on the following assumptions: (i) the algorithms execute so-called supersteps, that consist of one phase of local computation and one phase of interprocessor communication with intermediate barrier synchronization, (ii) all of the p processors have access to O(n/p) local memory, (iii) in each superstep, a processor can send and receive at most O(n/p) elements and (iv) the communication network between the processors can be arbitrary. In this model, an algorithm is evaluated w.r.t. its computation time and number of communication rounds.
Although the model is simple, nevertheless it provides a reasonable prediction of the actual performances of parallel algorithms; indeed, parallel algorithms for CGMs usually have a theoretical complexity analysis very close to the actual times determined experimentally when implementing and benchmarking them.</p>

CC BY-SA 3.0
2011-04-15T05:51:57.253Z
2011-04-15T05:51:57.253Z
Massimo Cafaro
<p><a href="http://dx.doi.org/10.1145/1378533.1378573" rel="nofollow" title="PEM">Parallel External Memory (PEM)</a> is a natural combination of a PRAM-style  shared memory machine with the external memory model.  It focuses on the implications of private caches.</p>

CC BY-SA 3.0
2011-04-15T20:35:24.233Z
2011-04-15T20:35:24.233Z
Riko Jacob
<p>From what i know, The BSP and LogP models are used today for distributed algorithms. Also, since GPU computing, the PRAM as become again popular, however one should include the memory hierarchies in the analysis.
You can check the UPMH model (Uniform Parallel memory hierarchy) which complements nicely to PRAM.  </p>

<p><em>B. Alpern, L. Carter, E. Feig, and T. Selker. The uniform memory hierarchy model of
computation. Algorithmica, 12:72–109, 1994. 10.1007/BF01185206.</em></p>

<p><em>Bowen Alpern, Larry Carter, and Jeanne Ferrante. Modeling parallel computers as memory
hierarchies. In In Proc. Programming Models for Massively Parallel Computers, pages 116–
123. IEEE Computer Society Press, 1993.</em></p>

<p>Also for GPU computing, there has been a proposal for a theoretical computing model; the K-model:</p>

<p><em>Gabriele Capannini, Fabrizio Silvestri, and Ranieri Baraglia. K-model: A new computational
model for stream processors. In Proceedings of the 2010 IEEE 12th International Conference
on High Performance Computing and Communications, HPCC ’10, pages 239–246, Washing-
ton, DC, USA, 2010. IEEE Computer Society.</em></p>

<p>Lastly, i've seen cellular automata (CA) modelled as parallel computers, personally i think this is a very interesting research topic. Who knows in the future processors will be made this way, like little spaces of computation. I do not have a solid reference for this, you can look in the web.</p>

CC BY-SA 3.0
2012-07-27T15:50:23.330Z
2012-07-27T16:10:09.483Z
2012-07-27T16:10:09.483Z
labotsirc
<p>Purely functional programs allow parallel execution of independent expressions.
Hence, I would count them as parallel models of computation.</p>

CC BY-SA 3.0
2011-04-16T08:18:27.643Z
There's no particular cost-model assocaited with functional programming, so this doesn't answer the question.  See http://cstheory.stackexchange.com/questions/376/using-lambda-calculus-to-derive-time-complexity/
Charles Stewart
CC BY-SA 3.0
2011-04-17T12:20:06.567Z
The evaluation mechanism for such lambda-calculus based languages is reduction, which doesn't really have a direct mapping to actual hardware. This is why Haskell still has to introduce explicit parallel constructs like 'par'.  reference: http://csg.csail.mit.edu/projects/languages/ph.shtml
Beef
CC BY-SA 3.0
2011-04-15T20:25:44.743Z
2011-04-15T20:25:44.743Z
Riko Jacob
<p>I prefer the <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.22&amp;rep=rep1&amp;type=pdf" rel="nofollow">Bader-Jaja approach</a> (see section 2.1). You model complexity as a message passing problem. For each message sent there is both a variable for latency to initiate the communication and a variable for bandwidth.</p>

<p>Let $t$ be latency, $u$ be bandwidth, $m$ be the message size, and $p$ be the number of processors. For most scalable networks the cost of broadcast is  O(($t$+$u$*$m$) log $p$).</p>

CC BY-SA 3.0
2011-05-06T20:54:20.153Z
2011-05-06T21:03:16.853Z
2011-05-06T21:03:16.853Z
Chad Brewbaker
<p>you mention Cloud computing specifically. there has been within just a few years intense innovation in this area with the <a href="http://aws.amazon.com/ec2/" rel="nofollow">Amazon elastic compute cloud,</a> the <a href="https://developers.google.com/appengine/" rel="nofollow">google app engine</a> &amp; various tools and their associated conceptual parallel processing "models".</p>

<p>special open source tools include google's <a href="http://en.wikipedia.org/wiki/MapReduce" rel="nofollow">Mapreduce</a>, Apache <a href="http://en.wikipedia.org/wiki/Hadoop" rel="nofollow">Hadoop,</a> and <a href="http://en.wikipedia.org/wiki/Hadoop" rel="nofollow">NoSQL</a> databases which are emerging as new, strong, widely-adapted standards in parallelization algorithm "best practices" and "design patterns". also <a href="http://en.wikipedia.org/wiki/Hadoop" rel="nofollow">memcacheD</a> is increasingly being used as an in-memory distributed database. an example of this is in use at Facebook described in a recent paper [1].</p>

<p>[1] <a href="http://gigaom2.files.wordpress.com/2011/07/facebook-tilera-whitepaper.pdf" rel="nofollow">Many core key-value store</a> by Berezecki et al </p>

CC BY-SA 3.0
2012-07-31T20:06:37.030Z
again. I ask for _models_ or parallel computation. Not tools. MapReduce is one such model. However Hadoop and NoSQL are not. Hadoop is a java-based reification of MapReduce. NoSQL is a model for relaxed key-stores from what I can tell.
Nicholas Mancuso
CC BY-SA 3.0
2012-07-31T22:02:19.920Z
MapReduce started as a tool and graduated to a model through widespread use/adoption. same with the others. Hadoop is not identical to MapReduce, but maybe similar. yes, I guess I was thrown off by Suresh's top-vote answer that included MapReduce ... people dont seem to care much about, or prefer not to discuss, actual software pkgs on this site...no matter how widely used.. even given that they inspire/crosspollinate/ _drive_ solid later theory as MapReduce did... my bad =(
vzn
CC BY-SA 3.0
2012-08-02T04:35:30.520Z
point is, you are not answering the question. the policy around here is that suggestions tangentially related to the question are not acceptable answers. if you don't like this policy, you could choose not to participate. if you had *actual ideas* about how to model a real-world parallel system, that would be more on topic (although still not an answer to the question asked)
Sasho Nikolov
CC BY-SA 3.0
2012-07-28T20:24:21.990Z
2012-07-28T20:24:21.990Z
vzn
<p>another angle on this. admittedly this could be regarded as somewhat obscure or fringe by some, but there is some work on parallelizing, in a general way, probabilistic algorithms, which are asserted to be somewhat naturally suited to parallelism.</p>

<p>see eg
<a href="http://www1.chapman.edu/~radenski/research/papers/parallel.pdf" rel="nofollow">Parallel Probabilistic Computations on a Cluster of Workstations</a> Radenski, Vann, Norris:</p>

<blockquote>
  <p>Probabilistic algorithms are computationally intensive approximate methods for solving
  intractable problems. Probabilistic algorithms are excellent candidates for cluster computations
  because they require little communication and synchronization. It is possible to specify a
  <b>common parallel control structure as a generic algorithm for probabilistic cluster computations.</b>
  Such a generic parallel algorithm can be glued together with domain-specific sequential
  algorithms in order to derive approximate parallel solutions for different intractable problems.
  In this paper we propose a generic algorithm for probabilistic computations on a cluster of
  workstations. We use this generic algorithm to derive specific parallel algorithms for two
  discrete optimization problems: the knapsack problem and the traveling salesperson problem.</p>
</blockquote>

<p>in case its not clear, the "common parallel control structure as a generic algorithm" referred to along with the probabilistic computation, and the overall conversion, is the "model".</p>

<p>it could be argued that probabilistic computation is not strictly classical computing or Turing complete. so note there is some work in tying classical with probabilistic computation also specifically in a parallel context eg</p>

<p><a href="http://dl.acm.org/citation.cfm?id=177724" rel="nofollow">Reasoning about probabilistic parallel programs</a> by Rao:</p>

<blockquote>
  <p>The use of randomization in the design and analysis of algorithms promises simple and efficient algorithms to difficult problems, some of which may not have a deterministic solution. This gain in simplicity, efficiency, and solvability results in a trade-off of the traditional notion of absolute correctness of algorithms for a more quantitative notion: correctness with a probability between 0 and 1. The addition of the notion of parallelism to the already unintuitive idea of randomization makes reasoning about probabilistic parallel programs all the more tortuous and difficult. In this paper we address the problem of specifying and deriving properties of probabilistic parallel programs that either hold deterministically or with probability 1.</p>
</blockquote>

<p>of course QM computing is highly similar to probabilistic computing (a nice ref that emphasizes this is <a href="http://people.cs.uchicago.edu/~fortnow/papers/quantview.pdf" rel="nofollow">One Complexity Theorist's View of Quantum Computing by Fortnow</a>) &amp; there is some hint these approaches might be extended there, eg in the work in parallel QM simulation.</p>

CC BY-SA 3.0
2012-08-01T22:58:49.530Z
2012-08-01T22:58:49.530Z
vzn
<p>this will be considered controversial by some, and even proponents of this angle will have to admit its in the early stages of research, but basically <b>quantum computing</b> seems to have many connections to parallelism and parallel computation. the references are right now scattered but an emerging theme can be seen by a determined researcher.</p>

<p>maybe the best connection is with <a href="http://en.wikipedia.org/wiki/Grover%27s_algorithm" rel="nofollow">Grovers search algorithm</a> which has recently been shown to be more general in the sense of being usable for speedup on most NP complete problems in general[5]. Grovers algorithm seems to have a strong analogy/connection with parallel database search algorithms. the best classical serial algorithms cannot meet the same performance but at least one authority recently argues that QM approaches for search actually do not outperform parallelized classical algorithms.[1]</p>

<p>further evidence are schemes that explicitly look at the parallelism in quantum search eg [2]. also quantum simulator(s) have been proposed that are based on parallel/distributed processing[3][4] and because the scheme fits well &amp; leads to efficient and tractable simulations (30 qubits are simulated in ref [3]), this conversion is surely not merely a coincidence and indicates a deeper bridge between parallel classical computing and QM computing, but probably so-far uncovered.</p>

<p>[1] <a href="http://web.eecs.umich.edu/~imarkov/pubs/jour/cise05-grov.pdf" rel="nofollow">Is quantum search practical?</a> by Viamontes et al</p>

<p>[2] <a href="http://pra.aps.org/abstract/PRA/v78/i1/e012303" rel="nofollow">Exact quantum search by parallel unitary discrimination schemes</a> by Wu/Dian</p>

<p>[3] <a href="http://arxiv.org/pdf/quant-ph/0201042.pdf" rel="nofollow">General purpose parallel simulator for quantum computing</a> by Niwa, Matsumoto, Imai.</p>

<p>[4] <a href="http://arxiv.org/pdf/1207.2307.pdf" rel="nofollow">efficient distributed quantum computing</a> by Beals et al 2012</p>

<p>[5] <a href="http://dl.acm.org/citation.cfm?id=1792918.1792985" rel="nofollow">Solving NP complete problems with quantum search</a> by Furer 2008</p>

CC BY-SA 3.0
2012-07-31T20:00:16.770Z
@vnz, this seems to be at best a random hodge-podge of concepts quantum. Googling "parallel quantum" and listing results here is of no use to me and to others reading this. I think it would be better for the community to actually respond to answers you feel comfortable with and knowledgeable of, rather than to just make a mad-dash for reputation points. It is nonconstructive and possibly disingenuous to think of quantum computation as parallel search. Quantum computation has, to use your description, "strong analogies/connections" with probabilistic search, not parallel.
Nicholas Mancuso
CC BY-SA 3.0
2012-07-31T20:42:06.100Z
I dont know what dogma is taught in classrooms but if somebody out there actually has a REFERENCE rather than mere BASELESS ASSERTIONS that indicates why there is no validity to a so-far uncovered correspondence of QM accomplishing parallel classical computation.... I will READ IT. QM computing returns precise answers ala/eg shor factoring otherwise it is not an actual computation system..... there are also other ways than I sketch to demonstrate that QM computing must be equivalent to parallel classical computing in some sense... maybe since its not in a textbook, it must be wrong huh!!
vzn
CC BY-SA 3.0
2012-07-31T20:49:26.010Z
There is an entire free course on quantum computing here: https://www.coursera.org/ it may clarify things for you.
Nicholas Mancuso
CC BY-SA 3.0
2012-07-31T20:52:02.357Z
ps as for "hodgepodge"... try actually READING THE REFS .. or maybe just skimming them in your case wink =)
vzn
CC BY-SA 3.0
2012-07-31T20:53:06.117Z
and what part of your course proves that QM cannot possibly be accomplishing parallel classical computation? I personally tend to prefer PAPERS or BOOKS rather than ONLINE COURSES for my proofs =)
vzn
CC BY-SA 3.0
2012-07-31T21:04:14.157Z
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/4339/discussion-between-nicholas-mancuso-and-vzn)
Nicholas Mancuso
CC BY-SA 3.0
2014-03-25T09:07:28.530Z
@vzn: For the sake of completeness (and in order to better support the comments I have made to you on cstheory and elsewhere), here are the critiques I would make with regards to your references. **(1.)** Grover's algorithm is no more parallel than a randomized computation: it does however transform things unitarily, allowing for destructive interference, which allows unproductive answers to be cancelled out. If the parallelism is there only to the extent that it *doesn't* allow you to obtain outcomes which were present in the interim, can those parallel processes be said to be there at all?
Niel de Beaudrap
CC BY-SA 3.0
2014-03-25T09:15:02.263Z
**(2.)** Your Ref.[1] is a popular article which does not make any serious claims that either Grover's algorithm or quantum computers generally perform parallel computation, except using the standard gloss of "quantum parallelism". But so-called "quantum parallelism" is just computation in superposition, which is available to classical computers as well (albeit using stochastic rather than unitary transformations). **(3.)** Your Ref.[2] considers quantum circuits which are "parallel" in that they perform operations on blocks of bits simultaneously, but doesn't address "quantum parallelism".
Niel de Beaudrap
CC BY-SA 3.0
2014-03-25T09:19:20.100Z
**(4.)** Your Ref.[3] describes a classical approach to simulating quantum computers, so it is the classical simulation which is parallel. This does not mean that the quantum computation is itself parallel, as the classical simulation is in a sense doing strictly more work than the quantum computation itself: the classical simulation works out transitions for individual "possible histories" which are not observed in the quantum computation as a physical process. **(5.)** Your Ref.[4] again concerns quantum computers which perform parallel operations on bits, and not "quantum parallelism".
Niel de Beaudrap
CC BY-SA 3.0
2014-03-25T09:24:37.237Z
**(6.)** Your Ref.[5] describes ways in which Grover's algorithm may be extended, again without addressing the parallelism that you seek for in quantum computation. **In summary:** your interpretation that there are connections between quantum and parallel computation seems to derive from the Many Worlds Interpretation of QM. While not obscure, it is also not uncontrovertial, and certainly does not allow us to productively describe quantum computation as "computation in parallel", except to the extent that we *don't* see those computations... which is not a strong argument for their presence.
Niel de Beaudrap
CC BY-SA 3.0
2014-03-25T15:59:02.247Z
@Niel thx for the additional comments which are relevant. this is a complex topic that is not amenable to se fmt & the chat room NM/I opened & wrote in got closed (did you see it?). conceded immed in answer to controversiality & admitted first comment _its a sketch_. it would seem its a topic of a "paper waiting to be written" eg by pro researcher (you? Nicholas?). it is interesting there seems to be neither any paper supporting or refuting the claim. see also further interest here, [QM computing/parallelism](http://cs.stackexchange.com/questions/12892/) cs.se. invite further [chat]
vzn
CC BY-SA 3.0
2014-04-03T22:00:48.543Z
see also [Can a parallel computer simulate a quantum computer? Is BQP inside NP?](http://physics.stackexchange.com/questions/34544/) physics.se
vzn
CC BY-SA 3.0
2012-07-28T20:09:07.017Z
2012-07-28T20:09:07.017Z
vzn
<p>There are a number of models floating around, but some of the most salient are:</p>

<ol>
<li>The <a href="http://arxiv.org/abs/cs.CC/0611108">MUD</a> and <a href="http://theory.stanford.edu/~sergei/papers/soda10-mrc.pdf">Mapreduce</a> models that are primarily about capturing the MapReduce framework, but more generally can be viewed as parallel-distributed models of computation</li>
<li>The various <a href="http://dimacs.rutgers.edu/Workshops/Parallel/abstracts.html#ramachandran">multicore models</a> that have been proposed (but by no means are the standard yet)</li>
</ol>

<p>There was a <a href="http://dimacs.rutgers.edu/Workshops/Parallel/program.html">workshop last month at DIMACS</a> on this topic: perusing the abstracts will give you more pointers. </p>

CC BY-SA 3.0
2011-04-15T05:17:46.760Z
The DIMACs workshop is brilliant! Thank you.
Nicholas Mancuso
CC BY-SA 3.0
2011-04-15T07:33:13.283Z
There was an earlier workshop in 2009 http://www.umiacs.umd.edu/conferences/tmc2009/ which seemed to me to be even more sharply honed than the recent DIMACs one.  Leslie Valiant introduced the Multi-BSP model there (discussed in more detail at this year's workshop), and Phil Gibbons from Intel presented a provocative talk _Theory: asleep at the switch to many-core_ that is worth looking at.  To me the DIMACs workshop was way too focused on MapReduce, which Google no longer uses for building their web index.
András Salamon
CC BY-SA 3.0
2011-04-15T08:33:35.497Z
that's true. I had forgotten about the earlier one.
Suresh Venkat
CC BY-SA 3.0
2011-04-15T05:07:23.967Z
2011-04-15T05:07:23.967Z
Suresh Venkat
<p>The 1980's gave rise to both the <a href="http://en.wikipedia.org/wiki/Parallel_Random_Access_Machine">PRAM</a> and the <a href="http://en.wikipedia.org/wiki/Bulk_synchronous_parallel">BSP</a> models of parallel computation. It seems that both model's heyday were during the late 80s and early 90s.</p>

<p>Are these areas still active in terms of research for parallel algorithms? Are there newer more sophisticated models for parallel computation? Are general models still in vogue, or are researchers trying to specialize with GPGPU or Cloud based computation coming in fashion?</p>

<ds.algorithms><dc.parallel-comp><dc.distributed-comp>
Current parallel models for computation
Nicholas Mancuso
# Current parallel models for computation

(Asked by: username_0 on 2011-04-15)

The 1980's gave rise to both the [PRAM](http://en.wikipedia.org/wiki/Parallel_Random_Access_Machine) and the [BSP](http://en.wikipedia.org/wiki/Bulk_synchronous_parallel) models of parallel computation. It seems that both model's heyday were during the late 80s and early 90s.

Are these areas still active in terms of research for parallel algorithms? Are there newer more sophisticated models for parallel computation? Are general models still in vogue, or are researchers trying to specialize with GPGPU or Cloud based computation coming in fashion?

**Tags:** ds.algorithms, dc.parallel-comp, dc.distributed-comp

---

## 10 answers

### Answer by username_10 on 2011-04-15. Score: 19 | Accepted answer

There are a number of models floating around, but some of the most salient are:

1. The [MUD](http://arxiv.org/abs/cs.CC/0611108) and [Mapreduce](http://theory.stanford.edu/~sergei/papers/soda10-mrc.pdf) models that are primarily about capturing the MapReduce framework, but more generally can be viewed as parallel-distributed models of computation
2. The various [multicore models](http://dimacs.rutgers.edu/Workshops/Parallel/abstracts.html#ramachandran) that have been proposed (but by no means are the standard yet)

There was a [workshop last month at DIMACS](http://dimacs.rutgers.edu/Workshops/Parallel/program.html) on this topic: perusing the abstracts will give you more pointers.

> **Comments:**
> **username_0**: The DIMACs workshop is brilliant! Thank you.  
> **username_11**: There was an earlier workshop in 2009 http://www.umiacs.umd.edu/conferences/tmc2009/ which seemed to me to be even more sharply honed than the recent DIMACs one.  Leslie Valiant introduced the Multi-BSP model there (discussed in more detail at this year's workshop), and Phil Gibbons from Intel presented a provocative talk _Theory: asleep at the switch to many-core_ that is worth looking at.  To me the DIMACs workshop was way too focused on MapReduce, which Google no longer uses for building their web index.  
> **username_10**: that's true. I had forgotten about the earlier one.  

---

### Answer by username_1 on 2011-04-15. Score: 22

I apologize beforehand for the blog-post format of my answer. I couldn't help myself making a small overview of the parallel computing world.

You can categorize parallel programming models in roughly two categories: control-flow and data-flow models.

The **control-flow models** try to make parallelism work within the context of a explicit-control program, basically every programmable computer today. The fundamental problem being tackled is that such a 'Von Neumann architecture' was not designed for parallel execution, but efficient sequential computations. Parallelism in such context is obtained by duplicating parts of the basic modules (memory, control, arithmetic).

Duplicating only arithmetic gives you SIMD instructions, all ALUs share the same Program Counter (PC) and thus always execute the same operation in parallel, albeit on different data.

Duplicating ALU and the PC but keeping the instruction sequencer inside the control unit gives you Out of Order (OoO) execution that yield some pipeline-parallelism. In this category you also have the Very Long Instruction Word (VLWI) and branche-prediction techniques. You rarely see this category at a software level though.

Going a bit further is duplicating the whole 'core' but keeping the memory shared, these are the current multicore processors that give you task (or thread) parallelism. Sharing memory in this context gives you very, [very hard and subtle concurrency issues](http://lambda-the-ultimate.org/node/4211). Parallel computations on current multicore are thus completely revolving around synchronization/concurrency problems, the careful balance of performance (no sync) and desired semantics (totally synchronized, sequential execution semantics). Examples of this is the PRAM or more popular these days the [Cilk](http://supertech.csail.mit.edu/cilk/) ofshoots such as fork/join ([IntelTBB](http://threadingbuildingblocks.org/), [Java.Utils.Concurrency](http://download.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html)). CSP and Actor models are concurrency models, but as mentioned above concurrency and parallelism become blurred in a shared-memory environment. n.b. parallelism is for performance, concurrency to maintain correct semantics.

Duplicating memory too gives you either networked computers that get programmed with MPI and its ilk or just strange non-Von Neumann architectures such as the network-on-a-chip processors (cloud processor, the Transputer, Tilera). Memory models such as [UMA](http://en.wikipedia.org/wiki/Uniform_Memory_Access) or [NUMA](http://en.wikipedia.org/wiki/Non-Uniform_Memory_Access) try to maintain the illusion of shared memory and can exist on either software or hardware level. MPI maintains the program-level parallelism and only communicates via message passing. Message passing is also used on a hardware level for communication and concurrency (Transputer).

The second category are **data-flow models**. These were designed at the dawn of the computer age as a way to write down and execute parallel computations, avoiding the Von Neumann design. These have fallen out of vogue (for parallel computing) by the '80s after sequential performance rose exponentially. However, a lot of parallel programming systems such as Google MapReduce, Microsoft's Dryad or Intel's Concurrent Collections are in fact dataflow computational models. At some point they represent computations as a graph and use that to guide execution.

By specifying parts of the models you get different categories and semantics for the dataflow model. What do you restrict the shape of the graph to: DAG (CnC, Dryad), tree (mapreduce), digraph? Are there strict synchronization semantics ([Lustre](http://en.wikipedia.org/wiki/Lustre_programming_language), reactive programming]? Do you disallow recursion to be able to have a static schedule (StreaMIT) or do you provide more expressive power by having a dynamic scheduler (Intel CnC)? Is there a limit on the number of incoming or outgoing edges? Do the firing semantics allow firing the node when a subset of the incoming data is available? Are edges streams of data (stream processing) or single data tokens (static/dynamic single assignment). For related work you could start by looking at the dataflow research work of people like Arvind, K. Kavi, j. Sharp, W. Ackerman, R. Jagannathan, etc.

**Edit: For the sake of completeness.** I should point out there are also parallel **reduction-driven** and **pattern-driven** models. For the reduction strategies you broadly have graph-reduction and string-reduction. Haskell basically uses graph-reduction, which is a very efficient strategy on a sequential shared-memory system. String-reduction duplicates work, but has a private-memory property that makes it better suited to being implicitly parallelized. The pattern-driven models are the parallel logic languages, such as concurrent prolog. The Actor model is also a pattern-driven model, but with private memory characteristics.

PS. I use the term 'model' broadly, covering abstract machines for both formal and programming purposes.

> **Comments:**
> **username_2**: I don't understand how mapreduce forms a tree.  Could you explain?  
> **username_1**: @Riko Jacob, lets say you map '+' to (1 2 3 4), conceptually this creates an application tree with '+' at each node and each number as leaves. reduce (or fold if you're from haskel) will collapse each node with the data from its children.  
> **username_2**: Hm. I understand that the data-flow can be a tree.  Why is it always a tree? Say input "a,b" gets mapped, a to (x,1),(y,2), b to (x,2), (y,5), and then reduced with '+', such that the result is (x,3) and (y,7).  In this example the connections between both inputs to both outputs, which is a $K_{2,2}$ which is not a tree.  
> **username_1**: If you do not factor in the creation of the graph itself (e.g. mapping a,b to the key/vale pairs) you get two trees doing the reduction, with a bit of goodwill :)  Maybe it's more a k-connected or lattice graph as you said. You're right that it is a bit more general than a simple tree. I was trying to make a distinction with more general DAG dataflow structures.  

---

### Answer by username_3 on 2011-04-15. Score: 8

For message-passing architectures, a model which is quite similar to BSP but easier to deal with and with performance analysis close to what you really get on a real machine is certainly CGM or Coarse Grained Multicomputer. It was proposed by Frank Dehne, and you will find many interesting papers presenting algorithms developed in this context.

CGM fits coarse-grained architectures assuming p processors, each one with O(n/p) local memory and the size of the input n much larger (orders of magnitude apart) than p, i.e. p≪n. Therefore, the model maps much better than others on current architectures; it has been studied extensively.
The model is based on the following assumptions: (i) the algorithms execute so-called supersteps, that consist of one phase of local computation and one phase of interprocessor communication with intermediate barrier synchronization, (ii) all of the p processors have access to O(n/p) local memory, (iii) in each superstep, a processor can send and receive at most O(n/p) elements and (iv) the communication network between the processors can be arbitrary. In this model, an algorithm is evaluated w.r.t. its computation time and number of communication rounds.
Although the model is simple, nevertheless it provides a reasonable prediction of the actual performances of parallel algorithms; indeed, parallel algorithms for CGMs usually have a theoretical complexity analysis very close to the actual times determined experimentally when implementing and benchmarking them.


---

### Answer by username_2 on 2011-04-15. Score: 4

[Parallel External Memory (PEM)](http://dx.doi.org/10.1145/1378533.1378573 "PEM") is a natural combination of a PRAM-style shared memory machine with the external memory model. It focuses on the implications of private caches.


---

### Answer by username_4 on 2012-07-27. Score: 4

From what i know, The BSP and LogP models are used today for distributed algorithms. Also, since GPU computing, the PRAM as become again popular, however one should include the memory hierarchies in the analysis.
You can check the UPMH model (Uniform Parallel memory hierarchy) which complements nicely to PRAM.

*B. Alpern, L. Carter, E. Feig, and T. Selker. The uniform memory hierarchy model of
computation. Algorithmica, 12:72–109, 1994. 10.1007/BF01185206.*

*Bowen Alpern, Larry Carter, and Jeanne Ferrante. Modeling parallel computers as memory
hierarchies. In In Proc. Programming Models for Massively Parallel Computers, pages 116–
123. IEEE Computer Society Press, 1993.*

Also for GPU computing, there has been a proposal for a theoretical computing model; the K-model:

*Gabriele Capannini, Fabrizio Silvestri, and Ranieri Baraglia. K-model: A new computational
model for stream processors. In Proceedings of the 2010 IEEE 12th International Conference
on High Performance Computing and Communications, HPCC ’10, pages 239–246, Washing-
ton, DC, USA, 2010. IEEE Computer Society.*

Lastly, i've seen cellular automata (CA) modelled as parallel computers, personally i think this is a very interesting research topic. Who knows in the future processors will be made this way, like little spaces of computation. I do not have a solid reference for this, you can look in the web.


---

### Answer by username_2 on 2011-04-15. Score: 3

Purely functional programs allow parallel execution of independent expressions.
Hence, I would count them as parallel models of computation.

> **Comments:**
> **username_5**: There's no particular cost-model assocaited with functional programming, so this doesn't answer the question.  See http://cstheory.stackexchange.com/questions/376/using-lambda-calculus-to-derive-time-complexity/  
> **username_1**: The evaluation mechanism for such lambda-calculus based languages is reduction, which doesn't really have a direct mapping to actual hardware. This is why Haskell still has to introduce explicit parallel constructs like 'par'.  reference: http://csg.csail.mit.edu/projects/languages/ph.shtml  

---

### Answer by username_6 on 2011-05-06. Score: 3

I prefer the [Bader-Jaja approach](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.22&rep=rep1&type=pdf) (see section 2.1). You model complexity as a message passing problem. For each message sent there is both a variable for latency to initiate the communication and a variable for bandwidth.

Let $t$ be latency, $u$ be bandwidth, $m$ be the message size, and $p$ be the number of processors. For most scalable networks the cost of broadcast is O(($t$+$u$\*$m$) log $p$).


---

### Answer by username_7 on 2012-07-28. Score: -3

you mention Cloud computing specifically. there has been within just a few years intense innovation in this area with the [Amazon elastic compute cloud,](http://aws.amazon.com/ec2/) the [google app engine](https://developers.google.com/appengine/) & various tools and their associated conceptual parallel processing "models".

special open source tools include google's [Mapreduce](http://en.wikipedia.org/wiki/MapReduce), Apache [Hadoop,](http://en.wikipedia.org/wiki/Hadoop) and [NoSQL](http://en.wikipedia.org/wiki/Hadoop) databases which are emerging as new, strong, widely-adapted standards in parallelization algorithm "best practices" and "design patterns". also [memcacheD](http://en.wikipedia.org/wiki/Hadoop) is increasingly being used as an in-memory distributed database. an example of this is in use at Facebook described in a recent paper [1].

[1] [Many core key-value store](http://gigaom2.files.wordpress.com/2011/07/facebook-tilera-whitepaper.pdf) by Berezecki et al

> **Comments:**
> **username_0**: again. I ask for _models_ or parallel computation. Not tools. MapReduce is one such model. However Hadoop and NoSQL are not. Hadoop is a java-based reification of MapReduce. NoSQL is a model for relaxed key-stores from what I can tell.  
> **username_7**: MapReduce started as a tool and graduated to a model through widespread use/adoption. same with the others. Hadoop is not identical to MapReduce, but maybe similar. yes, I guess I was thrown off by Suresh's top-vote answer that included MapReduce ... people dont seem to care much about, or prefer not to discuss, actual software pkgs on this site...no matter how widely used.. even given that they inspire/crosspollinate/ _drive_ solid later theory as MapReduce did... my bad =(  
> **username_8**: point is, you are not answering the question. the policy around here is that suggestions tangentially related to the question are not acceptable answers. if you don't like this policy, you could choose not to participate. if you had *actual ideas* about how to model a real-world parallel system, that would be more on topic (although still not an answer to the question asked)  

---

### Answer by username_7 on 2012-08-01. Score: -3

another angle on this. admittedly this could be regarded as somewhat obscure or fringe by some, but there is some work on parallelizing, in a general way, probabilistic algorithms, which are asserted to be somewhat naturally suited to parallelism.

see eg
[Parallel Probabilistic Computations on a Cluster of Workstations](http://www1.chapman.edu/~radenski/research/papers/parallel.pdf) Radenski, Vann, Norris:

> Probabilistic algorithms are computationally intensive approximate methods for solving
> intractable problems. Probabilistic algorithms are excellent candidates for cluster computations
> because they require little communication and synchronization. It is possible to specify a
> **common parallel control structure as a generic algorithm for probabilistic cluster computations.**
> Such a generic parallel algorithm can be glued together with domain-specific sequential
> algorithms in order to derive approximate parallel solutions for different intractable problems.
> In this paper we propose a generic algorithm for probabilistic computations on a cluster of
> workstations. We use this generic algorithm to derive specific parallel algorithms for two
> discrete optimization problems: the knapsack problem and the traveling salesperson problem.

in case its not clear, the "common parallel control structure as a generic algorithm" referred to along with the probabilistic computation, and the overall conversion, is the "model".

it could be argued that probabilistic computation is not strictly classical computing or Turing complete. so note there is some work in tying classical with probabilistic computation also specifically in a parallel context eg

[Reasoning about probabilistic parallel programs](http://dl.acm.org/citation.cfm?id=177724) by Rao:

> The use of randomization in the design and analysis of algorithms promises simple and efficient algorithms to difficult problems, some of which may not have a deterministic solution. This gain in simplicity, efficiency, and solvability results in a trade-off of the traditional notion of absolute correctness of algorithms for a more quantitative notion: correctness with a probability between 0 and 1. The addition of the notion of parallelism to the already unintuitive idea of randomization makes reasoning about probabilistic parallel programs all the more tortuous and difficult. In this paper we address the problem of specifying and deriving properties of probabilistic parallel programs that either hold deterministically or with probability 1.

of course QM computing is highly similar to probabilistic computing (a nice ref that emphasizes this is [One Complexity Theorist's View of Quantum Computing by Fortnow](http://people.cs.uchicago.edu/~fortnow/papers/quantview.pdf)) & there is some hint these approaches might be extended there, eg in the work in parallel QM simulation.


---

### Answer by username_7 on 2012-07-28. Score: -6

this will be considered controversial by some, and even proponents of this angle will have to admit its in the early stages of research, but basically **quantum computing** seems to have many connections to parallelism and parallel computation. the references are right now scattered but an emerging theme can be seen by a determined researcher.

maybe the best connection is with [Grovers search algorithm](http://en.wikipedia.org/wiki/Grover%27s_algorithm) which has recently been shown to be more general in the sense of being usable for speedup on most NP complete problems in general[5]. Grovers algorithm seems to have a strong analogy/connection with parallel database search algorithms. the best classical serial algorithms cannot meet the same performance but at least one authority recently argues that QM approaches for search actually do not outperform parallelized classical algorithms.[1]

further evidence are schemes that explicitly look at the parallelism in quantum search eg [2]. also quantum simulator(s) have been proposed that are based on parallel/distributed processing[3][4] and because the scheme fits well & leads to efficient and tractable simulations (30 qubits are simulated in ref [3]), this conversion is surely not merely a coincidence and indicates a deeper bridge between parallel classical computing and QM computing, but probably so-far uncovered.

[1] [Is quantum search practical?](http://web.eecs.umich.edu/~imarkov/pubs/jour/cise05-grov.pdf) by Viamontes et al

[2] [Exact quantum search by parallel unitary discrimination schemes](http://pra.aps.org/abstract/PRA/v78/i1/e012303) by Wu/Dian

[3] [General purpose parallel simulator for quantum computing](http://arxiv.org/pdf/quant-ph/0201042.pdf) by Niwa, Matsumoto, Imai.

[4] [efficient distributed quantum computing](http://arxiv.org/pdf/1207.2307.pdf) by Beals et al 2012

[5] [Solving NP complete problems with quantum search](http://dl.acm.org/citation.cfm?id=1792918.1792985) by Furer 2008

> **Comments:**
> **username_0**: @vnz, this seems to be at best a random hodge-podge of concepts quantum. Googling "parallel quantum" and listing results here is of no use to me and to others reading this. I think it would be better for the community to actually respond to answers you feel comfortable with and knowledgeable of, rather than to just make a mad-dash for reputation points. It is nonconstructive and possibly disingenuous to think of quantum computation as parallel search. Quantum computation has, to use your description, "strong analogies/connections" with probabilistic search, not parallel.  
> **username_7**: I dont know what dogma is taught in classrooms but if somebody out there actually has a REFERENCE rather than mere BASELESS ASSERTIONS that indicates why there is no validity to a so-far uncovered correspondence of QM accomplishing parallel classical computation.... I will READ IT. QM computing returns precise answers ala/eg shor factoring otherwise it is not an actual computation system..... there are also other ways than I sketch to demonstrate that QM computing must be equivalent to parallel classical computing in some sense... maybe since its not in a textbook, it must be wrong huh!!  
> **username_0**: There is an entire free course on quantum computing here: https://www.coursera.org/ it may clarify things for you.  
> **username_7**: ps as for "hodgepodge"... try actually READING THE REFS .. or maybe just skimming them in your case wink =)  
> **username_7**: and what part of your course proves that QM cannot possibly be accomplishing parallel classical computation? I personally tend to prefer PAPERS or BOOKS rather than ONLINE COURSES for my proofs =)  
> **username_0**: let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/4339/discussion-between-nicholas-mancuso-and-vzn)  
> **username_9**: @vzn: For the sake of completeness (and in order to better support the comments I have made to you on cstheory and elsewhere), here are the critiques I would make with regards to your references. **(1.)** Grover's algorithm is no more parallel than a randomized computation: it does however transform things unitarily, allowing for destructive interference, which allows unproductive answers to be cancelled out. If the parallelism is there only to the extent that it *doesn't* allow you to obtain outcomes which were present in the interim, can those parallel processes be said to be there at all?  
> **username_9**: **(2.)** Your Ref.[1] is a popular article which does not make any serious claims that either Grover's algorithm or quantum computers generally perform parallel computation, except using the standard gloss of "quantum parallelism". But so-called "quantum parallelism" is just computation in superposition, which is available to classical computers as well (albeit using stochastic rather than unitary transformations). **(3.)** Your Ref.[2] considers quantum circuits which are "parallel" in that they perform operations on blocks of bits simultaneously, but doesn't address "quantum parallelism".  
> **username_9**: **(4.)** Your Ref.[3] describes a classical approach to simulating quantum computers, so it is the classical simulation which is parallel. This does not mean that the quantum computation is itself parallel, as the classical simulation is in a sense doing strictly more work than the quantum computation itself: the classical simulation works out transitions for individual "possible histories" which are not observed in the quantum computation as a physical process. **(5.)** Your Ref.[4] again concerns quantum computers which perform parallel operations on bits, and not "quantum parallelism".  
> **username_9**: **(6.)** Your Ref.[5] describes ways in which Grover's algorithm may be extended, again without addressing the parallelism that you seek for in quantum computation. **In summary:** your interpretation that there are connections between quantum and parallel computation seems to derive from the Many Worlds Interpretation of QM. While not obscure, it is also not uncontrovertial, and certainly does not allow us to productively describe quantum computation as "computation in parallel", except to the extent that we *don't* see those computations... which is not a strong argument for their presence.  
> **username_7**: @Niel thx for the additional comments which are relevant. this is a complex topic that is not amenable to se fmt & the chat room NM/I opened & wrote in got closed (did you see it?). conceded immed in answer to controversiality & admitted first comment _its a sketch_. it would seem its a topic of a "paper waiting to be written" eg by pro researcher (you? Nicholas?). it is interesting there seems to be neither any paper supporting or refuting the claim. see also further interest here, [QM computing/parallelism](http://cs.stackexchange.com/questions/12892/) cs.se. invite further [chat]  
> **username_7**: see also [Can a parallel computer simulate a quantum computer? Is BQP inside NP?](http://physics.stackexchange.com/questions/34544/) physics.se  

---

