Monte Carlo double barrier option pricing on GPU using C++ AMP

I converted the double barrier option pricing code from my last post to run on the GPU, using C++ AMP, and got an 80% speedup.

This is running on a low powered Acer V5-122p laptop with an AMD A6-1450 processor with an integrated Radeon HD 8250 GPU.

The gist is here: https://gist.github.com/taumuon/bbeeb9e2c1f5082a2699

To be fair, I converted the CPU code to be otherwise identical to the gpu code. Instead of populating an array of the sample path, it instead for each point just determines whether the value breaches the upper or lower barriers and uses the last value for the payoff.

This reduced the runtime from the code in my last blog post, of 2540ms, to 1250ms, i.e. a 2x speedup.

The GPU code was ran twice, the first time it ran in 140ms, the second run (after all shaders already compiled etc) was 15.6ms, i.e. a very impressive 80x speedup from the CPU code.

If anything, it shows that AMDs strategy of cheap low powered laptop chips will payoff if people start taking advantage of the relatively strong GPU.

Monte Carlo pricing of Exotic Options in Functional Style C++

My last blog post was about pricing of exotic options using F#. In that post I said “Apart from the Monte Carlo code, the fact that in F# all functions are in the curried form means that composing the payoff functions using partial function application is beautiful. This would be lambda hell to replicate in C#.”

The OO version of this would probably be built via composition: having a class implementing a IPayoff interface (implemented for Call and Put), and that would be used in implementations of IPathPayof, which would be implemented by AsianArithmeticMean, DoubleBarrier etc. The use of OO is to pull out the common implementation, but there’s no state associated with any of these classes – it feels much nicer using function composition.

I’ve implemented a version in C++ using lambdas, and the functional composition is actually really nice. C++ has the std::bind method which means that any number of parameters can be partially applied even for functions not in the curried form.

The code can be found here: https://gist.github.com/taumuon/727c31f4a56518f91718

The most surprising thing was the speed increase – the equivalent algorithm in C++ is 20x faster than the F# code! For instance, running on my low-powered AMD A6-1450 powered laptop, the double barrier option took 45 seconds to calculate in F#, whereas it took 2.2 seconds in C++.

I did tweak the F# to instead of using Seq.unfold to create the asset path, it instead creates and mutates an array, and that reduced the running time by more than 25%.

EDIT: Jack Pappas has forked and modified the F# code so that its runtime is now in the same ballpark as the C++ code. The fork is here: https://gist.github.com/jack-pappas/d629a767823ca2f17967

I think there’s scope to speed up both the F# and C++, by introducing parallelism and investigating GPGPU, which I hope to do if I don’t get sidetracked.

Monte Carlo pricing of Exotic Options in F#

I’ve recently completed all exercises for the MOOC Monte Carlo methods in Finance, ran by the University of Madrid on Iversity. The course was excellent, both in its content and delivery.

The course started off by refreshing probability theory (cdf, pdf etc) and quickly moved onto generating random numbers, Brownian motion and stochastic differential equations followed by the pricing of options and calculating risk.
The final week’s homework is on the Monte Carlo calculation of a portfolio’s risk, using copulas with Student’s t distribution, but as that week’s homework is still running I’m blogging about the penultimate week’s homework.

This homework is about pricing path dependent options, and demonstrating how using a control variate can provide a better result for the same number of iterations (better meaning less error, i.e. with a smaller standard deviation). The homework further shows that when pricing a barrier
option, using an up-and-out option as the control variate produces better results than using a European option as the control variate.

The course delivery was extremely slick. The videos were filmed specially, this wasn’t a rehashing of a lecture in front of students (as seems to happen in some other online courses). The lectures were short, and to the point, managing to cram a lot of information in with zero fluff. I really appreciated this as I was watching on a daily commute.

The assessments were by multiple choice question, but with only one attempt, so it did end up actually feeling like a challenge. The questions were a mixture of maths and coding, with the balance moving more towards coding as the weeks went on.
The code was delivered in Matlab, which I had to get reacquainted to after a decade break. The main downside I found is that I ended up doing a fair bit of copy-paste coding, so completed some of the homeworks in .NET instead. I personally found the coding easy, and found the maths more challenging (in a good way).

Now, for the code – the F# code is available here: https://gist.github.com/taumuon/11302896

Apart from the Monte Carlo code, the fact that in F# all functions are in the curried form means that composing the payoff functions using partial function application is beautiful. This would be lambda hell to replicate in C#.

If this course runs again I’d wholeheartedly recommend it.

MOOCs

I’ve just enrolled on Iversity’s Monte Carlo Methods in Finance course, and have converted some of week 1’s Matlab demo code over to F# and Deedle: https://gist.github.com/taumuon/8602365

