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 submissions are to be from groups of four students for this lab. (It is up to you if you want to do task 1 in a group of four or in smaller groups or even alone; however we want to see only one submission from the group of four. Submit your best solution.)
-
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. (See slide 33 of Lecture 9 for information about a Repa version that works with the Haskell Platform.)
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 form a group of four students and 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
- GPU programming in Haskell: a tutorial on Accelerate
- GPU programming in Haskell: a tutorial on Nikola
- GPU programming in Haskell: a tutorial on Obsidian
- Parallel sorting in Haskell: how well can we do?
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. There will be a prize for the best tutorial. Great images or beautiful code may end up on T-shirts :)