Description
This first part of Lab 1 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 Nikita, the course assistant, by mail or in person during his office hours.
- In Lecture 2, we noticed that the divConq skeleton function from the second Strategies paper (from Haskell'10) doesn't follow the "hold onto the results of rpar" rule in its strategy code. The definition of divConq is on a slide (and of course in the paper). Your task is to make a new version of this function that does obey the rule. The file given.hs contains a suggested type for the new function, but you are free to make other choices if you wish. A good approach would be to get the function right first, ignoring strategies, and then to add your strategy code.
- Using the new divConq function, recode the scan algorithm that was defined using the old divConq function in the second lecture (see the file given.hs, which gives an ordinary recursive implementation of scan). Benchmark your algorithm using the Criterion library and report speeds and speedups (if any) for different values of the threshold.
- Optional: There are patterns of recursion that the new divConq does not cover. For example, what happens if the recursive call is only on part of the input? An example is the Brent Kung parallel scan algorithm, where the recursive formulation has only one recursive call, and doesn't fit the simpler pattern assumed in the original divConq. See this famous paper by Blelloch about prefix sums and their applications to understand why parallel prefix or scan is important for parallelism, by the way. Your task is to make your divConq more general and to implement and measure a couple more recursive algorithms using it.
-
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 after the break) 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.
The given file 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 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.
- 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. When I saw this paper on Palovca (available from SpringerLink via Chalmers library) being presented, I thought the examples and approach were very interesting. I wonder if some of the ideas could be used together with the Par Monad?