Parallel Programming with Hints(转)

浅浅的花香味﹌ 2022-04-22 00:32 156阅读 0赞

# [Parallel Programming with Hints][](转) #

Wouldn’t it be nice to be able to write sequential programs and let the compiler or the runtime automatically find opportunities for parallel execution? Something like this is already being done on a micro scale inside processors. As much as possible, they try to execute individual instructions in parallel. Of course they have to figure out data dependencies and occasionally stall the pipeline or idle while waiting for a memory fetch. More sophisticated processors are even able to speculate–they guess a value that hasn’t been calculated or fetched yet and run speculative execution. When the value is finally available, they compare it with their guess and either discard or commit the execution.

If processors can do it, why can’t a language runtime do the same on a larger scale? It would solve the problem of effectively using all those cores that keep multiplying like rabbits on a chip.

The truth is, we haven’t figured out yet how to do it. Automatic parallelization is, in general, too complex. But if the programmer is willing to provide just enough hints to the compiler, the runtime might figure things out. Such programming model is called semi-implicit parallelism and has been implemented in two very different environments, in Haskell and in .NET. The two relevant papers I’m going to discuss are [Runtime Support for Multicore Haskell][] and [The Design of a Task Parallel Library][].

In both cases the idea is to tell the compiler that certain calculations may be done in parallel. It doesn’t necessarily mean that the code *will* be executed in multiple threads–the runtime makes this decision depending on the number of cores and their availability. The important thing is that, other than providing those hints, the programmer doesn’t have to deal with threads or, at least in Haskell, with synchronization. I will start with Haskell but, if you’re not into functional programming, you may skip to .NET and the Task Parallel Library (and hopefully come back to Haskell later).

# In Multicore Haskell #

In Haskell, you hint at parallel execution using the `par` combinator, which you insert between two expressions, like this: ``e1 `par` e2``. The runtime then creates a *spark* for the left hand side expression (here, `e1`). A spark is a deferred calculation that may be executed in parallel (in the .NET implementation a spark is called a *task*). Notice that, in Haskell, which is a lazy programming language, all calculations are, by design, deferred until their results are needed; at which point their evaluation is forced. The same mechanism kicks in when the result of a spark is needed–and it hasn’t been calculated in parallel yet. In such a case the spark is immediately evaluated *in the current thread* (thus forfeiting the chance for parallel execution). The hope is though that enough sparks will be ready before their results are needed, leading to an overall speedup.

To further control when the sparks are evaluated (whether in parallel or not), Haskell provides another combinator, `pseq`, which enforces sequencing. You insert it between two expressions, ``e1 `pseq` e2``, to make sure that the left hand side, `e1`, is evaluated before the evaluation of `e2` is started.

I’ll show you how to parallelize the standard `map` function (in C++ it would be called `std::transform`). `Map` applies a function, passed to it as the first argument, to each element of a list, which is passed to it as the second argument. As a Haskell refresher, let me walk you through the implementation of `map`.

map f []     = []
    map f (x:xs) = y:ys
        where y  = f x
              ys = map f xs

`Map` is implemented recursively, so its definition is split into the base case and the recursive case. The base case just states that `map` applied to an empty list, `[]`, returns an empty list (it ignores the first argument, `f`).

If, on the other hand, the list is non-empty, it can be split into its head and tail. This is done through pattern matching–the pattern being `(x:xs)`, where `x` matches the head element and `xs` the (possibly empty) tail of the list.

In that case, `map` is defined to return a new list, `(y:ys)` whose head is `y` and tail is `ys`. The `where` clause defines those two: `y` is the result of the application of the function `f` to `x`, and `ys` is the result of the recursive application of `map` to the tail of the list, `xs`.

The parallel version does the same (it is semantically equivalent to the sequential version), but it gives the runtime the opportunity to perform function applications in paralle. It also waits for the evaluation to finish.

parMap f []     = []
    parMap f (x:xs) = y `par` (ys `pseq` y:ys)
        where y  = f x
              ys = parMap f xs

