Parallel programming model: Difference between revisions

Content deleted Content added
Reworked introduction and added a skeleton for classifications of parallel models.
Bender the Bot (talk | contribs)
 
(89 intermediate revisions by 62 users not shown)
Line 1:
{{Short description|Abstraction of parallel computer architecture}}
{{Under construction|notready=true}}
In [[computing]], a '''parallel programming model''' is an [[Abstraction (software engineering)|abstraction]] of [[parallel computing|parallel computer]] architecture, with which it is convenient to express [[algorithms]] and their composition in [[Computer program|programs]]. The value of a programming model can be judged on its ''generality'': how well a range of different problems can be expressed for a variety of different architectures, and its ''performance'': how efficiently the compiled programs can execute.<ref>Skillicorn, David B., "Models for practical parallel computation", International Journal of Parallel Programming, 20.2 133–158 (1991), https://www.ida.liu.se/~chrke55/papers/modelsurvey.pdf</ref> The implementation of a parallel programming model can take the form of a [[Library (computing)|library]] invoked from a [[programming language]], as an extension to an existing languages.
{{Prose|date=October 2008}}
 
Consensus around a particular programming model is important because it leads to different parallel computers being built with support for the model, thereby facilitating [[Software portability|portability]] of software. In this sense, programming models are referred to as ''[[bridging model|bridging]]'' between hardware and software.<ref name="Valiant1990">Leslie G. Valiant, "A bridging model for parallel computation", Communications of the ACM, Volume 33, Issue 8, August, 1990, pages 103–111.</ref>
A '''parallel programming model''' is a concept that bridges the gap between hardware and programming languages, in order to express [[parallel algorithm]]s and match applications with the underlying parallel systems.
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.
 
==Classification of parallel programming models==
Consensus on a programming model is important as it enables software expressed within it to be transportable between different architectures. The worth of a programming model is judged by how simply it is able to express a range of problems.
Classifications of parallel programming models can be divided broadly into two areas: process interaction and problem decomposition.<ref>John E. Savage, Models of Computation: Exploring the Power of Computing, 2008, Chapter 7 (Parallel Computation), https://cs.brown.edu/~jes/book/ {{Webarchive|url=https://web.archive.org/web/20161105053330/http://cs.brown.edu/~jes/book/ |date=2016-11-05 }}</ref><ref>{{Cite web |title=1.3 A Parallel Programming Model |url=https://www.mcs.anl.gov/~itf/dbpp/text/node9.html |access-date=2024-03-21 |website=www.mcs.anl.gov}}</ref><ref name=":0">{{Cite web |title=Introduction to Parallel Computing Tutorial {{!}} HPC @ LLNL |url=https://hpc.llnl.gov/documentation/tutorials/introduction-parallel-computing-tutorial |access-date=2024-03-21 |website=hpc.llnl.gov}}</ref>
 
==Main classifications and paradigms==
 
===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 interaction can also be implicit (invisible to the programmer).
 
====Shared memory====
{{Mainmain|Shared memory (interprocess communication)}}
Shared memory is an efficient means of passing data between processes. In a shared-memory model, parallel processes share a global address space that they read and write to asynchronously. Asynchronous concurrent access can lead to [[race condition]]s, and mechanisms such as [[Lock (computer science)|locks]], [[Semaphore (programming)|semaphores]] and [[Monitor (synchronization)|monitors]] can be used to avoid these. Conventional [[multi-core processor]]s directly support shared memory, which many parallel programming languages and libraries, such as [[Cilk (programming language)|Cilk]], [[OpenMP]] and [[Threading Building Blocks]], are designed to exploit.
 
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====
{{Mainmain|Message passing}}
In a message-passing model, parallel processes exchange data through passing messages to one another. These communications can be asynchronous, where a message can be sent before the receiver is ready, or synchronous, where the receiver must be ready. The [[Communicating sequential processes]] (CSP) formalisation of message passing uses synchronous communication channels to connect processes, and led to important languages such as [[Occam (programming language)|Occam]], [[Limbo (programming language)|Limbo]] and [[Go (programming language)|Go]]. In contrast, the [[actor model]] uses asynchronous message passing and has been employed in the design of languages such as [[D (programming language)|D]], [[Scala (programming language)|Scala]] and SALSA.
 
