Parallelism is a computing strategy that enables many computations (or the execution of processes) to be performed simultaneously. In this chapter, you will learn the basic elements of parallelism and concurrency in Haskell.
Before continuing, let’s see what the differences are between parallelism and concurrency. In parallel computing, a larger problem is divided into smaller ones that are solved simultaneously, which implies that the hardware needs to have many processing units. Mainly, the purpose of parallelism is to make programs faster by adopting a strategy in which the dependencies between data are at a minimum. By contrast, the purpose of concurrency is to make programs more usable, and it can be used on a single processing unit (although it is compatible with multiple processing units to increase the speed). In concurrency, a problem can be executed partially without affecting the final output. When you are dealing with concurrency, it involves distributed computing.
Typically, in parallelism, you work with processes (do not confuse processes with processors , which refers to the hardware component), while in concurrency you work with threads . As concurrency can be executed on a single processing unit, you can easily deduce that a process contains at least one thread.
Note that parallelism and concurrency are closely related and are used in many situations together.
Parallelism
Using Control.Parallel, which leads to pure parallelism
Using concurrency to parallelize IO
The advantages of using parallel programming are that you obtain the same result every time (i.e., determinism) and you don’t get race conditions (i.e., the system depends on the timing or sequences of uncontrollable events) or deadlocks (a number of processes/threads expects a response from another process/thread).
The par combinator says that the first argument is evaluated at the same time as the second argument, but it returns the value of the second argument.
For these scenarios, you’ll meet a new term, spark. So, in the x `par` y statement, the evaluation of x is sparked, but y is returned. The sparks are stored in a queue and are executed in first in, first out (FIFO) order, not immediately. If at the time of an execution step an idle central unit processing (CPU) is detected, then a spark is converted into a thread that will run on the idle CPU.
The combinator pseq is similar to seq,2 but the difference is at runtime: seq may evaluate the arguments in any order, and pseq is forced to evaluate the first argument before the second one.
Let’s look for values where n>1. Here, par sparks the thread to evaluate nfib(n-1), while pseq forces the evaluation of nfib(n-2) on the parent thread. Through pseq, the nfib(n-2) branch is evaluated before addition with nfib(n-1). This approach is actually a divide-and-conquer operation, in which the parent thread evaluates a branch, while a new thread is sparked to evaluate the other branch. The combinatory pseq ensures that n2 is evaluated before n1 in the parent thread in the expression (n1+n2+1). This is mandatory because the compiler may not generate code to evaluate the addends from left to right.
More complex combinators are provided in the Control.Parallel.Strategies4 module. Here, the operations are created around the par combinator, which provides more complex patterns for parallel computing.
Concurrency
In Haskell, concurrency (provided through Control.Concurrent) is accomplished by using threads from the monad IO. One of the greatest models in concurrency is software transactional memory (STM), which works with forkIO and MVars. We will not cover parallel and concurrent programming in this chapter because they require a whole separate discussion. In [8] you will find a great list of documentation about concurrent and parallel programming in Haskell.
Summary
What parallelism and concurrency are
The difference between parallelism and concurrency
How the function Control.Parallel can be used
References
- 1.
S. P. Jones, A. Gordon, and S. Finne, “Concurrent Haskell,” POPL, vol. 96 (1996)
- 2.
S. Marlow, Parallel and Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming (O’Reilly Media, 2013)
- 3.
S. P. Jones and S. Singh, “A Tutorial on Parallel and Concurrent Programming in Haskell,” International School on Advanced Functional Programming (Springer, 2008)
- 4.
parallel: Parallel programming library, http://hackage.haskell.org/package/parallel
- 5.
- 6.
Chapter 7, GHC language features, https://downloads.haskell.org/~ghc/7.0.3/docs/html/users_guide/lang-parallel.html
- 7.
Control.Parallel.Strategies, https://downloads.haskell.org/~ghc/6.6.1/docs/html/libraries/base/Control-Parallel-Strategies.html
- 8.
Parallel/reading, https://wiki.haskell.org/Parallel/Reading