DescriptionLab A explores the interplay between algorithms and parallelism. It is designed to get you using the tools for deterministic parallel programming that are available to you in Haskell. Some parts of the lab are designed to get you thinking and reading around the topics of the course. If you do any of the optional parts, please still submit your answers. This description of the Lab assumes that you have succeeded in doing Exercise 1. If you get stuck with any of the tasks, consult Nick, the course assistant, by mail or in person during his office hours.
Scan (sometimes called parallel prefix) is a very important algorithm in parallel programming, see this famous paper by Blelloch about prefix sums and their applications to get an idea of why this is.
In Haskell, you are probably familiar with its sequential equivalent the scanl1 function.
Your task is to make some parallel scan implementations. You should make at least two and at most four different implementations using the following methods:
- par and pseq
- the Eval monad (rpar and rseq)
- using a Strategy (as in the Haskell'10 Strategies paper)
- the Par monad
HintNote that there is a pretty simple recursive decomposition of scan. One applies scan recursively to the two halves of the input and then "fixes up" the output by applying the operator between the last output of the scan on the first half with each of the outputs of the scan on the second half. You can see a diagram that pictures this for 8 inputs in Fig. 5 of this paper by Mary. If you are having trouble trying to implement an "upsweep and downsweep" algorithm a la Blelloch, note also that you can do something very similar using recursion, see Fig. 10 in the same paper. (You don't need to read the paper. Just look at those two diagrams.)
BenchmarkingBenchmark your implementations (with varying thresholds where appropriate) using the Criterion library (see sl. 49, lecture 1) and report speeds and speedups (if any). Compare also to scanl1. Briefly discuss your results in your report. (Hints: You may need to experiment with ghc flags to control garbage collection. I find the -A flag useful. It might be a good idea to construct an associative operator that is more expensive than the standard (+)). Lecture 3 on monday of study week two will provide useful background information needed for doing a good job of the Haskell labs.
Now we turn our attention to another famous algorithm, the Fast Fourier Transform. The Discrete Fourier Transform (DFT) has complexity O(n^2) for n inputs. Any algorithm that cleverly gets this down to O(n log n) is called a Fast Fourier Transform. (An excellent survey on FFT algorithms is available. Even just looking at the pictures is useful :) Note also that this paper about the Repa library (to which we will return in lecture 5 or so) takes 3D FFT as an example, as do these slides about Single Assigment C, a very interesting project. FFTW and the Spiral project are also fascinating. The latter uses a declarative DSL to
describe algorithms. There will be a lecture about Single Assignment C later in the course.
The file given.hs contains a Haskell definition of both DFT and a simple recursive FFT (on lists of Complex Float). It also includes a function to generate lists of Complex Float values for use as inputs to the functions.
- Make a parallel FFT implementation in Haskell using par and pseq , rpar and rseq , or Strategies. You may start from the provided fft function if you wish, but this is not required. In particular, experiments using data types other than lists are welcome. (Thanks to Björn von Sydow for a simplification of last year's fft code.)
- Make a parallel FFT implementation in Haskell using the Par Monad.
- Benchmark and document your implementations. Explain the process by which you arrived at your best parallelisation. Provide an explanation for how the different implementations compare to each other for speed.
- Optional: Pick another, more control oriented algorithm and parallelise it using the Par Monad.
Possible problemsIf you find that you are missing packages used in the provided given.hs file, you may need to install them. (Only install packages if ghc tells you that it can't find something.) You might need some of
cabal intall normaldistribtion-220.127.116.11
cabal install monad-par-0.3.4.1
cabal install criterion