The important changes are: `y`, the new head, may be evaluated in parallel with the tail (the use of the `par` combinator). The result, `y:ys`, is returned only when the tail part, `ys`, has been evaluated (the use of the `pseq` combinator).

The tail calculation is also split into parallel computations through recursive calls to `parMap`. The net result is that all applications of `f` to elements of the list are potentially done in parallel. Because of the use of `pseq`, all the elements (except for the very first one) are guaranteed to have been evaluated before `parMap` returns.

It’s instructive to walk through the execution of `parMap` step-by-step. For simplicity, let’s perform `parMap` on a two-element list, `[a, b]`.

First we pattern-match this list to `x = a` and `xs = [b]`. We create the first spark for the evaluation of `(y = f a)` and then proceed with the evaluation of the right hand side of `par`, ``(ys `pseq` y:ys)``. Here `ys = parMap f [b]`.

Because of the `` `pseq` ``, we must evaluate `ys` next. To do that, we call `(parMap f [b])`. Now the list `[b]` is split into the head, `b`, and the empty tail, `[]`. We create a spark to evaluate `y' = f b` and proceed with the right-hand side, ``(ys' `pseq` y':ys')``.

Again, the `` `pseq` `` waits for the evaluation of `ys' = parMap f []`. But this one is easy: we apply the base definition of `parMap`, which returns an empty list.

Now we are ready to retrace our steps. The right hand side of the last `` `pseq` `` re-forms the list `y':[]`. But that’s the `ys` the previous `` `pseq` `` was waiting for. It can now proceed, producing `y:(y':[])`, which is the same as `[y, y']` or `[f a, f b]`, which is what we were expecting.

Notice complete absence of explicit synchronization in this code. This is due to the functional nature of Haskell. There’s no shared mutable state so no locking or atomic operations are needed. (More explicit concurrent models are also available in Haskell, using `MVar`s or transactional memory.).

# Task Parallel Library in .NET #

It’s no coincidence that many ideas from Haskell end up in Microsoft languages. Many Haskell programmers work for Microsoft Research, including the ultimate guru, Simon Peyton Jones. The Microsoft Task Parallel Library (TPL) translates the ideas from Multicore Haskell to .NET. One of its authors, Daan Leijen, is a Haskell programmer who, at some point, collaborated with Simon Peyton Jones. Of course, a .NET language like C\# presents a different set of obstacles to parallel programming. It operates on mutable state which needs protection from concurrent access. This protection (which, incidentally, is the hardest part of multithreaded programming) is left to the programmer.

Here’s the example of an algorithm in C\# with hidden opportunities for parallel implementation. `MatrixMult` multiplies two matrices. It iterates over columns and rows of the result matrix. The value that goes at their intersection is calculated by the innermost loop.

void MatrixMult(int size, double[,] m1,double[,] m2, double[,] result)
    {
       for(int i = 0; i < size; i++){
          // calculate the i'th column
          for(int j = 0; j < size; j++){
             result[i, j] = 0;
             for(int k = 0; k < size; k++){
                  result[i, j] += m1[i, k] * m2[k, j];
             }
          }
       }
    }

Each column of the result could potentially be evaluated in parallel. The problem is, the size of the array and the number of processor cores might be unknown until the program is run. Creating a large number of threads when there are only a few cores may lead to a considerable slowdown, which is the opposite of what we want. So the goal of TPL is to let the programmer express the potential for parallel execution but leave it to the runtime to create an optimal number of threads.

The programmer splits the calculation into *tasks* (the equivalent of Haskell sparks) by making appropriate library calls; and the runtime maps those tasks into OS threads–many-to-one, if necessary.

Here’s how the same function looks with parallelization hooks.

void ParMatrixMult(int size, double[,] m1,double[,] m2, double[,] result)
    {
       Parallel.For(0, size, delegate(int i)
       {
          for(int j = 0; j < size; j++){
             result[i, j] = 0;
             for(int k = 0; k < size; k++){
                  result[i, j] += m1[i, k] * m2[k, j];
             }
          }
       });
    }

Because of clever formatting, this version looks very similar to the original. The outer loop is replaced by the call to `Parallel.For`, which is one of the parallelizing TPL functions. The inner loops are packed into a delegate.

This delegate is assigned to a task (the analog of Haskell spark) that is potentially run in a separate thread. Here the delegate is actually a closure–it captures local variables, `size`, `m1`, `m2` and `result`. The latter is actually modified inside the delegate. This is how shared mutable state sneaks into potentially multi-threaded execution. Luckily, in this case, such sharing doesn’t cause races. Consider however what would happen if we changed the types of the matrices from `double[,]` to `char[,]`. Parallel updates to neighboring byte-sized array elements may inadvertently encroach on each other and lead to incorrect results. Programmer beware! (This is not a problem in Haskell because of the absence of mutable state.)

But even if the programmer is aware of potential sharing and protects shared variables with locks, it’s not the end of the story. Consider this example:

int sum = 0;
    Parallel.For(0, 10000, delegate(int i)
    {
       if(isPrime(i)){
          lock(this) { sum += i; }
       }
    });

The captured variable, `sum` is protected by the lock, so data races are avoided. This lock, however, becomes a performance bottleneck–it is taken for every prime number in the range.

Now consider the fact that, on a 4-core machine, we’ll be running 10000 tasks distributed between about 4 threads. It would be much more efficient to accumulate the sum in four local variables–no locking necessary–and add them together only at the end of the calculation. This recipe can be expressed abstractly as a map/reduce type of algorithm (a generalization of the C++ `std::accumulate`). The tasks are *mapped* into separate threads, which work in parallel, and the results are then *reduced* into the final answer.

Here’s how map/reduce is expressed in TPL:

int sum = Parallel.Aggregate(
      0, 10000, // domain
      0, // initial value
      delegate(int i){ return (isPrime(i) ? i : 0) },
      delegate(int x, int y){ return x+y; }
    );

The first delegate, which is run by 10000 tasks, does not modify any shared state–it just returns its result, which is internally accumulated in some hidden local variable. The second delegate–the “reduce” part of the algorithm–is called when there’s a need to combine results from two different tasks.

# The Place for Functional Programming #

Notice that the last example was written in very functional style. In particular you don’t see any mutable state. The delegates are pure functions. This is no coincidence: functional programming has many advantages in parallel programming.

I’ve been doing a lot of multi-threaded programming in C++ lately and I noticed how my style is gradually shifting from object-oriented towards functional. This process is accellerating as functional features keep seeping into the C++ standard. Obviously, lambdas are very useful, but so is move semantics that’s been made possible by rvalue references, especially in passing data between threads. It’s becoming more and more obvious that, in order to be a good C++ programmer, one needs to study other languages. I recommend Haskell and Scala in particular. I’ll be blogging about them in the future.

# Bibliography #

1.  Simon Marlow, Simon Peyton Jones, and Satnam Singh, [Runtime Support for Multicore Haskell][]
2.  Daan Leijen, Wolfram Schulte, and Sebastian Burckhardt, [The Design of a Task Parallel Library][]
3.  A video introduction to Haskell by Simon Peyton Jones: [Part I][], [Part II][], together with [the slides][].

[Parallel Programming with Hints]: http://bartoszmilewski.wordpress.com/2010/05/11/parallel-programming-with-hints/
[Runtime Support for Multicore Haskell]: http://www.haskell.org/~simonmar/papers/multicore-ghc.pdf
[The Design of a Task Parallel Library]: http://research.microsoft.com/pubs/77368/TheDesignOfATaskParallelLibrary%28oopsla2009%29.pdf
[Part I]: http://oscon.blip.tv/file/324976
[Part II]: http://oscon.blip.tv/file/325646/
[the slides]: http://conferences.oreillynet.com/presentations/os2007/os_peytonjones.pdf