Exercise 1

Description

This exercise is designed to get you started with looking at the course materials and with playing with parallelism in Haskell. It does not need to be submitted (though you may submit it if you wish, for feedback). Feel free to discuss it with your class mates and help each other out. If you run into problems, mail Nick, the course assistant (frolov at chalmers.se). If you have a eureka moment while reading papers or doing the exercise, let us know.

  1. First, you need to get as far as running and profiling a parallel Haskell program. The stuDAT (Linux) computers have a recent Haskell Platform installed.
    2. The GHC user guide contains a chapter about Using GHC (command-line arguments and the like).
  2. A good way to get started is to read the first part of Simon Marlow's book and follow his instructions for downloading and running code (see section on Sample Code). . It is good to make sure that you know how to compile Haskell code and get information about its performance. Note that Threadscope is installed on the stuDAT machines. (We will return to the details of the Eval monad later. For now, we are using the earlier approach (par and pseq)).
  3. Next, write, compile and run a sequential merge sort program in Haskell. 
    

msort :: Ord a => [a] -> [a]
    If your Haskell is very rusty, you might want to look back at Dave Sands' course on Functional Programming. The course pages point to plenty of useful information about Haskell.

  4. Next, study the section on using multiple cores with GHC in Chapter 24 of Real World Haskell. We are going to concentrate on the examples involving quicksort. See also the slides from Lecture 1. The actual code (for the whole book) is available. Download this and pick out the Sorting.hs and SortMain.hs files from Chapter 24. Play with them and then use them for inspiration in your own coding.
  5. For benchmarking, we advise using the Criterion package from Hackage. Type 
    

cabal update
cabal install criterion
    (and be prepared to wait a while). A nice intro. to the package (by its author Bryan O'Sullivan) is well worth reading, even though it is about an older version of the package. (See also Lecture 1).
  6. Think about the questions raised at the end of Lecture 1. What exactly has been parallelised in quicksort?
  7. Parallelise your merge sort in much the same way as quicksort is parallelised in the RWH code or in Lecture 1. Be prepared to play with the code. Develop a habit of documenting what you have tried. Does it help to introduce a threshold below which the code reverts to a sequential algorithm? Does changing heap size for garbage collection have a noticeable effect? We don't expect spectacular results -- just some speedup. The aim of the exercise is to get used to the tools, and to get you thinking.
  8. More questions to think about: Does it help to use a tree data structure to represent lists during the sorting (so as to avoid repeated list splitting or appending)? What about Strategies? Will they help here?