Serving the Quantitative Finance Community

 
User avatar
quartz
Posts: 3
Joined: June 28th, 2005, 12:33 pm

The ultimate Monte Carlo framework

November 25th, 2011, 6:43 pm

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: Traden4AlphaIt would seem that the guts of the engine would include:* Sample generators (RNGs, weighted sampling, antithetic sampling, low-discrepancy, etc.)* Sample functions (converts a "random number" to an application-specific quantity)* Path constructors (constructs an event path as a sum of function-mapped samples, including path-dependencies)* Event aggregators (aggregates across samples or paths to compute MC statistics, MC-based solution estimates, and MC quality estimates)* MC run managers (spawns/handles multiple MC runs such as with different application parameter values or MC control parameter values)On top of this would be an application layer that maps a user's domain application to a configuration of the MC engine components (e.g., defining sample generator, path constructor, event aggregator, etc.). The application layer could/should intermediate between a "friendly" interface on to MC and the more complex hardware-specific internals (e.g. SIMD/GPU details).Talking a data/task view, I see 3 'levels': 1) market/calibrated data and models 2) Simulated data (e.g. paths) and 3) MIS, high-level data and high-scenarios. These can be separately designed and they lead to parallel task and data decomposition. The above list of subtasks will be in one of the 3 parent tasks.Important in the engine are efficiency (very fast), functionality (what kinds of SDEs to support), maintainabiliy (add plug ins, narrow interfaces between components.).What do you think?Could you please explain a bit more this 3 levels view?In the meantime a few down-to-earth thoughts on the MC engine elaborating on T4A's ones, some of them obvious (but in need for explicit approval), others opening a Pandora vase...- antithetic variates: is it better to write a wrapper over existing random uniform *vector* generators, sending out antithetic pairs one component at a time (u1, 1-u1, u2, 1-u2...), thus leaving function sampling untouched and requiring only ex post fixes to sample variance estimators... or to proceed on the function as g(u):=(f(u)+f(1-u))/2? however this implicitly means that we actually need such an *explicit* f(u) interface somewhere! (which is often not the case) - both are ugly in some sense (we could refer to these two approaches "external AV" and "internal AV" for brevity).- control variates: what helpful infrastructure can be provided? the regression coefficient? most of the work must be done by users anyway implementing the actual control variate for each problem, and machinery for the controlled estimator seems a bit silly/trivial/superfluous, unless it's all about the coefficient and maybe controlling the bias from adaptivity.- support for QMC points/vectors - possibly unified with classic PRNGS; otherwise retrofitting LDS points to a univariate framework is feasible but ugly (=perverse) and unleashes a cascade of other issues (had to do it once; never again please!); the opposite adapter is the most sensible approach - other QMC support: lots of things (list never ends actually), but a minimum set would include at least fast quantiles, Sobol', bridging, PCA and smoothers/periodizers; I'd also love to be able to easily connect our adaptive LDS engine (both as LDS server as well as model "client") - simd/vector-readyness - meaning also that aggregation operators will need to operate on at least two levels; unless all data is cached for a final pass; and at the other end random generators might need changes/rewrites too.-- Are boost accumulators simd ready? I don't think so, especially quantiles, but at least first simple adapters can be prepared. -- There might also be interactions with the weighted sample topic below.- random generators: as for the two random syntaxes provided by boost/C++ I am not sure about which one is technically the best(definitely the simple nonuniform_sampler(uniform_RNG()) is best for novice users, but might have drawbacks... haven't really tried it in our framework yet). E.g. there might be issues with caching/persistency. - parallel PRNG/QMC streams support: there are 2(+1 fake) main approaches: split one huge stream in shorter chunks or use multiple generator parameters. In the first case there are 3 algos for on-the-fly calculations (only one is fast enough), or I could provide a set of ready generator states for MT or WELL (and then the WELL generator too). The second approach also requires slow precalculation for MT, but other generators might be faster (e.g. combined LCGs). In both approaches it's not trivial to deal with reproducibility of results (do we want it at all?); especially once load balancing gets into the game. - Or one simply "randomly" initializes generator states and *hopes* for nonoverlaps/noncorrelation (but this is a strange bet with unwarranted assumptions).- kind of parallel engine: embarassingly parallel is easy, but obviously a realworld MC engine should do much more: how to best parallelize early exercise? adaptive methods (even a simple control variate!)? accumulators such as quantile? subsimulations? and what about load balancing? without forgetting that distributed systems, SMP and SIMD all raise different issues which will interact... - Instead of dealing with shared objects first and later going distributed, I would think about serialization&c from the start, retrofitting might become a pain. One might forget about SMP peculiarities at first and start with something more general; optimized algos for SMP can always be added later. Clearly this topic interacts a lot with the other discussion between static vs dynamic polymorphism vs components&signals (which warrants a dedicated thread imho).- early exercise algos: if we want to provide something automatic, here is a big question mark: LS is definitely not enough, how advanced do we want to go? - AND shall the framework be closed/blackbox or open to (intrusive) third party algos? not an easy design issue!- subsimulation: nowadays the MC engine should be able to handle multiple levels of simulation: derivative portfolio VaR is already >=2 levels. Some (american) pricers already have 2 simulation levels by themselves, and it's easy with credit and multiperiod optimization to get to 3-4 levels and beyond. This will become more and more common so the framework should be ready (there are also specific algorithms improving results in such situations; also some QMC developments might help; and of course in some of the cases one might just use regression). Especially if we want the lib to be used for pretrade simulation it must all be damn FAST. This is a Major Point imho, otherwise it's just YetAnotherQuantLib.- weighted samples: unify their treatment, they come from various sources: stratified/importance sampling&measure changes, weighted MC/entropy pooling, unequal weight integration rules... they need to be supported atleast by aggregators: quantiles, moments, regressions, early exercise... better a uniform concept for weight+sample pair or an explicit type? as the coupling is there for algorithmic reasons anyway, it's probably better to go for the type. Still I'm not an expert in metaprogramming so I'd be glad if someone could check what boost::accumulators is doing with those binary operators in numeric::functional exactly.--weighted samples must allow for vectors (e.g. for regression with importance sampling)! per se obvious, but: what about vector/matrix containers, as they are not as lightweight as scalars?- in general everything should work on vectors (or tensors) so as to have a unified interface to multivariate distributions, see also the requirements of antithetic variates, QMC, etc...- GPU will be a mess, just a reminder :-)There'd be other issues, but better stop here for now Here requirements and less mature thoughts are mixed because I feel one major topic is reaching modularity while satisfying interoperability required by numerical constraints, so it's better to discuss all together first. Just two cents.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

The ultimate Monte Carlo framework

November 27th, 2011, 9:30 am

Hi quartz,QuoteCould you please explain a bit more this 3 levels view?Since DevonFangs wants the ultimo MC engine, a design based on proven software techniques is needed imo. So, issues such as information hiding, decomposition and patterns are needed.To take an example in the case of 1 factor, the 3 levels are:1. SDE part (manufacturing model)2. FDM/numerics part (tracking model)3. High-level MIS info (e.g. statistics, post-processing convergence results, VAR)This process can be generalised.Design each subsystem until we get to patterns and code. This approach is used by many software designers. AFAIK this approach is needed if you want a parallel solution as bottom-up OO approach is not so easy to parallelise. The list of 'features' posted by quartz and T4A will be placed on some subsystem when we get to the algorithm design phase. QuoteEspecially if we want the lib to be used for pretrade simulation it must all be damn FAST. This is a Major Point imho, otherwise it's just YetAnotherQuantLib.Thus, I would avoid GOF Observer and deploy design 'parallel' from day 1. Use signals-based Propagator pattern is more flexible. Quote GPU will be a mess, just a reminder :-)I believe you. QuoteI feel one major topic is reaching modularity while satisfying interoperability required by numerical constraints, so it's better to discuss all together first.Yes. And add speedup.The main effort is the assembly of all the bespoke 'interoperable' building blocks (which you already completed?) into the main design.
Last edited by Cuchulainn on November 26th, 2011, 11:00 pm, edited 1 time in total.
 
User avatar
FinancialAlex
Posts: 1
Joined: April 11th, 2005, 10:34 pm

The ultimate Monte Carlo framework

December 10th, 2011, 3:56 pm

In my opinion we could also get inspiration from the framework/code laid out in the second edition of Design Patterns book of Mark Joshi for the exotic Monte Carlo engine Here is a class diagram of all the classes in the book
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

The ultimate Monte Carlo framework

December 12th, 2011, 4:28 pm

Status update.I have now completed a loosely-coupled, customisable MC engine based on several programming styles (FP, OOP, GP and procedural). I use a number of Boost and STL libraries and the engine is a V2 version of a previous 'pure' OO engine.The engine is for 1-factor but n-factor is not difficult. The code is not documented as such but it is readable. Having Boost signals and function is a major shift imo. It means we can write s/w like h/w.I will deliver the full code in a few days. Thijs, sandbox or zip file? The same kind of design can be applied to other systems.
Last edited by Cuchulainn on December 11th, 2011, 11:00 pm, edited 1 time in total.
 
User avatar
DevonFangs
Topic Author
Posts: 0
Joined: November 9th, 2009, 1:49 pm

The ultimate Monte Carlo framework

December 12th, 2011, 4:54 pm

QuoteOriginally posted by: CuchulainnStatus update.I have now completed a loosely-coupled, customisable MC engine based on several programming styles (FP, OOP, GP and procedural). I use a number of Boost and STL libraries and the engine is a V2 version of a previous 'pure' OO engine.The engine is for 1-factor but n-factor is not difficult. The code is not documented as such but it is readable. Having Boost signals and function is a major shift imo. It means we can write s/w like h/w.I will deliver the full code in a few days. Thijs, sandbox or zip file? The same kind of design can be applied to other systems.Very very cool.
 
User avatar
FinancialAlex
Posts: 1
Joined: April 11th, 2005, 10:34 pm

The ultimate Monte Carlo framework

December 14th, 2011, 10:50 am

QuoteOriginally posted by: outrunIf you want contribute a design like this then please do! One thing we could use to move forward is people who start contributing themselves. Cuch is working on something build around boost::signals, maybe that can be aligned with the Joshia-tree?Nice play of words with Joshia/Joshua tree I was not clear what was the contribution process, but then Daniel's later post clarified it. I will try to have something available in next 2 weeks
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

The ultimate Monte Carlo framework

December 14th, 2011, 7:24 pm

QuoteThese are two types of programming styles here. Some like this type of classic OO coupled design structures with classes, inheritances etc. i expect there will eventually be various design and libs.we should give various designs sensible names, reflecting the chosen design model (OO GOF?) and showing the destinctions. AlongsideOOPGPthere are Functional and Procedural models. The pioneer of multi-paradigm C++ is Jim Coplien I think it is wortth taking a wee bit of time to read what he has written. He is a C++ guru.My take is OOP == models ISA and HASA relationships (thus, classses)GP == generic data structures and dataFP = the glue/interfaces between modulesProcedural == configuration at highest levelAnd developers use a mix of these and I think we must take this into account.
Last edited by Cuchulainn on December 13th, 2011, 11:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

The ultimate Monte Carlo framework

December 16th, 2011, 1:04 pm

Monte Carlo Engine 101 using Domain Architectures and Boost C++ Libraries2011-12-16 startVersion 0.72Introduction and ObjectivesIn this chapter we examine the well-known problem of pricing a plain one-factor option using the Monte Carlo method. This problem is easy to understand and to program, for example in pseudocode (Clewlow 1998), VBA, C and finally in C++ using system decomposition techniques and design patterns (Duffy 2010). The single-paradigm approach taken leads to inflexible software systems and to this end we wish to take a new defined plan to analyse, design and implement software systems (and in particular a system for the Monte Carlo method). To this end, we bring together a number of methods, techniques and software tools that allow us to create maintainable, interoperable and adaptable software systems. We achieve these ends by using system decomposition methods, multi-paradigm design and Boost C++ libraries whenever possible:. We model the current Monte Carlo application as a special case of a RAT (Resource Allocation and Tracking) domain architecture (Duffy 2004) which allows us to find the initial set of components and modules that cooperate to satisfy system needs. Each component is highly cohesive and it must be loosely coupled to other components.. We explicitly model each component?s provides and requires interfaces. In particular, we require the delivered software system to implement an ADL (Architecture Definition Language, see Leavens 2000). Object-oriented technology has no provision for modelling requires interfaces and hence it is unsuitable as a means of implementing component interfaces. Instead, we employ the functional programming model to implement component interfaces. This ensures loose coupling between components. It also means that we can replace one component by another component having the same interface at run-time.. We employ a combination of the procedural, object-oriented, generic and functional programming models to implement the current software system. System and user requirements determine which model is most suitable in which part of the design. We have already discussed this topic.. Appropriate application of Design Patterns (GOF 1995). In the current version we use the Visitor pattern in order to extend the functionality in the system.. We strive to use standardised C++ libraries rather than creating our own libraries. In particular, Boost and STL provide much of the functionality that is needed in the current application: . uBLAS library: vectors and matrices to model data structures. . Random library: creating random numbers (Mersenne Twister, Lagged Fibonacci).. Higher-order function libraries such as Boost Function, Bind and Signals (Signals2). We also use C++ 11 lambda functions in combination with STL algorithms. . Timer library: this allows us to report on elapsed computing time.We now discuss the design and implementation of this system. You also can examine the code, run it and see how the parts fit together....Conclusions and Summary In this chapter we have designed and implemented a model problem from a design and multi-paradigm viewpoint. We have created a defined software process that formalises and externalises implicit assumptions and work practices in software development. It is possible in a second iteration of the project lifecycle to generalise the design the Monte Carlo system to multi-factor GBM and jump models. In a later chapter we shall show how to design a Finite Difference Engine using the same principles.//C++ project; used VS2010Run the code!. Source: TestMC.cpp, NormalGenerator.cpp. Specify additional directories for Boost .hpp and .lib files
Attachments
MCEngine001.zip
(24.26 KiB) Downloaded 90 times
Last edited by Cuchulainn on December 15th, 2011, 11:00 pm, edited 1 time in total.
 
User avatar
rmax
Posts: 374
Joined: December 8th, 2005, 9:31 am

The ultimate Monte Carlo framework

December 16th, 2011, 2:53 pm

Excellent - it this the first building block complete?
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

The ultimate Monte Carlo framework

December 17th, 2011, 10:29 am

Quartz,Some initial responses to you list, now that we have an initial model up and running. In general, we need to determine in which subsystem the new features 'live' and what impact this will have on 'provided' and 'required' interfaces:Please feel free to comment on these initial feedback.1.- antithetic variates: is it better to write a wrapper over existing random uniform *vector* generators, sending out antithetic pairs one component at a time (u1, 1-u1, u2, 1-u2...), thus leaving function sampling untouched and requiring only ex post fixes to sample variance estimators... or to proceed on the function as g(u):=(f(u)+f(1-u))/2? however this implicitly means that we actually need such an *explicit* f(u) interface somewhere! (which is often not the case) - both are ugly in some sense (we could refer to these two approaches "external AV" and "internal AV" for brevity).On the one hand, this is just another way to generate the path for S. But the random numbers are generated differently? We have pairs replication instead of independent replication. The choice will depend on option type and OTM etc.2.- control variates: what helpful infrastructure can be provided? the regression coefficient? most of the work must be done by users anyway implementing the actual control variate for each problem, and machinery for the controlled estimator seems a bit silly/trivial/superfluous, unless it's all about the coefficient and maybe controlling the bias from adaptivity.I think a simple wrapper should work in this case?3.- support for QMC points/vectors - possibly unified with classic PRNGS; otherwise retrofitting LDS points to a univariate framework is feasible but ugly (=perverse) and unleashes a cascade of other issues (had to do it once; never again please!); the opposite adapter is the most sensible approach - other QMC support: lots of things (list never ends actually), but a minimum set would include at least fast quantiles, Sobol', bridging, PCA and smoothers/periodizers; I'd also love to be able to easily connect our adaptive LDS engine (both as LDS server as well as model "client") Can you give an example?4.- simd/vector-readyness - meaning also that aggregation operators will need to operate on at least two levels; unless all data is cached for a final pass; and at the other end random generators might need changes/rewrites too.In my 101 design I have the MC engine and MCPostProcess (potentially concurrent) modules. I now shovel the generated path data to MCPostProcess.5.-- Are boost accumulators simd ready? I don't think so, especially quantiles, but at least first simple adapters can be prepared. -- There might also be interactions with the weighted sample topic below.Don't know; is it not possible to use it sequentially?6.- random generators: as for the two random syntaxes provided by boost/C++ I am not sure about which one is technically the best(definitely the simple nonuniform_sampler(uniform_RNG()) is best for novice users, but might have drawbacks... haven't really tried it in our framework yet). E.g. there might be issues with caching/persistency. We can make it customisable.7.- kind of parallel engine: embarassingly parallel is easy, but obviously a realworld MC engine should do much more: how to best parallelize early exercise? adaptive methods (even a simple control variate!)? accumulators such as quantile? subsimulations? and what about load balancing? without forgetting that distributed systems, SMP and SIMD all raise different issues which will interact... Loops-level parallelism is possible in MC 101 but we worry about non-reentrant RNGs. Another parallel pattern is Producer-Consumer.8.- early exercise algos: if we want to provide something automatic, here is a big question mark: LS is definitely not enough, how advanced do we want to go? - AND shall the framework be closed/blackbox or open to (intrusive) third party algos? not an easy design issue!We need standardised interfaces between us and external packages.Which subsystem would you put the early exercise code in? Can it run concurrently with the MC engine?9.- subsimulation: nowadays the MC engine should be able to handle multiple levels of simulation: derivative portfolio VaR is already >=2 levels. Some (american) pricers already have 2 simulation levels by themselves, and it's easy with credit and multiperiod optimization to get to 3-4 levels and beyond. This will become more and more common so the framework should be ready (there are also specific algorithms improving results in such situations; also some QMC developments might help; and of course in some of the cases one might just use regression). Especially if we want the lib to be used for pretrade simulation it must all be damn FAST. This is a Major Point imho, otherwise it's just YetAnotherQuantLib.I think these are "higher-order" aggregation/consolidation systems on top of MC 101. One this is sure: we do not need a classic Observer pattern. 10.- in general everything should work on vectors (or tensors) so as to have a unified interface to multivariate distributions, see also the requirements of antithetic variates, QMC, etc...Should we agree in Boost uBLAS and multi array since these are shipping now?11. Instead of dealing with shared objects first and later going distributed, I would think about serialization&c from the start, retrofitting might become a pain. One might forget about SMP peculiarities at first and start with something more general; optimized algos for SMP can always be added later. Clearly this topic interacts a lot with the other discussion between static vs dynamic polymorphism vs components&signals (which warrants a dedicated thread imho).Having loosely coupled components, one possibility is to use proxies to hide details of local/remote access, like DCOM, Corba. I agree that we should design to support both shared and distributed up-front. Using Boost function allows us to bind to almost anything.
Last edited by Cuchulainn on December 16th, 2011, 11:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

The ultimate Monte Carlo framework

December 17th, 2011, 10:29 am

..
Last edited by Cuchulainn on December 16th, 2011, 11:00 pm, edited 1 time in total.