Personal tools

Applications and libraries/Concurrency and parallelism

From HaskellWiki

< Applications and libraries(Difference between revisions)
Jump to: navigation, search
(Concurrency: rearrange a bit)
 
(25 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
'''Concurrent and Parallel Programming'''
 
'''Concurrent and Parallel Programming'''
   
Haskell has been designed for parallel and concurrent programming since
+
Haskell offers a broad spectrum of tools for developing parallel or concurrent programs. For parallelism, Haskell libraries enable concise high-level parallel programs with results that are guaranteed to be deterministic, i.e., independent of the number of cores and the scheduling being used. Concurrency is supported with lightweight threads and high level abstractions such as [[software transactional memory]] for managing information shared across threads. Distributed programming is still mainly a research area. Some low-level tools (MPI bindings) and research prototypes are available and new approaches being developed, such as Cloud Haskell (Erlang-style actors as a Haskell library).
its inception. In particular, Haskell's [http://haskell.org/haskellwiki/Why_Haskell_matters purity] greatly simplifies reasoning about
+
parallel programs. This page lists libraries and extensions for programming
+
This page lists libraries and extensions for programming
concurrent and parallel applications in Haskell. See also the
+
concurrent and parallel applications in Haskell.
[[Parallel|parallel portal]] for research papers, tutorials and on
+
  +
See also the
  +
[[Parallel|parallel Haskell portal]] for research papers, tutorials and on
 
parallel and concurrent Haskell.
 
parallel and concurrent Haskell.
   
 
== Parallelism ==
 
== Parallelism ==
   
=== Parallel Strategies ===
+
=== Strategies and Par ===
   
Strategies provide a high-level compositional API for parallel programming.
+
;Strategies
  +
:A high-level compositional API for parallel programming.
  +
:* [http://hackage.haskell.org/package/parallel The parallel package on Hackage]
  +
:* [http://hackage.haskell.org/packages/archive/parallel/3.1.0.1/doc/html/Control-Parallel-Strategies.html Control.Parallel.Strategies Documentation]
  +
:* Latest paper: [http://research.microsoft.com/apps/pubs/default.aspx?id=138042 Seq no more: Better Strategies for Parallel Haskell]
  +
:* Original paper: [http://www.macs.hw.ac.uk/~dsg/gph/papers/html/Strategies/strategies.html Algorithm + Strategy = Parallelism]
  +
;[http://hackage.haskell.org/package/monad-par Monad-par]
  +
:An alternative parallel programming API to that provided by the parallel package. The Par monad allows the simple description of parallel computations, and can be used to add parallelism to pure Haskell code. The basic API is straightforward: the monad supports forking and simple communication in terms of IVars.
   
* [http://hackage.haskell.org/package/parallel The parallel package on Hackage]
+
=== Data parallelism ===
* [http://hackage.haskell.org/packages/archive/parallel/3.1.0.1/doc/html/Control-Parallel-Strategies.html Control.Parallel.Strategies Documentation]
 
* Latest paper: [http://research.microsoft.com/apps/pubs/default.aspx?id=138042 Seq no more: Better Strategies for Parallel Haskell]
 
* Original paper: [http://www.macs.hw.ac.uk/~dsg/gph/papers/html/Strategies/strategies.html Algorithm + Strategy = Parallelism]
 
 
=== Data Parallel Haskell ===
 
   
  +
;[http://repa.ouroborus.net/ Repa]
  +
:REgular PArallel arrays: high performance, regular, multi-dimensional, shape polymorphic parallel arrays.
  +
;[https://github.com/AccelerateHS/accelerate Accelerate]
  +
:An embedded language of array computations for high-performance computing in Haskell. Computations on multi-dimensional, regular arrays are expressed in the form of parameterised collective operations (such as maps, reductions, and permutations).
 
;[http://haskell.org/haskellwiki/GHC/Data_Parallel_Haskell Data Parallel Haskell]
 
;[http://haskell.org/haskellwiki/GHC/Data_Parallel_Haskell Data Parallel Haskell]
 
:Implicitly parallel, high performance (nested) arrays, supporting large multicore programming.
 
:Implicitly parallel, high performance (nested) arrays, supporting large multicore programming.
   
=== Low-level parallelism: par and pseq ===
+
=== Research efforts ===
 
The Control.Parallel module provides the low-level operations for parallelism on which Strategies are built.
 
 
* [http://hackage.haskell.org/packages/archive/parallel/latest/doc/html/Control-Parallel.html Control.Parallel Documentation]
 
 
=== Feedback-directed implicit parallelism ===
 
 
[http://research.microsoft.com/~tharris/papers/2007-fdip.pdf Implicit parallelism in Haskell, and a feedback-directed mechanism to increase its granularity]
 
 
=== Glasgow Parallel Haskell ===
 
 
''EYK: is this redundant with strategies?''
 
   
  +
; Feedback-directed implicit parallelism
  +
: Implicit parallelism in Haskell, and a feedback-directed mechanism to increase its granularity ([http://research.microsoft.com/~tharris/papers/2007-fdip.pdf FDIP paper])
 
;[http://www.macs.hw.ac.uk/~dsg/gph/ GpH: Glasgow Parallel Haskell]
 
;[http://www.macs.hw.ac.uk/~dsg/gph/ GpH: Glasgow Parallel Haskell]
 
:A complete, GHC-based implementation of the parallel Haskell extension GpH and of evaluation strategies is available. Extensions of the runtime-system and language to improve performance and support new platforms are under development.
 
:A complete, GHC-based implementation of the parallel Haskell extension GpH and of evaluation strategies is available. Extensions of the runtime-system and language to improve performance and support new platforms are under development.
Line 27: Line 33:
   
 
== Concurrency ==
 
== Concurrency ==
  +
  +
=== Concurrent Haskell ===
   
 
;[[Concurrency|Concurrent Haskell]]
 
;[[Concurrency|Concurrent Haskell]]
 
:GHC has supported concurrency with lightweight threads for more than a decade, and it [http://shootout.alioth.debian.org/gp4/benchmark.php?test=threadring&lang=all is very fast]. Threads in Haskell are preemptively scheduled and support everything you would normally expect from threads, including blocking I/O and foreign calls.
 
:GHC has supported concurrency with lightweight threads for more than a decade, and it [http://shootout.alioth.debian.org/gp4/benchmark.php?test=threadring&lang=all is very fast]. Threads in Haskell are preemptively scheduled and support everything you would normally expect from threads, including blocking I/O and foreign calls.
* [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent.html Documentation]
+
:* [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent.html Documentation]
* [http://haskell.org/haskellwiki/Concurrency_demos Examples]
+
:* [http://haskell.org/haskellwiki/Concurrency_demos Examples]
   
 
=== Software transactional memory ===
 
=== Software transactional memory ===
Line 37: Line 45:
 
;[[Software transactional memory|Software Transactional Memory]]
 
;[[Software transactional memory|Software Transactional Memory]]
 
:GHC supports a sophisticated version of software transactional memory. Software Transactional Memory (STM) is a new way to coordinate concurrent threads.
 
:GHC supports a sophisticated version of software transactional memory. Software Transactional Memory (STM) is a new way to coordinate concurrent threads.
* [http://hackage.haskell.org/package/stm Documentation]
+
:* [http://hackage.haskell.org/package/stm Documentation]
* The paper [http://research.microsoft.com/en-us/um/people/simonpj/papers/stm/stm.pdf Composable memory transactions].
+
:* The paper [http://research.microsoft.com/en-us/um/people/simonpj/papers/stm/stm.pdf Composable memory transactions].
* The paper [http://research.microsoft.com/en-us/um/people/simonpj/papers/stm/lock-free-flops06.pdf Lock-free data structures using Software Transactional Memory in Haskell] gives further examples of concurrent programming using STM.
+
:* The paper [http://research.microsoft.com/en-us/um/people/simonpj/papers/stm/lock-free-flops06.pdf Lock-free data structures using Software Transactional Memory in Haskell] gives further examples of concurrent programming using STM.
   
=== Actors ===
+
=== Research efforts ===
   
 
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/actor Actors with multi-headed receive clauses]
 
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/actor Actors with multi-headed receive clauses]
Line 47: Line 55:
 
;[http://www.cs.kent.ac.uk/projects/ofa/chp/ CHP: Communicating Haskell Processes]
 
;[http://www.cs.kent.ac.uk/projects/ofa/chp/ CHP: Communicating Haskell Processes]
 
:CHP is built on the ideas of CSP (Communicating Sequential Processes), featuring encapsulated parallel processes (no shared data!) communicating over synchronous channels. This is a very composable mode that also allows choice on communications, so that a process may offer to either read on one channel or write on another, but will only take the first that is available.
 
:CHP is built on the ideas of CSP (Communicating Sequential Processes), featuring encapsulated parallel processes (no shared data!) communicating over synchronous channels. This is a very composable mode that also allows choice on communications, so that a process may offer to either read on one channel or write on another, but will only take the first that is available.
 
=== Helper tools ===
 
 
;[[WrapConc | Wrapped Concurrency]]
 
:A wrapper around Control.Concurrency and Control.Exception that provides versions of forkIO that have more guarantees.
 
 
=== Experimental tools ==
 
 
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/transactional-events Transactional events, based on Concurrent ML]
 
:Transactional events for Haskell.
 
   
 
----
 
----
Line 74: Line 72:
 
;[http://www.macs.hw.ac.uk/~dsg/gdh/ GdH: Glasgow Distributed Haskell]
 
;[http://www.macs.hw.ac.uk/~dsg/gdh/ GdH: Glasgow Distributed Haskell]
 
:GdH supports distributed stateful interactions on multiple locations. It is a conservative extension of both Concurrent Haskell and GpH, enabling the distribution of the stateful IO threads of the former on the multiple locations of the latter. The programming model includes forking stateful threads on remote locations, explicit communication over channels, and distributed exception handling.
 
:GdH supports distributed stateful interactions on multiple locations. It is a conservative extension of both Concurrent Haskell and GpH, enabling the distribution of the stateful IO threads of the former on the multiple locations of the latter. The programming model includes forking stateful threads on remote locations, explicit communication over channels, and distributed exception handling.
 
;Mobile Haskell (mHaskell) (dead link)
 
:Mobile Haskell supports both strong and weak mobility of computations across open networks. The mobility primitives are higher-order polymorphic channels. Mid-level abstractions like remote evaluation, analogous to Java RMI, are readily constructed. High-level mobility skeletons like mobile map and mobile fold encapsulate common patterns of mobile computation.
 
   
 
;[http://www.mathematik.uni-marburg.de/~eden Eden]
 
;[http://www.mathematik.uni-marburg.de/~eden Eden]
 
:Eden extends Haskell with a small set of syntactic constructs for explicit process specification and creation. While providing enough control to implement parallel algorithms efficiently, it frees the programmer from the tedious task of managing low-level details by introducing automatic communication (via head-strict lazy lists), synchronisation, and process handling.
 
:Eden extends Haskell with a small set of syntactic constructs for explicit process specification and creation. While providing enough control to implement parallel algorithms efficiently, it frees the programmer from the tedious task of managing low-level details by introducing automatic communication (via head-strict lazy lists), synchronisation, and process handling.
   
=== Ports ===
+
;[[Cloud Haskell]]
  +
:Cloud Haskell is a domain-specific language for developing programs for a distributed computing environment. Implemented as a shallow embedding in Haskell, it provides a message passing communication model, inspired by Erlang, without introducing incompatibility with Haskell’s established shared-memory concurrency.
   
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ports-0.4.3.2 The Haskell Ports Library (HPL)]
+
=== Research efforts ===
:Ports are an abstraction for modelling variables whose values evolve over time without the need to resort to mutable variable, such as IORefs. More precisely, a port represents all values that a time-dependent variable successively takes as a stream, where each element of the stream corresponds to a state change - we can also say that a port represents a time series. Moreover, a port supports concurrent construction of the time series, or stream of values.
 
 
=== Modelling concurrent and distributed systems ===
 
   
 
;[http://www.cs.kent.ac.uk/~cr3/HCPN/ HCPN: Haskell-Coloured Petri Nets]
 
;[http://www.cs.kent.ac.uk/~cr3/HCPN/ HCPN: Haskell-Coloured Petri Nets]
 
:Haskell-Coloured Petri Nets (HCPN) are an instance of high-level Petri Nets, in which anonymous tokens are replaced by Haskell data objects (and transitions can operate on that data, in addition to moving it around). This gives us a hybrid graphical/textual modelling formalism for Haskell, especially suited for modelling concurrent and distributed systems.
 
:Haskell-Coloured Petri Nets (HCPN) are an instance of high-level Petri Nets, in which anonymous tokens are replaced by Haskell data objects (and transitions can operate on that data, in addition to moving it around). This gives us a hybrid graphical/textual modelling formalism for Haskell, especially suited for modelling concurrent and distributed systems.
  +
  +
  +
[[Category:Parallel]]

Latest revision as of 09:57, 17 August 2012

Concurrent and Parallel Programming

Haskell offers a broad spectrum of tools for developing parallel or concurrent programs. For parallelism, Haskell libraries enable concise high-level parallel programs with results that are guaranteed to be deterministic, i.e., independent of the number of cores and the scheduling being used. Concurrency is supported with lightweight threads and high level abstractions such as software transactional memory for managing information shared across threads. Distributed programming is still mainly a research area. Some low-level tools (MPI bindings) and research prototypes are available and new approaches being developed, such as Cloud Haskell (Erlang-style actors as a Haskell library).

This page lists libraries and extensions for programming concurrent and parallel applications in Haskell.

See also the parallel Haskell portal for research papers, tutorials and on parallel and concurrent Haskell.

Contents

[edit] 1 Parallelism

[edit] 1.1 Strategies and Par

Strategies
A high-level compositional API for parallel programming.
Monad-par
An alternative parallel programming API to that provided by the parallel package. The Par monad allows the simple description of parallel computations, and can be used to add parallelism to pure Haskell code. The basic API is straightforward: the monad supports forking and simple communication in terms of IVars.

[edit] 1.2 Data parallelism

Repa
REgular PArallel arrays: high performance, regular, multi-dimensional, shape polymorphic parallel arrays.
Accelerate
An embedded language of array computations for high-performance computing in Haskell. Computations on multi-dimensional, regular arrays are expressed in the form of parameterised collective operations (such as maps, reductions, and permutations).
Data Parallel Haskell
Implicitly parallel, high performance (nested) arrays, supporting large multicore programming.

[edit] 1.3 Research efforts

Feedback-directed implicit parallelism
Implicit parallelism in Haskell, and a feedback-directed mechanism to increase its granularity (FDIP paper)
GpH: Glasgow Parallel Haskell
A complete, GHC-based implementation of the parallel Haskell extension GpH and of evaluation strategies is available. Extensions of the runtime-system and language to improve performance and support new platforms are under development.

[edit] 2 Concurrency

[edit] 2.1 Concurrent Haskell

Concurrent Haskell
GHC has supported concurrency with lightweight threads for more than a decade, and it is very fast. Threads in Haskell are preemptively scheduled and support everything you would normally expect from threads, including blocking I/O and foreign calls.

[edit] 2.2 Software transactional memory

Software Transactional Memory
GHC supports a sophisticated version of software transactional memory. Software Transactional Memory (STM) is a new way to coordinate concurrent threads.

[edit] 2.3 Research efforts

Actors with multi-headed receive clauses
Actor-based concurrency for Haskell
CHP: Communicating Haskell Processes
CHP is built on the ideas of CSP (Communicating Sequential Processes), featuring encapsulated parallel processes (no shared data!) communicating over synchronous channels. This is a very composable mode that also allows choice on communications, so that a process may offer to either read on one channel or write on another, but will only take the first that is available.

[edit] 3 Distributed programming

[edit] 3.1 MPI

hMPI
hMPI is an acronym for HaskellMPI. It is a Haskell binding conforming to MPI (Message Passing Interface) standard 1.1/1.2. The programmer is in full control over the communication between the nodes of a cluster.
Haskell-MPI
Haskell-MPI provides a Haskell interface to MPI, built on top of the foreign function interface. It is notionally a descendant of hMPI, but is mostly a rewrite.

[edit] 3.2 Distributed Haskell

GdH: Glasgow Distributed Haskell
GdH supports distributed stateful interactions on multiple locations. It is a conservative extension of both Concurrent Haskell and GpH, enabling the distribution of the stateful IO threads of the former on the multiple locations of the latter. The programming model includes forking stateful threads on remote locations, explicit communication over channels, and distributed exception handling.
Eden
Eden extends Haskell with a small set of syntactic constructs for explicit process specification and creation. While providing enough control to implement parallel algorithms efficiently, it frees the programmer from the tedious task of managing low-level details by introducing automatic communication (via head-strict lazy lists), synchronisation, and process handling.
Cloud Haskell
Cloud Haskell is a domain-specific language for developing programs for a distributed computing environment. Implemented as a shallow embedding in Haskell, it provides a message passing communication model, inspired by Erlang, without introducing incompatibility with Haskell’s established shared-memory concurrency.

[edit] 3.3 Research efforts

HCPN: Haskell-Coloured Petri Nets
Haskell-Coloured Petri Nets (HCPN) are an instance of high-level Petri Nets, in which anonymous tokens are replaced by Haskell data objects (and transitions can operate on that data, in addition to moving it around). This gives us a hybrid graphical/textual modelling formalism for Haskell, especially suited for modelling concurrent and distributed systems.