Hello,Is Boost.Random threadsafe and can it be used in parallel monte carlo simulation on a multicore processor?

Have they switched off Google in your area?http://stackoverflow.com/questions/2920 ... -boost-rng

Quotehttp://stackoverflow.com/questions/2920497/thread-safty-of-boost-rngIt is a good question by OP.Putting a mutex around the rng would ensure serial equivalence but speedup is impaired. A better solution might be a Producer-Consumer solution with n RN producers and m consumers (path evolvers). If you know some graph theory/scheduling service algos allows us to determine what the multiplicity n:m should be (n << m?) Putting mutexed RNG in the simulation loop is not wrong but is a bottleneck.Here is an example of PC in Boost Thread So, RNG that is re-entrant, thread-safe and speedup_ed. How? No clear solution has been given in the literature AFAIK. Maybe @quartz has some ideas? edit: another option would be to assign a separate engine to each thread (e.g. MT to t1 and lagged Fibonacci to t2). The issue might that the generated RNs from the engines be independent. The seed will need to be 'good'? (maybe generate a random Boost UUID). In any case this solution is thread-safe and has good speedup.

We've implemented the efficient jump ahead procedure in our version of Mersenne Twister. It works pretty well, but the time to make the big jump is large compared to spawning threads so we create a random number generator pool with K generators lagged 2^10000 steps apart.

QuoteOriginally posted by: JimWe've implemented the efficient jump ahead procedure in our version of Mersenne Twister. It works pretty well, but the time to make the big jump is large compared to spawning threads so we create a random number generator pool with K generators lagged 2^10000 steps apart.Is this code public domain? Or would it be easy to customise the algorithm to suit current needs?

I would recommend having a look at the TRNG library (http://numbercrunch.de/trng/) . It is well suited for multicore and also message-passing parallelism.

QuoteOriginally posted by: katastrofaHave they switched off Google in your area?http://stackoverflow.com/questions/2920 ... t-rngSorry my initial question was not phrased correctly, let me rephrase it:Is it possible to use Boost.Random in parallel monte carlo simulations *without introducing intercorrelations* in my simulations. Thread safety is a first requirement but it's not enough. Parallel rngs are implemented using basically 3 techniques:- Initialize the same rng with different parameters.- Block splitting: the random sequence is broken down by the rng in k non overlapping subsequences. Each subsequence is then assigned to a specific processor/core by the rng. - Leapfrogging. Basically spread the sequence of random variates across processors like a deck of cards is dealt in turn to players.Off course the rng should be designed in such a way to implement one or all the above-mentioned techniques. Obviously Boost does not implement these techniques and therefore is not suitable as a parallel rng library. I m actually amazed that they overlook such functionality. As bojan mentioned Tina TRNG does implement the Block splitting and leapfrogging techniques. The block splitting method is explained in the link provided by Jim.

QuotePutting a mutex around the rng would ensure serial equivalence but speedup is impaired. A better solution might be a Producer-Consumer solution with n RN producers and m consumers (path evolvers). If you know some graph theory/scheduling service algos allows us to determine what the multiplicity n:m should be (n << m?) Putting mutexed RNG in the simulation loop is not wrong but is a bottleneck.Here is an example of PC in Boost Thread So, RNG that is re-entrant, thread-safe and speedup_ed. How? No clear solution has been given in the literature AFAIK. Maybe @quartz has some ideas? edit: another option would be to assign a separate engine to each thread (e.g. MT to t1 and lagged Fibonacci to t2). The issue might that the generated RNs from the engines be independent. The seed will need to be 'good'? (maybe generate a random Boost UUID). In any case this solution is thread-safe and has good speedup.It s more about guaranteeing that there are no intercorrelations in your simulations. Random seeding does not guarantee that. Thread safety, although is a requirement for a rng, will not guarantee lack of intercorrelations in the random sequences. You could also indeed assign a different rng to each thread, but it would be easier to use the parameterization technique: for each thread initialize the same type of generator with different parameters. For example Mersenne Twister can be initialized with 1024 parameter sets.

QuoteYou could also indeed assign a different rng to each thread, but it would be easier to use the parameterization technique: for each thread initialize the same type of generator with different parameters. For example Mersenne Twister can be initialized with 1024 parameter sets. Like in the spirit of creating a tempering matrix? here

> Is this code public domain?Sorry, Daniel, it is not.> Or would it be easy to customise the algorithm to suit current needs? It is not that hard to do. In MT19937 you extract the 624 bit state vector, apply a jump polynomial for the size of jump you wish to do, and then replace the state vector with the transformed vector. We've precomputed the jump polynomials for 2^(10000+k) where k=0,1,...,15. Given a 16 bit sequenceID, for each bit, k, which is non-zero we apply the k-th jump polynomial.So the overall procedure goes like this:1) Instantiate the base RNG with the user specified seed.2) Create a pool of K RNGs where the 0th member is the base RNG and all others are clones of the base jumped forward using sequenceIDs 1..K-1.3) Each thread has its own unique sequenceID which is used as an index into the RNG pool.

> I would recommend having a look at the TRNG library (http://numbercrunch.de/trng/) . It is well suited for multicore and also message-passing parallelism. When last I looked, the TRNG library only had the jump ahead implemented for L'Eculer's linear congruential RNGs, not the Mersenne Twister. If that works for you, great!!

QuoteOriginally posted by: Jim> I would recommend having a look at the TRNG library (http://numbercrunch.de/trng/) . It is well suited for multicore and also message-passing parallelism. When last I looked, the TRNG library only had the jump ahead implemented for L'Eculer's linear congruential RNGs, not the Mersenne Twister. If that works for you, great!!Coming back to my original question, why did Boost.Random pass over parallel generators? I mean in a world of multicore processors this is a serious omission. If I m not mistaken the Boost random number generation facility has been included in the C++11 standard?This means that the new random number generation facility is useless when considering parallel monte carlo. Am I missing something?