Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

The 1980's gave rise to both the PRAM and the BSP 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?

share|improve this question

10 Answers 10

up vote 18 down vote accepted

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

  1. The MUD and Mapreduce 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 that have been proposed (but by no means are the standard yet)

There was a workshop last month at DIMACS on this topic: perusing the abstracts will give you more pointers.

share|improve this answer
    
The DIMACs workshop is brilliant! Thank you. –  Nicholas Mancuso Apr 15 '11 at 5:17
2  
There was an earlier workshop in 2009 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 Apr 15 '11 at 7:33
    
that's true. I had forgotten about the earlier one. –  Suresh Venkat Apr 15 '11 at 8:33

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. 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 ofshoots such as fork/join (IntelTBB, Java.Utils.Concurrency). 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 or NUMA 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, 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.

share|improve this answer
    
I don't understand how mapreduce forms a tree. Could you explain? –  Riko Jacob Apr 15 '11 at 20:11
    
@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 Apr 17 '11 at 12:12
    
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 Apr 18 '11 at 20:26
    
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 Apr 19 '11 at 10:56

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.

share|improve this answer

Parallel External Memory (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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
There's no particular cost-model assocaited with functional programming, so this doesn't answer the question. See cstheory.stackexchange.com/questions/376/… –  Charles Stewart Apr 16 '11 at 8:18
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: csg.csail.mit.edu/projects/languages/ph.shtml –  Beef Apr 17 '11 at 12:20

I prefer the Bader-Jaja approach (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$).

share|improve this answer

you mention Cloud computing specifically. there has been within just a few years intense innovation in this area with the Amazon elastic compute cloud, the google app engine & various tools and their associated conceptual parallel processing "models".

special open source tools include google's Mapreduce, Apache Hadoop, and NoSQL databases which are emerging as new, strong, widely-adapted standards in parallelization algorithm "best practices" and "design patterns". also memcacheD 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 by Berezecki et al

share|improve this answer
    
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 Jul 31 '12 at 20:06
    
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 Jul 31 '12 at 22:02
1  
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 Aug 2 '12 at 4:35

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 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 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) & there is some hint these approaches might be extended there, eg in the work in parallel QM simulation.

share|improve this answer

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 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? by Viamontes et al

[2] Exact quantum search by parallel unitary discrimination schemes by Wu/Dian

[3] General purpose parallel simulator for quantum computing by Niwa, Matsumoto, Imai.

[4] efficient distributed quantum computing by Beals et al 2012

[5] Solving NP complete problems with quantum search by Furer 2008

share|improve this answer
    
@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 Jul 31 '12 at 20:00
    
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 Jul 31 '12 at 20:42
    
There is an entire free course on quantum computing here: coursera.org it may clarify things for you. –  Nicholas Mancuso Jul 31 '12 at 20:49
    
ps as for "hodgepodge"... try actually READING THE REFS .. or maybe just skimming them in your case wink =) –  vzn Jul 31 '12 at 20:52
    
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 Jul 31 '12 at 20:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.