====Partitioned global address space====
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
{{main|Partitioned global address space}}
message-passing employed communication channels to 'connect' processes, and led to a number of important languages such as Joyce, occam and Erlang.
Partitioned Global Address Space (PGAS) models provide a middle ground between shared memory and message passing. PGAS provides a global memory address space abstraction that is logically partitioned, where a portion is local to each process. Parallel processes communicate by asynchronously performing operations (e.g. reads and writes) on the global address space, in a manner reminiscent of shared memory models. However by semantically partitioning the global address space into portions with affinity to a particular processes, they allow programmers to exploit [[locality of reference]] and enable efficient implementation on [[distributed memory]] parallel computers. PGAS is offered by many parallel programming languages and libraries, such as [[Fortran 2008]], [[Chapel (programming language)|Chapel]], [http://upcxx.lbl.gov UPC++], and [[SHMEM]].
 
====Implicit interaction====
{{Mainmain|Implicit parallelism}}
In an implicit model, no process interaction is visible to the programmer and instead the compiler and/or runtime is responsible for performing it. Two examples of implicit parallelism are with [[___domain-specific language]]s where the concurrency within high-level operations is prescribed, and with [[functional programming|functional programming languages]] because the absence of [[Side effect (computer science)|side-effects]] allows non-dependent functions to be executed in parallel.<ref name="ParFuncProg">Hammond, Kevin. Parallel functional programming: An introduction. In International Symposium on Parallel Symbolic Computation, p. 46. 1994.</ref> However, this kind of parallelism is difficult to manage<ref>McBurney, D. L., and M. Ronan Sleep. "Transputer-based experiments with the ZAPP architecture." PARLE Parallel Architectures and Languages Europe. Springer Berlin Heidelberg, 1987.</ref> and functional languages such as [[Concurrent Haskell]] and [[Concurrent ML]] provide features to manage parallelism explicitly and correctly.
 
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===
A parallel program is composed of simultaneously executing processes. Problem decomposition relates to the way in which the constituent processes are formulated.<ref>{{Cite web |title=2.2 Partitioning |url=https://www.mcs.anl.gov/~itf/dbpp/text/node16.html |access-date=2024-03-21 |website=www.mcs.anl.gov}}</ref><ref name=":0" />
 
====Task parallelism====
{{Mainmain|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. In [[Flynn's taxonomy]], task parallelism is usually classified as [[Multiple instruction, multiple data|MIMD]]/[[Flynn's taxonomy#MPMD|MPMD]] or [[Multiple instruction, single data|MISD]].
 
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====
{{Mainmain|Data parallelism}}
A data-parallel model focuses on performing operations on a data set, typically a regularly structured array. A set of tasks will operate on this data, but independently on disjoint partitions. In [[Flynn's taxonomy]], data parallelism is usually classified as [[Multiple instruction, multiple data|MIMD]]/[[SPMD]] or [[Single instruction, multiple data|SIMD]].
 
====Stream 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.
Stream parallelism, also known as pipeline parallelism, focuses on dividing a computation
into a sequence of stages, where each stage processes a portion of the input
data. Each stage operates independently and concurrently, and the output of one
stage serves as the input to the next stage. Stream parallelism is particularly suitable
for applications with continuous data streams or pipelined computations.
 
====Implicit parallelism====
{{Mainmain|Implicit parallelism}}
As with implicit process interaction, an implicit model of parallelism reveals nothing to the programmer as the compiler, the runtime or the hardware is responsible. For example, in compilers, [[automatic parallelization]] is the process of converting sequential code into parallel code, and in computer architecture, [[Superscalar processor|superscalar execution]] is a mechanism whereby [[instruction-level parallelism]] is exploited to perform operations in parallel.
 
==Terminology==
As with implicit process interaction, an implicit model of parallelism reveals nothing to the programmer as the the compiler and/or the runtime is responsible.
Parallel programming models are closely related to [[model of computation|models of computation]]. A model of parallel computation is an [[abstraction]] used to analyze the cost of computational processes, but it does not necessarily need to be practical, in that it can be implemented efficiently in hardware and/or software. A programming model, in contrast, does specifically imply the practical considerations of hardware and software implementation.<ref>Skillicorn, David B., and Domenico Talia, Models and languages for parallel computation, ACM Computing Surveys, 30.2 123–169 (1998), https://www.cs.utexas.edu/users/browne/CS392Cf2000/papers/ModelsOfParallelComputation-Skillicorn.pdf</ref>
 
A parallel programming language may be based on one or a combination of programming models. For example, [[High Performance Fortran]] is based on shared-memory interactions and data-parallel problem decomposition, and [[Go (programming language)|Go]] provides mechanism for shared-memory and message-passing interaction.
== Example parallel programming models==
{{Create-list|date=February 2010}}
Models
* [[Algorithmic skeleton|Algorithmic Skeletons]]
* Components
* Distributed Objects
* Remote Method Invocation
* Workflows
Libraries
* [[POSIX Threads]]
* [[Message Passing Interface|MPI]]
* [[Global Arrays]]
* [[SHMEM]]
* [[Parallel Virtual Machine|PVM]]
* [[Intel Threading Building Blocks|TBB]]
* [[Kernel for Adaptative, Asynchronous Parallel and Interactive programming|KAAPI]]
Languages
* [[Ada (programming language)|Ada]]
* [[Ateji PX]]
* [[C*]]
* [[Cilk]]
* [[Charm++]]
* [[Partitioned global address space]] languages:
** [[Co-array Fortran]],
** [[Unified Parallel C]],
** Titanium
* [[High Performance Fortran]]
* [[Haskell (programming language)|Haskell]]
* [[Occam (programming language)|Occam]]
* [[Event-driven programming]] & [[Hardware Description Language]]s:
** [[Verilog]]
** [[VHDL]]
** [[SystemC]]
** [[ParC]] Parallel C++ through language extensions
* [[Ease (programming language)|Ease]]
* [[Erlang (programming language)|Erlang]]
* [[Linda (coordination language)|Linda coordination language]]
* [[Oz (programming language)|Oz]]
* [[CUDA]]
* [[OpenCL]]
* [[AccelerEyes|Jacket]]
* [[NESL]]
* [[Scala (programming language)|Scala]]
 
==Example parallel programming models==
Unsorted
{| class="wikitable"
! Name || Class of interaction || Class of decomposition || Example implementations
|-
| [[Actor model]]
| Asynchronous message passing
| Task
| [[D (programming language)|D]], [[Erlang (programming language)|Erlang]], [[Scala (programming language)|Scala]], SALSA
|-
| [[Bulk synchronous parallel]]
| Shared memory
| Task
| [[Apache Giraph]], [[Apache Hama]], [[BSPlib]]
|-
| [[Communicating sequential processes]]
| Synchronous message passing
| Task
| [[Ada (programming language)|Ada]], [[Occam (programming language)|Occam]], [[VerilogCSP]], [[Go (programming language)|Go]]
|-
| [[Circuit (computer science)|Circuits]]
| Message passing
| Task
| [[Verilog]], [[VHDL]]
|-
| [[Dataflow programming|Dataflow]]
| Message passing
| Task
| [[Lustre (programming language)|Lustre]], [[TensorFlow]], [[Apache Flink]]
|-
| [[Functional programming|Functional]]
| Message passing
| Task
| [[Concurrent Haskell]], [[Concurrent ML]]
|-
| [[LogP machine]]
| Synchronous message passing
| Not specified
| None
|-
| [[Parallel random access machine]]
| Shared memory
| Data
| [[Cilk (programming language)|Cilk]], [[CUDA]], [[OpenMP]], [[Threading Building Blocks]], [[XMTC]]
|-
| [[SPMD]] [[Partitioned global address space|PGAS]]
| Partitioned global address space
| Data
| [[Fortran 2008]], [[Unified Parallel C]], [http://upcxx.lbl.gov UPC++], [[SHMEM]]
|-
| Global-view [[Task parallelism]]
| Partitioned global address space
| Task
| [[Chapel (programming language)|Chapel]], [[X10 (programming language)|X10]]
|}
 
==See also==
* [[OpenMP]]
* [[GlobalAutomatic Arraysparallelization]]
* [[Intel Ct]]
* [[Pervasive DataRush]]
* [[ProActive]]
* [[Parallel Random Access Machine]]
* [[Stream processing]]
* [[Ambric#Architecture_and_Programming_Model|Structural Object Programming Model (SOPM)]]
* [[Pipeline (software)|Pipelining]]
* [[ZPL (programming language)|ZPL]]
 
Other research-level models are:
* Cray's [[Chapel programming language|Chapel]]
* Sun’s [[Fortress (programming language)|Fortress]]
* IBM’s [[X10 (programming language)|X10]]
 
==See also ==
* [[Bridging model]]
* [[ConcurrencyConcurrent (Computer science)computing|Concurrency]]
* [[Automatic parallelization]]
* [[Degree of parallelism]]
* [[Explicit parallelism]]
* [[Partitioned global address space]]
* [[List of concurrent and parallel programming languages]]
* [[Optical Multi-Tree with Shuffle Exchange]]
* [[Parallel external memory (Model)]]
 
==References ==
{{reflist}}
* 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]]. ''[http://portal.acm.org/citation.cfm?id=898142&coll=&dl=GUIDE&CFID=15151515&CFTOKEN=6184618 Machine independent Analytical models for cost evaluation of template--based programs]'', [[University of Pisa]], 1996
 
==Further reading==
==External links ==
* {{Citation | author = Blaise Barney | institution = Lawrence Livermore National Laboratory | title = Introduction to Parallel Computing | url = https://computing.llnl.gov/tutorials/parallel_comp/ | access-date = 2015-11-22 | archive-date = 2013-06-10 | archive-url = https://web.archive.org/web/20130610122229/https://computing.llnl.gov/tutorials/parallel_comp/ | url-status = dead }}
* [http://www.oracle.com/technetwork/server-storage/solarisstudio/documentation/oss-parallel-programs-170709.pdf Developing Parallel Programs — A Discussion of Popular Models] (Oracle White Paper September 2010)
* {{Citation | author = Murray I. Cole. | title = Algorithmic Skeletons: Structured Management of Parallel Computation | institution = University of Glasgow | url = http://homepages.inf.ed.ac.uk/mic/Pubs/skeletonbook.pdf }}
* [http://www.mcs.anl.gov/~itf/dbpp/text/book.html Designing and Building Parallel Programs] (Section 1.3, 'A Parallel Programming Model')
* {{Cite book|author1=J. Darlinton |author2=M. Ghanem |author3=H. W. To |title=Proceedings of Workshop on Programming Models for Massively Parallel Computers |chapter=Structured parallel programming |date=1993 |pages=160–169 |doi=10.1109/PMMP.1993.315543 |isbn=0-8186-4900-3 |s2cid=15265646 | url = https://www.researchgate.net/publication/3557907}}
* [http://computing.llnl.gov/tutorials/parallel_comp/ Introduction to Parallel Computing] (Section 'Parallel Programming Models')
* {{Citation | author = Ian Foster | institution = Argonne National Laboratory | title = Designing and Building Parallel Programs | url = http://www.mcs.anl.gov/~itf/dbpp}}
 
{{Parallel Computing}}
Line 130 ⟶ 133:
[[Category:Programming paradigms]]
[[Category:Concurrent programming languages]]
 
[[cs:Paralelní programování]]
[[de:Parallele Programmierung]]
[[lt:Lygiagretusis programavimas]]
[[no:Parallellprogrammering]]
[[pt:Modelo de programação paralela]]
[[ru:Распараллеливание программ]]