CMU 15-418/618 (Spring 2013) Final Project:
Pricing American Asian Options with the Binomial Model
Main Project Page

The first step we took was writing a serial implementation. The serial implementation was straightforward to implement with the use of a lot of C++ data structures, namely lists and maps to represent the tree structure. It gives correct results, but is much slower than we want our parallel implementation to calculate.

We then began converting the serial version of the code to a parallel one. One obstacle in doing so was converting the tree structure into a representation that could be manipulated inside kernels i.e. converting the STL data structures into regular arrays. Another obstacle we have to take into consideration is how to index the kernels. Because the parallel decomposition is in a tree (triangular) form and not in squares like in the case of the renderer from homework 2, we have to find a way to index into the tree without wasting processors.

In terms of the presentation at the parallelism competition, we plan on going over the results of running our program on actual data about stock prices in the past and compare our predicted option prices with corresponding option prices determined by the market. For example, we could run our program on information about Apple's stock prices in 2011, and see what Apple options value predicted for 2012 are, and compare those prices to the actual market values. It might also be possible to try to run our program in real-time on stocks.

At this point, we do not have any results from a parallel implementation, as it is still under works. However, our serial implementation does run correctly with a reasonable depth for the tree, albeit too slowly. Because we want our implementation to run as close to real time as possible, we will still be adding many optimizations to the Cuda implementation to reach that speed.

The following schedule is our plane for the following weeks. All of the tasks will be done together in mettings.
Week What We Plan To Do
Apr 27-30 Finish the parallel implementation
May 1-3 Add optimizations to reduce memory and divide workload optimally
May 4-7 Collect data by running our implementation on existing stock information
May 8-11 Write and prepare the presentation