Parallelizing Tree Traversals for Binomial Option Pricing

Quantitative finance analysts and software developers often need to develop efficient software implementations of pricing models, hedging tools, and other financial algorithms in order to support their research. Some of the most commonly used quantitative analysis tools include binomial trees, which are useful to represent possible future model states and estimate the current value of an asset. Open-source libraries such as QuantLib provide tools to help analysts implement such algorithsms without needing to reinvent widely studied logic. Though such libraries are widely used by quantative finance developers in industry and academia, the algorithms presented for binomial tree traversals do not take advantage of parallelism or optimizations for cache locality, such as those proposed by Zubair and Mukkamala in 2008. The optimizations presented by Zubair and Mukkamala have not been tested on modern machines, nor have they been implemented in a way accessible to quantatative analysts. We provide a performance analysis of the cache optimizations presented by Zubair and Mukkamala on modern machines. Beyond this, we contribute an open-source framework that enables developers to compute a variety of binomial option-types using an easy-to-use programming interface and taking advantage of the parallel, cache-optimized algorithm developed by Zubair and Mukkamala. We find that our optimizations achieve up to a factor of a seven times speedup over a vanilla serial implementation, and a two times speedup up over a vanilla paralllel implementation. Our performance results support the direction of continuing to explore cacheoptimized algorithms for tree traversals and seeking to create generalized frameworks for more widespread use.M.Eng