Welcome
Our goal of this project is to use parallel computing techniques to increase the calculating performance of binomial security pricing model. We will implement the project on Nvidia GPU platforms using CUDA API. In the end, we wish we can build a program that reacts to changes in variables and returns the theoretical prices of securities. Hope this pricing engine can serve as the core of a black-box trading system.
Link to Project Milestone Report
Link to Project Final Report
Background Information
Binomial security pricing model is a fundamental technique used in the financial industry. The idea of this model is that we can use a binomial tree to describe the evolution of security price. At time 0, we can denote the security price to be S0. At the next time period, the price S0 can evolve into S1(Head) with an up factor of u and S1(Tail) with a down factor of d. A multiple period binomial model is shown in the graph.
Picture from Stochastic Calculus for Finance I: The Binomial Asset Pricing Model by Steven E. Shreve. (In this case, the up factor and down factor (u and d) are fixed throughout time.) To calculate the initial price of the security, we introduce the technique of backward induction. Given the arbitrage-free interest rate r, the up factor u and down factor d, the no-arbitrage price of the security at time n can be computed recursively backward in time by this equation
Where p and q are the risk-neutral probabilities given by
We can draw some quick observations of this model. The price of each tree node depends on the price of its left and right children nodes and different parameters in the backward induction formula. Different path calculates its price using different children nodes, thus paths are independent of each other. This property allows us to parallelize the calculation of an N period binomial model, theoretically improving its performance from O(2^N) to O(N) time complexity. We will need to use some data to train and calibrate the binomial model and find the best parameters (u, d, r) before we can backward induct the current correct price of the security. If a trading system sees a difference between the market price and theoretical model price, it can further exam the situation and explore potential arbitrage in the mis-priced security.
THE CHALLENGE:
Problem Size - The nature of the binomial model presents some difficulties. As the time period increases, the total nodes in the binomial tree grows exponentially. (Total of 2^N nodes) Initially, we are aiming to have a 30-period binomial model, but we need to do some math and computer science optimizations. There is simply no platform that can calculate and store the 2^30-level binomial tree.
Memory Management - Assume that each node only contains a single floating number, because we have 2^30 nodes in total, there will be no reasonable storage device that can store this much data. We need to find a way to compress, hash and even abandon duplicated information. At the same time, we will be accessing value in the memory frequently. There's no way we can fit everything in the cache, so we need to find a way to access data that best utilizing the GPU memory and cache.
Smart Work Distribution - All the security price calculation involves the backward induction equation. The calculation time does not vary too much. However, we still need to manage to distribute the calculate in a clever way to best utilize the GPU.
Model Training - For simplicity, we use the binomial pricing model with three variables (up factor u, down factor d, and interest rate r). At the beginning, we don't have a concrete idea about the value of different variables. First thing to do in the program is to use training data to tune the model and find the best fitting variable value. Only then we can use the variable to produce correct theoretical price.
Time/ Speed - One of the goals is to use this program as the pricing engine to a black-box trading system. This goal poses a significant challenge and has a strict time requirement. To catch the mis-pricing arbitrage opportunities in the market, the system needs to react to a variety of products and provide pricing suggestions almost in real time. We will try our best to speed up the program and see if we can complete calculation in single digit second or even less than a second.
Resources
Computer Platform:
CPU and Nvidia GPU platform (potential benefit from GPU parallel computing)
Coding Language:
C/C++
Textbook Reference:
Stochastic Calculus for Finance I: The Binomial Asset Pricing Model by Steven E. Shreve.
Faculty Advisers:
Dr. David Handron (CMU-21370)
Prof. Todd C. Mowry (CMU-15418)
Prof. Brian Railing (CMU-15418)
Authors and Contributors
Team Members: Qifang “Charlie” Cai (@caiqifang), Xiqiao Shan (@firekarlshanxq)