I spent the latter half of last year diving into various online courses. I completed Coursera’s Mathematical Methods for Quantitative Finance, and also followed along with a number of other courses to varying levels of completeness.

I completed three weeks assignments of Udacity’s Cuda programming course.  Week three was painful due to an error in the reference code, and week 4 was crashing due to a memory exception. I was using a GPU emulator in Ubuntu, and decided that it would be easier with real hardware. I watched the remaining videos and found the parallel algorithms explanations useful.

I completed the first two weeks of Coursera’s Scientific Computing. These were maths exercises, which I enjoyed and that’s what inspired me to do the Maths Methods for Quant Finance course. The Matlab exercises I was planning to do in F#, but left the course when other attendees were complaining that to complete the homework to the correct numerical accuracy you needed the exact version of Matlab the instructor was using, and they were unable to use Gnu Octave.

It is great that there’s so much free high standard material available. The fixed timescale nature of the course is a bit annoying – if work or life gets in the way one week it may make it impossible to catch up with the remainder of the course. I may get around to trying a course again next time it comes around though.

Option pricing in F# using the Explicit Finite Difference method

It’s been a little while since I’ve coded any F#, so I’ve done a little coding kata to polish off the rust.

I’ve converted the explicit finite difference option pricing example from (Paul Wilmott Introduces Quantitative Finance).

Call

I followed similar steps as those I performed in my previous blog post on the binomial tree option pricing; I converted the VBA code into very similar looking imperative F# code, before refactoring out the loops into recursive calls.

It was a useful exercise as converting the algorithm made me actually focus on the mechanics of how it worked, much more than simply translating VBA code into imperative F#. It’d be interesting to hear in the comments whether people find it easy to read.

The code is available https://gist.github.com/taumuon/4999749.

Binomial Tree Option Pricing in F#

This post will look at implementing the binomial tree algorithm in an imperative style, and refactoring it to be more functional.

The wikipedia page on the binomial options pricing model provides pseudo-code for the pricing of an American Put option.

That code can be implemented almost identically in F#.

clip_image002_thumb25255B125255D

and is called as follows:

clip_image004_thumb25255B125255D

Functional programmers have probably died a little on the inside on seeing that code, but one of the good thing about F# being multi-paradigm is that it’s easy to take code of this form and implement it, and test it for correctness before refactoring.

I did actually look at whether the results of the code were as expected at this point, but I’ll cover this later in this blog post.

The first thing to do is to change the initial values V to be created more functionally:

clip_image00625255B425255D

 

 

Now, the main algorithm consists of two parts, an outer loop where each ‘level’ of the tree is calculated stepping up towards the root, using the results of the previous level’s nodes (the nodes nearest to the leaves). The inner loop iterates over all of the nodes at a given level calculating the option’s value at that node.

First off, the outer loop can be replaced with a recursive method:

clip_image00825255B425255D

The next change is quite minor – it’s for each pass of the inner loop to create a new array, instead of mutating the vi array:

clip_image01025255B425255D

This change now means that there’s no need for any mutable state, so the initial values can be created as a sequence instead of an array, and the inner loop can be written in a functional style:

clip_image01225255B425255D

I find this code style is clearer to understand than following the array mutations to see what each part of the code is doing and how those parts interact.

If I was implementing this in C# I’d probably change the variable names to be more descriptive (e.g. strikePrice, riskFreeRate etc) but as one of the key advantages of F# is its succinctness it makes more sense to leave the well-known symbols in. Anyone implementing the algorithm with knowledge of the domain would know what the symbols mean without the more verbose names.

Validating the results

The calculated option value with the requested parameters is 4.486090. Running the EqutyOptions example in the .NET port of QuantLib, QLNet (http://sourceforge.net/projects/qlnet), with the same parameters gives the following results:

clip_image01425255B425255D

The figures are in the same ballpark, but the difference is curious.

Chapter 45 of GPU GEMS 2  creates the initial values in this way:

clip_image016_thumb25255B125255D

 

This gives a result of 4.486375 which still doesn’t match QLNet, but is nearer.

The result of running the Cox version of Bubo’s code from here http://cs.hubfs.net/topic/None/59053 also equals 4.486375, which matches the results of using this initialisation function. As an aside, I like how that examples shows how F# partial function application allows the variations on the algorithm to be composed, and much more succinctly than using OO.

Bubo’s Tian model does match QuantLib’s result exactly. I’ll have to dig a bit deeper to figure out which variations on the binomial tree model these different examples are using.

The code is available here: https://github.com/taumuon/FSharp-Binomial-Tree