Description
This second part of the first lab is about flat data parallel programming. If you get stuck with any of the tasks, consult Nikita, 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::Int)]
*Main> buySell ins
(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. (If you are keen to do extra reading, a recent paper about cost models for parallel functional programming is very interesting.)
-
The second task again involves using the Repa library. Making use of bit-map images (.bmp files) as a means to make array operations concrete, write a brief tutorial on Repa array processing and parallelism.
Making a web page is probably the easiest way to do this but other forms of
document are also welcome.
Repa makes it easy to read in, manipulate and write out BMP files, see Don Stewart's Repa tutorial and also the repa-examples package that is mentioned there. The repa-io package can be used to read in BMP files. Thus, you will need the repa, repa-io and repa-examples packages (which you should install using Cabal, see the Repa tutorial). I use repa-2.1.1.5 with the current Haskell platform, and matching versions of the other packages. I started from the Main.hs file in the Blur example from repa-examples-2.1.0.2. That file shows how to read and write .bmp files. Once read in, you get three DIM2 arrays of Word8 values (which you may wish to cast to Double at times (as in the file mentioned)). The three arrays correspond to the red, green and blue values (as Word8) for each pixel.
You can either make your own arrays in a form suitable to be written out as BMP files or you can manipulate existing files (or both). Here are some small building blocks
block :: (Elt a) => Int -> Int -> a -> Array DIM2 a
block n m k = fromList ((Z :. (n::Int) :. m) :: DIM2) (replicate (n*m) k)red n m = P.map (block n m) [255,0,0]
green n m = P.map (block n m) [0,255,0]
blue n m = P.map (block n m) [0,0,255]
black n m = P.map (block n m) [0,0,0]
white n m = P.map (block n m) [255,255,255]
You could start by figuring out how to compose such images vertically and horizontally. Ways to combine two images into one are interesting. In general, pick operations on images that exercise the API of Repa. Make sure to include traverse and traverse2, as these are probably the hardest functions to understand. Remember to include functions that change the size and shape of arrays.
This tree picture and a larger image made from it are provided as exaples for you to manipulate. The main point, remember, is to make a clear and simple tutorial. 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 :)
