Description
Lab C 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.
-
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. 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) and/or to these draft lecture notes by Licata from the new CMU first year course.
-
The second task is to 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?
- Parallelising the Barnes-Hut algorithm in Haskell: an experience report
- Parallelising the Barnes-Hut algorithm in Erlang: an experience report
- GPU programming in Haskell: a tutorial on Accelerate
- GPU programming in Haskell: a tutorial on Obsidian
- Parallel sorting in Haskell: how well can we do?
- Parallel sorting in Erlang: 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
- Parallel programming in Eden: a tutorial
- Cloud Haskell: a tutorial
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 will add the best tutorials to the course pages. Great images or beautiful code may end up on T-shirts :)