A parallel programming model is a concept that enables the expression of parallel programs which can be compiled and executed. The value of a programming model is usually judged on its generality: how well a range of different problems can be expressed and how well they execute on a range of different architectures. The implementation of a programming model can take several forms such as libraries invoked from traditional sequential languages, language extensions, or complete new execution models.

Consensus on a particular programming model is important as it enables software expressed within it to be transportable between different architectures. The von Neumann model has facilitated this with sequential architectures as it provides an efficient bridge between hardware and software, meaning that high-level languages can be efficiently compiled to it and it can be efficiently implemented in hardware.

Main classifications and paradigms

Classifications of parallel programming models can be divided broadly into two areas: process interaction and problem decomposition.

Process interaction

Process interaction relates to the mechanisms by which parallel processes are able to communicate with each other. The most common forms of interaction are shared memory and message passing, but it can also be implicit.

Shared memory

In a shared memory model, parallel tasks share a global address space which they read and write to asynchronously. This requires protection mechanisms such as locks and semaphores to control concurrent access. Shared memory can be
emulated on distributed-memory systems but non-uniform memory access (NUMA) times can come in to play.

Message passing

In a message passing model, parallel tasks exchange data through passing messages to one another. These communications can be asynchronous or synchronous. The Communicating Sequential Processes (CSP) formalisation of message-passing employed communication channels to 'connect' processes, and led to a number of important languages such as Joyce, occam and Erlang.

Implicit

In an implicit model, no process interaction is visible to the programmer, instead the compiler and/or runtime is responsible for performing it. This is most common with domain-specific languages where the concurrency within a problem can be more prescribed.

Problem decomposition

Any parallel program is composed of simultaneously executing processes, problem decomposition relates to the way in which these processes are formulated. This classification may also be referred to as algorithmic skeleton

Algorithmic skeleton

In computing, algorithmic skeletons are a high-level parallel programming model for parallel and distributed computing....

s or parallel programming paradigms.

Task parallelism

A task-parallel model focuses on processes, or threads of execution. These processes will often be behaviourally distinct, which emphasises the need for communication. Task parallelism is a natural way to express message-passing communication. It is usually classified as MIMD/MPMD or MISD.

Data parallelism

A data-parallel model focuses on performing operations on a data set which is usually regularly structured in an array. A set of tasks will operate on this data, but independently on separate partitions. In a shared memory system, the data will be accessible to all, but in a distributed-memory system it will divided between memories and worked on locally. Data parallelism is usually classified as SIMD/SPMP.

Implicit

As with implicit process interaction, an implicit model of parallelism reveals nothing to the programmer as the compiler and/or the runtime is responsible.

Example parallel programming models

• Algorithmic Skeletons
  Algorithmic skeleton
  In computing, algorithmic skeletons are a high-level parallel programming model for parallel and distributed computing....
  
  
• Components
• Distributed Objects
• Remote Method Invocation
• Workflows
• Parallel Random Access Machine
  Parallel Random Access Machine
  In computer science, Parallel Random Access Machine is a shared memory abstract machine. As its name indicates, the PRAM was intended as the parallel computing analogy to the random access machine...
  
  
• Stream processing
  Stream processing
  Stream processing is a computer programming paradigm, related to SIMD , that allows some applications to more easily exploit a limited form of parallel processing...
  
  
• Bulk synchronous parallelism
  Bulk synchronous parallel
  The Bulk Synchronous Parallel abstract computer is a bridging model for designing parallel algorithms. A bridging model "is intended neither as a hardware nor a programming model but something in between" . It serves a purpose similar to the Parallel Random Access Machine model. BSP differs from...
  
  

See also

• List of concurrent and parallel programming languages
• Bridging model
  Bridging model
  In computer science, a bridging model is an abstract model of a computer which provides a conceptual bridge between the physical implementation of the machine and the abstraction available to a programmer of that machine; in other words, it is intended to provide a common level of understanding...
  
  
• Concurrency
  Concurrent computing
  Concurrent computing is a form of computing in which programs are designed as collections of interacting computational processes that may be executed in parallel...
  
  
• Automatic parallelization
  Automatic parallelization
  Automatic parallelization, also auto parallelization, autoparallelization, or parallelization, the last one of which implies automation when used in context, refers to converting sequential code into multi-threaded or vectorized code in order to utilize multiple processors simultaneously in a...
  
  
• Degree of parallelism
  Degree of parallelism
  The degree of parallelism is a metric which indicates how many operations can be or are being simultaneously executed by a computer. It is especially useful for describing the performance of parallel programs and multi-processor systems....
  
  
• Partitioned global address space
  Partitioned global address space
  In computer science, a partitioned global address space is a parallel programming model. It assumes a global memory address space that is logically partitioned and a portion of it is local to each processor. The novelty of PGAS is that the portions of the shared memory space may have an affinity...
  
  

Further reading

• H. Shan and J. Pal Singh. A comparison of MPI, SHMEM, and Cache-Coherent Shared Address Space Programming Models on a Tightly-Coupled Multiprocessor. International Journal of Parallel Programming, 29(3), 2001.
• H. Shan and J. Pal Singh. Comparison of Three Programming Models for Adaptive Applications on the Origin 2000. Journal of Parallel and Distributed Computing, 62:241–266, 2002.
• About structured parallel programming: Davide Pasetto and Marco Vanneschi. Machine independent Analytical models for cost evaluation of template--based programs, University of Pisa
  University of Pisa
  The University of Pisa , located in Pisa, Tuscany, is one of the oldest universities in Italy. It was formally founded on September 3, 1343 by an edict of Pope Clement VI, although there had been lectures on law in Pisa since the 11th century...
  
  , 1996

External links

• Developing Parallel Programs — A Discussion of Popular Models (Oracle White Paper September 2010)
• Designing and Building Parallel Programs (Section 1.3, 'A Parallel Programming Model')
• Introduction to Parallel Computing (Section 'Parallel Programming Models')