Abstract
We examine how trinomial-tree based computations such as those involved in American or European-style option price valuations can be performed in parallel. Towards this we introduce a parallel algorithm for performing such computations on trinomial trees. The algorithm is described and analyzed in an architecture independent setting and achieves optimal theoretical speedup O(p) and is thus within a 1 + o(1) multiplicative factor of the corresponding sequential method. We verify the practicality and plausibility of the designed algorithm by carrying out an experimental study of an implementation of the algorithm on a high-latency parallel system, a cluster of PC workstations. The algorithmic and programming methodology used to design and analyze the algorithm allows its implementation to work with only recompilation of the source code under two parallel programming libraries: MPI (LAM-MPI) and BSPlib thus making the implementation not only architecture but also communication-library independent.
Original language | English (US) |
---|---|
Pages (from-to) | 181-196 |
Number of pages | 16 |
Journal | Parallel Algorithms and Applications |
Volume | 18 |
Issue number | 4 |
DOIs | |
State | Published - Dec 2003 |
All Science Journal Classification (ASJC) codes
- General Computer Science
Keywords
- BSP model
- Bulk-synchronous parallel
- Option valuations
- Trinomial trees