All, I have a question which is not related directly to boost. I am writing a multithreaded application and would like to make use of a multiprocessor machine in order to speed up our Monte Carlo simulation engine. We make use of the random number package (random number distributions). My question is: making the random number generator a global variable (object) it is possible to use it in several threads at the same time -> does it mean that the random sequences will be repeated and the entire simulation will be simply a repetition of n non-random sequences? This can be avoided when a lock is acquired on the random number generator and at a given time just one thread can access the rng and the advantage of the multiprocessor machine is lost. Can you advise? Thanks Pshemek -------------------------------------------------------- If you are not an intended recipient of this e-mail, please notify the sender, delete it and do not read, act upon, print, disclose, copy, retain or redistribute it. Click here for important additional terms relating to this e-mail. http://www.ml.com/email_terms/ --------------------------------------------------------
Sliwa, Przemyslaw (London) wrote:
All,
I have a question which is not related directly to boost.
For future reference, from: http://www.boost.org/more/discussion_policy.htm It would seem that this probably belongs in a newsgroup (such as comp.lang.c++.moderated - I could be wrong, being new, just thought I'd point this out).
I am writing a multithreaded application... [*snip*] My question is: making the random number generator a global variable (object) it is possible to use it in several threads at the same time -> does it mean that the random sequences will be repeated and the entire simulation will be simply a repetition of n non-random sequences?
This depends on the RNG used - most are not thread safe, and depending on the generator the same number will have a tendancy to come up repeatedly.
This can be avoided when a lock is acquired on the random number generator and at a given time just one thread can access the rng and the advantage of the multiprocessor machine is lost. Can you advise?
Assuming that 100% of your time is spent getting RNGs - I don't know the details of the simulation you're working on... but an absolute 100% is impossible for anything useful (e.g. it amounts to an optimized "while( 1 ) { rand(); }"). That said, the (un)locking overhead may offset any benifits, profile this to confirm this is a concern. Unless you need to be able to repeat a sequence for some reason, multiple RNGs (one per thread) with seperate seeds should work (and may even work for repeatable simulations, with the proper conditions). There's also hardware RNGs that depend on quantum physics to produce truely random numbers, although I don't have the links stored, which I'm sure could be used effectively. Further, assuming less than 50% of your time (for a dual-processor system) is spent actually generating the numbers, you could have one thread in charge of number generation, filling up random number pools for each thread (and pausing when each thread has it's own pool up to high enough levels). Of course, such techniques should be covered in a good book on multithreading... Hope this helps. -Mike
Hi, On Wed, 1 Jun 2005 09:10:49 +0100 "Sliwa, Przemyslaw (London)" <Przemyslaw_Sliwa@ml.com> wrote:
I have a question which is not related directly to boost. I am writing a multithreaded application and would like to make use of a multiprocessor machine in order to speed up our Monte Carlo simulation engine. We make use of the random number package (random number distributions). My question is: making the random number generator a global variable (object) it is possible to use it in several threads at the same time -> does it mean that the random sequences will be repeated and the entire simulation will be simply a repetition of n non-random sequences? This can be avoided when a lock is acquired on the random number generator and at a given time just one thread can access the rng and the advantage of the multiprocessor machine is lost. Can you advise?
in my opinion the Boost random number generators are not qualified for parallel applications. You need a mechanism to distribute streams of random numbers in an _controlled_ way over the parallel processes. One way to do this is the leap frog method. With three CPUs the original stream original 1 2 4 6 2 5 1 5 2 4 6 4 6 2 3 1 1 6 would be distributed like this CPU 1 1 6 1 4 6 1 CPU 2 2 2 5 6 2 1 CPU 3 4 5 2 4 3 6 In Tina's Random Number Generator Library (TRNG) you find a some long period pseudo random number generators with special functions for parallel computations like sequence splitting (leap frog) and jumping. see http://tina.nat.uni-magdeburg.de/TRNG Do not hesitate to ask me, if you have questions about TRNG or parallel random number generators. Heiko -- -- Gegen Angriffe kann man sich wehren, gegen Lob ist man machtlos. -- (Sigmund Freud, österr. Psychologe u. Psychater, 1856-1939) -- Supercomputing in Magdeburg @ http://tina.nat.uni-magdeburg.de -- Heiko Bauke @ http://www.uni-magdeburg.de/bauke
G'day all. "Sliwa, Przemyslaw (London)" <Przemyslaw_Sliwa@ml.com> wrote:
I have a question which is not related directly to boost. I am writing a multithreaded application and would like to make use of a multiprocessor machine in order to speed up our Monte Carlo simulation engine. We make use of the random number package (random number distributions). My question is: making the random number generator a global variable (object) it is possible to use it in several threads at the same time -> does it mean that the random sequences will be repeated and the entire simulation will be simply a repetition of n non-random sequences? This can be avoided when a lock is acquired on the random number generator and at a given time just one thread can access the rng and the advantage of the multiprocessor machine is lost. Can you advise?
You might be able to ease the pain by requesting them from the RNG in blocks and caching them in a thread-local way. The attached code is untested, but it should give you a general idea. You create a concurrent_number_generator_adaptor for the RNG, then create a number_generator_cache for each thread. Cheers, Andrew Bromage --------8<---CUT HERE---8<-------- template<class Generator> class concurrent_number_generator_adaptor { public: // This class models NumberGenerator, in addition to a get_bulk // operation which gets a bunch of numbers. (This should probably // be modelled as a concept in its own right.) BOOST_CLASS_REQUIRE(Generator, boost, NumberGeneratorConcept); typedef Generator generator_type; typedef typename Generator::result_type result_type; result_type operator()() { Generator& gen = *gen_; mutex::scoped_lock lck(mut_); return gen(); } template<typename It> void get_bulk(int num, It out) { function_requires< OutputIteratorConcept<It> >(); Generator& gen = *gen_; mutex::scoped_lock lck(mut_); while (num-- > 0) { *out++ = gen(); } } concurrent_number_generator_adaptor(const shared_ptr<Generator> gen) : gen_(gen) { } private: mutex mut_; shared_ptr<Generator> gen_; }; template<class Generator, int N> class number_generator_cache { public: // This class models NumberGenerator BOOST_CLASS_REQUIRE(Generator, boost, NumberGeneratorConcept); // We also require the get_bulk() operation. typedef Generator generator_type; typedef typename Generator::result_type result_type; result_type operator()() { if (pos_ == cache_.end()) { gen_->get_bulk(N, cache_); pos_ = cache_.begin(); } return *pos_++; } number_generator_cache(const shared_ptr<Generator> gen) : gen_(gen), pos_(cache_.end()) { } private: typedef array<result_type,N> cache_type; shared_ptr<Generator> gen_; cache_type cache_; cache_type::iterator pos_; };
participants (4)
-
ajb＠spamcop.net -
Heiko Bauke -
Michael B. Edwin Rickert -
Sliwa, Przemyslaw (London)