### A survey of parallel tree-based methods on option pricing

```A Survey of Parallel Tree-based
Methods on Option Pricing
PRESENTER: LI,XINYING
Outline
Introduction
Black-Scholes Model
Binomial Options Pricing Model
Trinomial Options Pricing Model
Improved Binomial Option Pricing
CPU-GPU Hybrid Parallel Binomial
Summary
Introduction
Stock
Bond
Currency
Underlying Asset!
Introduction
Option’s price is based on the corresponding underlying asset’s price.
+
A suitable
price of
option
Introduction
Classification of options
According to the
Options’ right:
Call Option & Put Option
Option Styles:
European Option
American Option
Bermudan Option
Asian Option
Barrier Option
Binary Option
Exotic Option
Vanilla Option
Introduction
Central Processing Unit (CPU) Graphics Processing Unit (GPU)
CPU:
CPU: efficient
in
serial efficient
computing
in serial
computin
g
GPU: efficient in
parallel
computing
Introduction
Option pricing:
High demand on calculating speed
Heavy computation volume
The calculation procedure could be parallelized
Input: price of
the underlying
asset
GPU: parallel
computing
Efficient Algorithm
Output: option
price
Introduction
Properties for evaluating the option pricing method
Efficiency
Storage
Accuracy
Therefore, a series of
tree-based algorithms
have been proposed to
optimize the previous
ones from different
aspects.
Outline
Introduction
Black-Scholes Model
Binomial Options Pricing Model
Trinomial Options Pricing Model
Improved Binomial Option Pricing
CPU-GPU Hybrid Parallel Binomial
Summary
Black-Scholes Model
It was raised by Fischer Black and Myron Scholes in 1973.
From the model, one can deduce the Black-Scholes formula, which gives a theoretical estimate of the
price of European-style options.
=  ∙  1 −  ∙  − ∙ (2 )
log XS
d1=
+ +

2
2

log XS
d2=
+(−
2
)
2
√
=  ∙  − ∙  −2 −  ∙ (−1 )
Where, Vcall is the price for an option call, Vput is the price for an option put, CND(d) is the Cumulative
Normal Distribution function, S is the current option price, X is the strike price, T is the time to
expiration
Outline
Introduction
Black-Scholes Model
Binomial Options Pricing Model
Trinomial Options Pricing Model
Improved Binomial Option Pricing
CPU-GPU Hybrid Parallel Binomial
Summary
Binomial Options Pricing Model (BOPM)
The Binomial Model was first proposed by Cox, Ross and Rubinstein in 1979.
Essentially, the model uses a “discrete-time” model of the varying price over time of the
underlying financial instrument.
Option valuation using this method is, as described, a three-step process:
1.
Price tree generation,
2.
Calculation of option value at each final node,
3.
Sequential calculation of the option value at each preceding node.
Binomial Options Pricing Model (BOPM)
1. Sup = S× u or Sdown = S× d
u =
1
d =  −  =
2. Max [( − ), 0], for a call option.
Max [(K −  ), 0], for a put option.
Where K is the strike price and  is the spot price of
the underlying asset at the ℎ period
3. Binomial Value = [p× option up + 1 − p ×
option down]× exp −r × ∆t
(−)∆ −
p=
−
Binomial Options Pricing Model (BOPM)
Use of the Model
Handling a variety of
conditions & Over a
period of time rather
than a single point
Slower than the BlackScholes formula but
more accurate, especially
for long-dated options
Less practical for options
with several sources of
uncertainty and
complicated features
Outline
Introduction
Black-Scholes Model
Binomial Options Pricing Model
Trinomial Options Pricing Model
Improved Binomial Option Pricing
CPU-GPU Hybrid Parallel Binomial
Summary
Trinomial Options Pricing Model
The Trinomial Tree was developed by Phelim Boyle in 1986.
It is an extension of the Binomial options pricing model, and is conceptually similar.
Under the Trinomial method, at each node, the price has three possible paths: an up, down and stable
or middle path.
Trinomial Options Pricing Model
The price of the underlying asset can be found by multiplying the
value at the current node by the appropriate factor u, d or m where,
=
2∆ ,d
=  −
2∆ (the
structure is recombining), m=1
And the corresponding probabilities are:

=
− ∆/2

=
∆/2
∆/2
−
− ∆/2
−  −
−
2
∆/2
− ∆/2
∆/2 −  − ∆/2
= 1 −  +
2
Trinomial Options Pricing Model
Use of the Model
More accurate than the
BOPM when fewer time
steps are modelled.
For vanilla options, the
binomial model is
preferred due to its
simple implementation.
For exotic options, the
trinomial model is more
stable and accurate,
regardless of step-size.
Outline
Introduction
Black-Scholes Model
Binomial Options Pricing Model
Trinomial Options Pricing Model
Improved Binomial Option Pricing
CPU-GPU Hybrid Parallel Binomial
Summary
Improved Binomial Option Pricing
It is proposed by Mohammad Zubair and Ravi Mukkamala in 2008.
This algorithm exploits the underlying memory hierarchy using cache blocking techniques.
Assume cache of the processor running Vanilla algorithm can hold up to m elements of the array.
Considering the nested loop which includes the outer and inner loop, we partition the
computation into a certain number of blocks. And therefore, we can fetch m elements of the
array into cache.
Improved Binomial Option Pricing
Improved Binomial Option Pricing
Outline
Introduction
Black-Scholes Model
Binomial Options Pricing Model
Trinomial Options Pricing Model
Improved Binomial Option Pricing
CPU-GPU Hybrid Parallel Binomial
Summary
CPU-GPU Hybrid Parallel Binomial
It is proposed by Nan Zhang et al. in 2012.
The hardware devices includes two CPU cores and a GPU.
CPU 1: communication & synchronization
CPU 2
Both share equal workload with each other.
Principle of Hybrid
GPU
To see the performance of the hybrid algorithm we did two groups of tests where L, the maximum number
of levels in a block, was set to 20 and 50, respectively.
CPU-GPU Hybrid Parallel Binomial
Speedup plots of the CPU parallel implementation and the hybrid implementation
Outline
Introduction
Black-Scholes Model
Binomial Options Pricing Model
Trinomial Options Pricing Model
Improved Binomial Option Pricing
CPU-GPU Hybrid Parallel Binomial
Summary
Summary
In order to improve the calculation efficiency, GPU computation became a promising tool for
option pricing.
We mainly focus on the parallel tree-based algorithms on option pricing.
The Black-Scholes Model is the theory basis of all the other algorithms.
All the other tree-based algorithms including the trinomial lattice are based on the method of
binomial lattice.
In the future, we will further improve the parallel algorithm on GPU to achieve better accuracy
and efficiency on option pricing.