Lab A

Description

Lab 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.

1. 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:
   1. par and pseq
   2. the Eval monad (rpar and rseq)
   3. using a Strategy (as in the Haskell'10 Strategies paper)
   4. the Par monad

   Hint

   Note 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.)

   Benchmarking

   Benchmark 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.

2. 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.

   1. 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.)
   2. Make a parallel FFT implementation in Haskell using the Par Monad.
   3. 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.
3. Optional: Pick another, more control oriented algorithm and parallelise it using the Par Monad.

Possible problems

If 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 update
cabal intall normaldistribtion-1.1.0.3
cabal install monad-par-0.3.4.1
cabal install criterion

Submission

Deadline

The deadline for this first part is midnight on Monday April 6. However, you are strongly advised to submit earlier if possible. The final deadline is midnight on June 3. (Please read the rules on what first and final deadline mean.) The assignment should be submitted in the reporting system.

Clean Code

Before you submit your code, Clean It Up! Submitting clean code is Really Important, and simply the polite thing to do. After you feel you are done, spend some time on cleaning your code; make it simpler, remove unneccessary things, etc. We will reject your solution if it is not clean. Clean code:

• Does not have long lines (< 80 characters)
• Has a consistent layout
• Has type signatures for all top-level functions
• Has good comments
• Has no junk (junk is unused code, commented-out code, unnecessary comments)
• Has no overly complicated function definitions
• Does not contain any repetitive code (copy-and-paste programming)

Submission

Your submission needs to include the following information:

• Your Haskell file (.hs or .lhs), containing your solution. A single Haskell file is preferred. Call it LabAxx where xx is your group number. Do not submit .o, .hi or .exe files!
• report.txt or report.pdf, a file containing brief documentation of what you have done. Answer the questions asked in the assignment.

Before you submit, please read the note on cheating.

You are supposed to submit your solution using the Fire system.

Note: You do NOT have to use zip/gzip/tar/bzip on your files! Just upload each file that is part of your solution. Don't forget to submit when you have uploaded all the files.

To the Fire System

Good luck!