SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
AndreyShihov
Topic Author
Posts: 15
Joined: August 12th, 2019, 2:38 pm

Parallel programming in Finance

August 16th, 2019, 10:19 am

Hello all,

I've been looking where I could use and improve my TPL C# skills in Finance?

I have done MCS for some path-dependent option pricing in python before. Done it again in C# TPL and improved performance almost 20 (Edit: should be 200) times on the same machine (8 cores). It is pleasant result but delightfully parallel fork-join implementation (I think it's most rational one in this case. minimum context switches and there is nothing to synchronise) is too simple. 

I have also done Basket Defaults Swap MCS pricing in python in the past. If I'll do it with TPL I'll end up with the same approach as in previous case. Another thing that puts me off doing it is the fact that MC isn't the most efficient method compared to FFT and Hull-White Recursion anyway. 

I've looked at american option pricing with MC (Boyle, Broadie and Glasserman 97). I might have just scratched the surface but my intuition whispers me that quite often MC is going to be simple to parallelise. Whereas considering my software development experience in finance I might be mistaking. 

I think (but I'm not sure) that algotraiding might need more advanced parallelism solutions than MC. So my next move is to dissect pyalgotrade and try to find if I could speed it up a bit with C#, TPL and other tools. Is it reasonable plan purely for exercise? Otherwise what would you suggest for stretching my neurons and fingers?

I'm waiting for CQF results coming in September and have one month for fun before I'll throw myself back at job market. 

Thanks!
Last edited by AndreyShihov on August 19th, 2019, 11:15 am, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 60501
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Parallel programming in Finance

August 16th, 2019, 1:15 pm

I would look into the full lifecycle of swap trading by extending your expertise to ADO.NET, P(LINQ) and possibly Reflection  API and profiling system throughput.

And Excel-DNA interfacing.

And the new-fangled TPL Dataflow?

http://hamidmosalla.com/2018/08/04/what ... we-use-it/

See C# book by Germani and Duffy for more pointers.
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik
 
AndreyShihov
Topic Author
Posts: 15
Joined: August 12th, 2019, 2:38 pm

Re: Parallel programming in Finance

August 16th, 2019, 4:07 pm

I would look into the full lifecycle of swap trading by extending your expertise to ADO.NET, P(LINQ) and possibly Reflection  API and profiling system throughput.

Thanks Cuchulainn,

Sorry, I didn't mention, I work with C# 16+ years. Know most important perks of ADO.NET & EF as well as their bottlenecks pretty well. Working with Link for 6+ years. Have an intuition about PLink. Nice for quick and dirty solutions (plinq fans, pardon me), but perhaps not as flexible when need to solve a problems of a different class e.g beyond simple partitioning, e.g tricky balancing and synchronisation issues. 

Built in Visual Studio (OS) Profilers, Sysinternals, Concurrency Visualiser, ILSpy, SharpLab, PerfView, Benchmark.NET highly respected and often used tools.

Very interested about swap trading lifecycle. Germani and Duffy?

And Excel-DNA interfacing.

One of the Excel Datasources is WebAPI. If it worth doing for one Excel User it might be useful for many in Organisation. I've not tried it yet but I think it's possible to use Servers Infrastructure for Parallel or even Distributed computations to be available over WebAPI. Just pass data as query string parameters to WebAPI, make servers hot and get fast results.

And the new-fangled TPL Dataflow?

http://hamidmosalla.com/2018/08/04/what ... we-use-it/

Thanks, nice article and tool, worth keeping in mind, as well as below "When not to use it" point: Performance is very important, because TPL Dataflow is an abstraction over thread etc.

I found an interesting project in comments: https://github.com/JasperFx/jasper. Might work as plan H if won't find anything else.

See C# book by Germani and Duffy for more pointers.

I found an online preview. It's a good book, especially for c# advanced beginners. Way better than "Applied C# in Financial Markets". However, I find it hard to justify the way how MCS (Monte Carlo Simulation) was implemented with Producer/Consumer pattern. Page 724. Producer produces RNGs and Consumer uses them to run MCS. Obvious disbalance and unnecessary use of BlockingCollection data structure. I won't buy it right away and give it a chance by looking at other chapters. I'm sure I'll find something interesting and then decide. 
Last edited by AndreyShihov on September 2nd, 2019, 2:41 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 60501
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Parallel programming in Finance

August 16th, 2019, 4:58 pm

Thanks for the detailed feedback, AndreyShihov

For MonteCarlo, I ported single-threaded code to C++ Asynchronous Agent library. Can't remember speedup but it should be good for load balancing I reckon.

https://docs.microsoft.com/en-us/cpp/pa ... ew=vs-2019

In this case C++/CLI should be doable for this?

// Granted, Producer Consumer with Blocking might not be the most efficient solution.
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik
 
AndreyShihov
Topic Author
Posts: 15
Joined: August 12th, 2019, 2:38 pm

Re: Parallel programming in Finance

August 22nd, 2019, 1:33 pm

OK, I've done MC Lookback Pricing with Simple Parallel Fork/Join, Blocking Collection and Concurrent Queue. Latter two Producer/Consumer.
2_500_000_000 (50K x 50K)
The winner is: Delightfully Parallel Fork/Join. 
First point: Speed - 40 sec (on my laptop). 10 seconds faster than Concurrent Queue and 15 seconds faster than Blocking Collection.
Second point: Simplicity to tune up. Just number of partitions to fork to per CPU. Each partition generates its own set of random numbers, then simulate paths. 

The other 2 approaches are implemented as Producer/Consumer. Producer generates set of random numbers, consumer simulate paths. Main disadvantage: too many parameters to tune up. First partitioning, then level of parallelisation for each end to get closer to Delightfully Parallel. I tried to set bounds on a blocking collection (that's what it's been build for) but tuning level of parallelisation individually for each end provided better results. 

Seems that doing both things at the same time on the same machine is a bit fiddly. I'll try to split it and get a buffer of random numbers generated elsewhere and filled up over the network. 

Edit: I have progressed this farther and got betters times. See posts below.
Last edited by AndreyShihov on August 28th, 2019, 6:56 am, edited 2 times in total.
 
User avatar
Cuchulainn
Posts: 60501
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Parallel programming in Finance

August 22nd, 2019, 1:50 pm

Nice booklet on .NET parallel patterns

http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik
 
User avatar
Cuchulainn
Posts: 60501
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Parallel programming in Finance

August 22nd, 2019, 2:14 pm

Just one issue: the danger of race conditions and correlation between random number generation (grey area: are .NET rngs thread-safe??)
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik
 
AndreyShihov
Topic Author
Posts: 15
Joined: August 12th, 2019, 2:38 pm

Re: Parallel programming in Finance

August 22nd, 2019, 3:01 pm

Just one issue: the danger of race conditions and correlation between random number generation (grey area: are .NET rngs thread-safe??)
Thanks for the book, I'll have a look.

Good question. Thanks for reminding. I've used MathNet.Distributions.Normal with Box-Muller algorithm. I'll be able to compare by filling the buffer from separate machine and single thread. Quick empirical uniformity test, maybe. If I'll have more time, maybe dig into TestU01 subject, but it's not at the top of the list at the moment.
 
User avatar
Cuchulainn
Posts: 60501
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Parallel programming in Finance

August 22nd, 2019, 7:50 pm

AFAIK Math.Net has thread-safe MT 19937 RNG

https://numerics.mathdotnet.com/api/Mat ... wister.htm
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik
 
AndreyShihov
Topic Author
Posts: 15
Joined: August 12th, 2019, 2:38 pm

Re: Parallel programming in Finance

August 23rd, 2019, 7:20 am

Nice booklet on .NET parallel patterns

Figured out that I've already read that book. There is free pdf online. It's a really good book that gives quick overview about TPL, patterns and antipatterns. 
 
User avatar
Cuchulainn
Posts: 60501
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Parallel programming in Finance

August 23rd, 2019, 9:32 am

I really like that book too. Very good writers. There's also a C++ equivalent. 
https://epdf.pub/a-parallel-programming ... ition.html

I have applied many of these patterns in my Financial Instrument Pricing using C++, 2nd edition, for MC and PDE.

Here is an architecture for MC that I have parallelised. It is language-independent.
Attachments
MC Application.pdf
(736.97 KiB) Downloaded 72 times
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik
 
AndreyShihov
Topic Author
Posts: 15
Joined: August 12th, 2019, 2:38 pm

Re: Parallel programming in Finance

August 25th, 2019, 5:41 pm

Thank you for sharing, it is very interesting. I'm looking at it. I'll send you my implementation a bit later. Would be interesting to hear your opinion about the design!
 
User avatar
Cuchulainn
Posts: 60501
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Parallel programming in Finance

August 25th, 2019, 7:06 pm

Thank you for sharing, it is very interesting. I'm looking at it. I'll send you my implementation a bit later. Would be interesting to hear your opinion about the design!
Sure, I would like that. You have my email address dduffy ... datasim.nl.

BTW here is a design I used for Monte Carlo in C#.
http://www.datasimfinancial.com/forum/v ... =33&t=1219

Just out of curiosity, Andrey, do you use the CRTP pattern in C# (in C++ it is very efficient)
https://zpbappi.com/curiously-recurring ... in-csharp/
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik
 
AndreyShihov
Topic Author
Posts: 15
Joined: August 12th, 2019, 2:38 pm

Re: Parallel programming in Finance

August 28th, 2019, 6:53 am

BTW here is a design I used for Monte Carlo in C#.
http://www.datasimfinancial.com/forum/v ... =33&t=1219

Thanks, I'll have a look.

Just out of curiosity, Andrey, do you use the CRTP pattern in C# (in C++ it is very efficient)
https://zpbappi.com/curiously-recurring ... in-csharp/

IMO such things comes handy when you do hard-core engineering. Build a library or framework. Preferably it has to be hidden from end users to reduce cognitive load and allow focus on actual problem. Interesting discussion: https://blogs.msdn.microsoft.com/ericlippert/2011/02/03/curiouser-and-curiouser/


I rarely do engineering (unfortunately) because it's totally different class of problems to solve. Most of the time I develop software that has business value following these rules: 
  • Good memory management (in C#)
  • Use of nice and clean patterns that helps to understand, maintain, extend and test the code
  • CLR friendly code and good use CPU cache lines :) (also C#)

And update on my current project. I've managed to get path-dependent lookback option price with 50Kx50K simulations (2_500_000_000 cycles) down to 20 seconds (Edit: this number is incorrect, I found a bug), with thanks to Producer/Consumer Work Stealing algorithm. All other approaches of the same pricing stabilised at 36 seconds. So I've got a new wiener. Only one problem left is LOH allocations. Looking into it now.
 
User avatar
tekavec
Posts: 1
Joined: August 26th, 2019, 6:19 am

Re: Parallel programming in Finance

August 31st, 2019, 8:47 pm

I addition to very good suggestions before me, I'd also recommend investing some time in functional programming, aiming to write pure functions which are easy to parallelise (and unit test). In .NET world you can start with functional C# (e.g. "Functional programming in C#" by Enrico Buonanno is a very good one) or if you have more time and want to go step further, F# can be also a very good long-term investment.

Best,
Tomaz
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On