When you are done, please submit your solution using the Fire system, see guidelines for submission at the bottom of the page.

In this lab assignment, you will get started with parallel programming in Haskell, including the use of Criterion and Threadscope for profiling.

see the Haskell Installation page. It is important to read the advice below on GHC flags, task size etc.!

Setup

Follow the instructions for preparing Lab A.

Assignment 1

This first assignment is about parallelising an “embarassingly parallel” function.

An embarassingly parallel function is one that has many separate and non-communicating tasks. In Haskell, it is often a map. The file given.hs (Links to an external site.) contains the function jackknife that maps the mean function over a list of lists (created using resamples). The code is borrowed from this lecture (Links to an external site.) (I think by Bryan O’Sullivan, author of Criterion, the benchmarking tool you will use).

Your job is to parallelise that map in a number of different ways, and to benchmark and report on your results. (If you get bored with parallelising map, you can always move on to resamples. I have not tried that!)

At a minimum, you should do the following

Parallelise jackknife using par and pseq (for example by defining a parallel map function that uses par and pseq).
Parallelise jackknife using rpar and rseq from the Eval monad by defining a parallel map function that uses rpar and rseq. Compare with the built in parMap.
Parallelise jackknife using Strategies. [Comment in response to a question that John got: Here, you are expected to use Strategies without using rpar and rseq directly. So question c is not already solved if you answer question b. (These are all easy questions., by the way.)]
Parallelise jackknife using the Par Monad.

Remember that PCPH (Links to an external site.) is a great source of information and examples.

Assignment 2

In Haskell, define a Divide and Conquer higher order function that enables parallelisation of recursive algorithms. We suggest using the Par Monad but you may make other choices if you wish. Now, use the pattern to implement two different parallel algorithms, one of which should be sorting on lists. Try to choose a completely new algorithm for the second one, rather than just copying some code from a book or paper. Benchmark your implementations systematically. Report on your results. (Expect only moderate speedups for sorting on lists. If you run out of things to do, you could play with sorting on arrays or other data structures.)

Assignment 3

As discussed in Chapter 3 of PCPH, Haskell programs that work on lazy streams can pose a bit of a problem for parallelisation because there is a risk of losing the nice lazy behaviour. One possible solution is parBuffer, which keeps control over the number of available sparks.

Advice on GHC flags, garbage collection, task size etc (Nick Frolov, former TA)

If you’re not getting speedups, or if the performance of a parallel program is worse than that of a sequential one, make sure that garbage collection is not the bottleneck in your program. If a significant part of your Threadscope plots is GC (orange color), try to run your program pretending you have unlimited memory, so no GC will happen. Set a ridiculously large nursery size with the -A flag (100 Mb will do), this will effectively turn the collector off, as the nursery will never be full, therefore no GC will be needed. To enable this, you need to use the +RTS flag before -A when invoking your program.

If your program actually requires more memory for intermediate values over its runtime, you might want to consider to recycle memory. A small nursery size will cause more frequent GC but also more eager promotion. The former brings an overhead when allocated data doesn’t tend to be short-living, and the latter in the opposite case (if short-living data ended up being promoted to an older generation, it will still have to be collected). A good nursery size should not usually also be larger than L2 cache to exploit locality, but a better one can only be found experimentally. The -H flag (setting the initial heap size) should not be neglected either.

While the heap will expand if its initial size was not enough, doing so is an extra work for the collector. Set it generously (perhaps, 1 Gb), there is no fault in doing it other than exhausting your RAM. Which, ideally, you shouldn’t do, as swapping is much more expensive than GC, just as serving cache faults from main memory is if the nursery exceeds the cache size.

Don’t forget to experiment with depth (or unit of work size, if you prefer that). If you’re getting many fizzled sparks (check on it with the -s flag or in Threadscope), it is a clear sign that your units of work are too small and not worth spawning a thread to do. Remember that to run even a Haskell green thread means tens of instructions, this does not justify an addition of 32-bit integers or a similarly cheap operation. Another cause of fizzled sparks is uneven division of work into chunks, which can also lead to sparked computation results being needed sooner than the corresponding sparks get a chance to be converted. You can see spark size statistics in Threadscope (“Spark sizes” tab).

If you’re wondering why your sequential scan with an “expensive” operator runs much faster than a parallelized version, try to switch off optimization. Some “expensive” operators are not that expensive if GHC takes a good look at them, especially if it sees a chance for aggressive inlining (and there are many indeed, when no sparks are being created).

Submission

This lab has two deadlines:

First deadline (Wednesday, April 12 at 23:59): You need to have made a serious effort on all obligatory parts of the lab assignment.
Final deadline (Wednesday, April 19 at 23:59): You need to have passed the lab unless you have requested and been given an extension.

Your submission needs to include the following information:

Your Haskell file (.hs or .lhs) or files, containing your solution. A single Haskell file is preferred (but that can be awkward when using some libraries). Call it LabAxx where xx is your group number (or something similar if you have several files). Do not submit .o, .hi or .exe files!
report.txt or report.pdf, a file containing brief documentation of what you have done. Submit the files separately (no tar or similar).

Before you submit your code, Clean It Up! Remember, 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 unnecessary things, etc. We will reject your solution if it is not clean. Clean code:

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

When you are done, please submit using the Fire system.

Good luck!