Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
There are a number of models floating around, but some of the most salient are:
There was a workshop last month at DIMACS on this topic: perusing the abstracts will give you more pointers.
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.
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.
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.
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.
Purely functional programs allow parallel execution of independent expressions. Hence, I would count them as parallel models of computation.
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$).
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
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.
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
