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. 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. We welcome interesting 20 minute short talks from students and they will count as part of your lab work.

  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. You should enable it with 
    

    vcs-select -p haskell-platform-2011.4.0.0
    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 lecture notes and follow his instructions for downloading code and running the Sudoku examples that he describes (see his home page). 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 studDAT machines. (We will return to the details of the Eval monad later. For now, we are using the more old-fashioned 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.

  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. (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. Optional for now: 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?