Lab B

Description

The first part of Lab B is about flat data parallel programming. If you get stuck with any of the tasks, consult Nick, the course assistant, by mail or in person during his office hours.

  1. The first task is a variant on the stock market problem, which is a classic NESL example. The input is an array of Ints, corresponding to the price of a stock on successive days. You may, if you wish, assume that the input has length a power of two. A trader wants to make either zero or one transactions consisting of buying on one day and selling on another, later day. Write a program using the Repa library that, given such an array of prices, returns a triple (b,s,p), where b and s indicate the indices into the array at which it is best to buy and sell the stock respectively, and p is the resulting profit (the difference between the prices at the two times). If two different times for sale give the same profit, then choose the earlier one, and similarly if two times for buying give the same profit, choose the later one. Return (0,0,0.0) or in some other way indicate when no transaction is wise. Example:

    *Main> let ins = fromList (Z :. (8::Int)) [0,0,2,9,8,10,1,10] :: Array U DIM1 Int
    Applying your buySell function to ins should give
    (1,5,10)

    Benchmark using Criterion and report on performance and speedups.

    Analyse the cost of your algorithm in terms of work and depth (or span) in the style of Blelloch, for an input array of length N. I would like you to devote significant time to this part of the lab, studying relevant material (including the lecture on Data Parallel Programming, which introduces NESL, and the associated reading). The best place to start is probably on the page about NESL at CMU. You can then move on to papers by Blelloch (or the first chapters of his book).

  2. The second part of the Lab is to do at least one of Task I and Task II:
    • Task I: write a tutorial on one of the following topics:
      • Repa 3: a tutorial for curious Haskell programmers
      • Data Parallel Haskell: a tutorial for curious Haskell programmers
      • Profiling and optimising parallel Haskell programs with Threadscope: a tutorial
      • The Par Monad for parallel Haskell programming: a tutorial
      • A comparison of different approaches to deterministic parallel programming in Haskell
      • A tutorial on Parallel Strategies in Haskell
      • How to use par and pseq for parallel programming in Haskell
      • Why choose Haskell for deterministic parallel programming?
      • GPU programming in Haskell: a tutorial on Accelerate
      • Parallel sorting in Haskell: how well can we do?
      • An introduction to skeletons and their use in parallel functional programming
      • Parallel programming in F#: a tutorial
      • Laziness considered harmful for parallel programming
      or on a topic of your choice agreed with Mary by email (ms at chalmers.se). This year, we will (as an experiment) not try to restrict each topic to being covered by one lab group.

      The main point, remember, is to make a clear and simple tutorial (something like a technical blog post). Good tutorials often contain nice pictures! Give readers some information about sequential and parallel running times. Submit your document or web page with all associated images and code. We may add excellent tutorials to the course pages. Great images or beautiful code may end up on T-shirts :)

    • Task II: Implement an interesting deterministic parallel program in Haskell, documenting your work in developing and optimising the program, and writing a blog post about it. Your grade on this part will be particularly high if you in some way augment the parallel library that you are using. If you are in doubt about your choice of problem to tackle, consult with Nick, copying to Mary. You should put in about the same amount of work as you would in writing a tutorial (above). We are adding this option to do programming instead of writing a tutorial because of feedback from students. Some really liked writing tutorials and some did not find it so interesting.

      • You may, of course, submit answers to both of these tasks (Task I and Task II) if you wish! We think that both of these tasks could be used to explore possible Masters Thesis topics. It would be great if some of this work turned into published papers!

Submission

Deadline

The deadline for Lab B is 23.59 on Monday May 4. 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.

Submission

Follow the general submission guidlines (and note the section on benchmarking requirements). Submit Your tutorial or your report on a parallel programming exercise in a suitable format such as html or pdf.

To the Fire System

Good luck!