We present a parallel algorithm that computes the ask and bid prices of an American option when proportional transaction costs apply to trading in the underlying asset. The algorithm computes the prices on recombining binomial trees, and is designed for modern multi-core processors. Although parallel option pricing has been well studied, none of the existing approaches takes transaction costs into consideration. The algorithm that we propose partitions a binomial tree into blocks. In any round of computation a block is further partitioned into regions which are assigned to distinct processors. To minimise load imbalance the assignment of nodes to processors is dynamically adjusted before each new round starts. Synchronisation is required both within a round and between two successive rounds. The parallel speedup of the algorithm is proportional to the number of processors used. The parallel algorithm was implemented in C/C++ via POSIX Threads, and was tested on a machine with 8 processors. In the pricing of an American put option, the parallel speedup against an efficient sequential implementation was 5.26 using 8 processors and 1500 time steps, achieving a parallel efficiency of 65.75%.
KeywordsParallel AlgorithmAmerican Option PricingBinomial Tree ModelTransaction Costs
F. Black and M. Scholes, “The Pricing of Options and Corporate Liabilities,” The Journal of Political Economy, Vol. 81, No. 3, 1973, pp. 637-659. doi:10.1086/260062
R. Merton, “Theory of Rational Option Pricing,” Bell Journal of Economics and Management Science, Vol. 4, No. 1, 1973, pp. 141-183. doi:10.2307/3003143
A. V. Gerbessiotis, “Architecture Independent Parallel Binomial Tree Option Price Valuations,” Parallel Computing, Vol. 30, No. 2, 2004, pp. 301-316. doi:10.1016/j.parco.2003.09.003
A. V. Gerbessiotis, “Parallel Option Price Valuations with the Explicit Finite Difference Method,” International Journal of Parallel Programming, Vol. 38, No. 2, 2010. pp. 159-182. doi:10.1007/s10766-009-0126-5
A. Ghuloum, G. Wu, X. Zhou, P. Guo and J. Fang, “Programming Option Pricing Financial Models with Ct. Technical Report,” Intel Corporation, Santa Clara, 2007.
Y. Peng, B. Gong, H. Liu and Y. X. Zhang, “Parallel Computing for Option Pricing Based on the Backward Stochastic Differential Equation,” Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2010, pp. 325-330.
S. Solomon, R. K. Thulasiram and P. Thulasiraman. “Option Pricing on the GPU,” Proceedings of the 12th IEEE International Conference on High Performance Computing and Communications, Melbourne, 1-3 September 2010, pp. 289-296.
M. Zubair and R. Mukkamala, “High Performance Implementation of Binomial Option Pricing,” Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2008, pp. 852-866.
A. Roux and T. Zastawniak, “American Options under Proportional Transaction Costs: Pricing, Hedging and Stopping Algorithms for Long and Short Positions,” Acta Applicandae Mathematicae, Vol. 106, No. 2, 2009, pp. 199-228. doi:10.1007/s10440-008-9290-7
B. Bensaid, J.-P. Lesne and H. Pages, “Derivative Asset Pricing with Transaction Costs,” Mathematical Finance, Vol. 2, No. 2, 1992, pp. 63-86. doi:10.1111/j.1467-9965.1992.tb00039.x
P. P. Boyle and T. Vorst, “Option Replication in Discrete Time with Transaction Costs,” The Journal of Finance, Vol. 47, No. 1, 1992, pp. 271-293. doi:10.1111/j.1540-6261.1992.tb03986.x
S. Perrakis and J. Lefoll, “Derivative Asset Pricing with Transaction Costs: An Extension,” Computational Economics, Vol. 10, No. 4, 1997, pp. 359-376. doi:10.1023/A:1008693830990
S. Perrakis and J. Lefoll, “Option Pricing and Replication with Transaction Costs and Dividends,” Journal of Economic Dynamics & Control, Vol. 24, No. 11-12, 2000, pp. 1527-1561. doi:10.1016/S0165-1889(99)00086-X
S. Perrakis and J. Lefoll, “The American Put under Transactions Costs,” Journal of Economic Dynamics & Control, Vol. 28, No. 5, 2004, pp. 915-935. doi:10.1016/S0165-1889(03)00099-X
C. Kolb and M. Pharr, “Options Pricing on the GPU Gems 2: Programming Techniques for High Performance Graphics and General-purpose Computation, Chapter 45,” Pearson, Upper Saddle River, 2005.
R. H. Bisseling, “Parallel Scientific Computation: A Structured Approach Using BSP and MPI,” Oxford University Press, Oxford, 2004.
G. Burns, R. Daoud and J. Vaigl, “LAM: An Open Cluster Environment for MPI,” Proceedings of Supercomputing Symposium, Toronto, 6-8 June 1994, pp. 379-386.
B. Dai, Y. Peng and B. Gong, “Parallel Option Pricing with BSDE Method on GPU,” Proceedings of the 9th International Conference on Grid and Cloud Computing, Melbourne, 17-20 May 2010, pp. 191-195. doi:10.1109/GCC.2010.47
W. D. Zhao, L. F. Chen and S. G. Peng, “A New Kind of Accurate Numerical Method for Backward Stochastic Differential Equations,” SIAM Journal on Scientific Computing, Vol. 28, No. 4, 2006, pp. 1563-1581. doi:10.1137/05063341X
R. P. Garg and I. Sharapov, “Techniques for Optimizing Applications: High Performance Computting,” Prentice Hall PTR, Upper Saddle River, 2001.
J. E. Savage and M. Zubair, “Cache-Optimal Algorithms for Option Pricing,” ACM Transactions on Mathematical Software, Vol. 37, No. 1, 2010, pp. 1-30.
A. V. Gerbessiotis, “Trinomial-Tree Based Parallel Option Price Valuations,” International Journal of Parallel, Emergent and Distributed Systems, Vol. 18, No. 3, 2003, pp. 181-196.
E. S. Schwartz, “The Valuation of Warrants: Implementing a New Approach,” Journal of Financial Economics, Vol. 4, No. 1, 1977, pp. 79-93. doi:10.1016/0304-405X(77)90037-X
R. L. Graham, T. S. Woodall and J. M. Squyres, “Open MPI: A Flexible High Performance MPI,” Proceedings of the 6th Annual International Conference on Parallel Processing and Applied Mathematics, Poznan, September 2005.
D. A. Bader, V. Kanade and K. Madduri, “SWARM: A Parallel Programming Framework for Multi-Core Processors,” Proceedings of the 1st Workshop on Multithreaded Architectures and Applications, Long Beach, 30 March 2007.
K. Huang and R. K. Thulasiram, “Parallel Algorithm for Pricing American Asian Options with Multi-Dimensional Assets,” Proceedings of the 19th International Symposium on High Performance Computing Systems and Applications, Guelph, 15-18 May 2005, pp. 177-185.
G. Fusai, D. Marazzina and M. Marena, “Option Pricing, Maturity Randomization and Distributed Computing,” Parallel Computing, Vol. 36, No. 7, 2010, pp. 403-414. doi:10.1016/j.parco.2010.03.002
W. Schoutens, “Levy Processes in Finance: Pricing Financial Derivatives,” Wiley, New York, 2003.
V.Surkov, “Parallel Option Pricing with Fourier Space Time-Stepping Method on Graphics Processing Units,” Parallel Computing, Vol. 36, No. 7, 2012, pp. 372-380. doi:10.1016/j.parco.2010.02.006
H. Prasain, G. K. Jha, P. Thulasiraman and R. K. Thulasiram, “A Parallel Particle Swarm Optimization Algorithm for Option Pricing,” Proceedings of 2010 IEEE International Symposium on Parallel and Distributed Processing, Workshops and PhD Forum (IPDPSW), Atlanta, 19-23 April 2012, pp. 1-7.
H. Sak, S. Ozekici and I. Boduroglu, “Parallel Computing in Asian Option Pricing,” Parallel Computing, Vol. 33, No. 2, 2007, pp. 92-108. doi:10.1016/j.parco.2006.11.002