Jump to content
  • Advertisement
Sign in to follow this  
ddengster

Multithreaded RNG access

This topic is 498 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I'm thinking of doing simple job-based multithreading for my particle emitter updates, think: foreach particle emitter determine emission, then update all particles connected to the emitter. My particles use the standard library's Random Number Generator. Is the usual way of handling this putting a critical section whenever you want a random number? Or do you single thread the emitter spawning particles, then predetermine the random numbers per particle at spawn time.

Share this post


Link to post
Share on other sites
Advertisement
I am not sure what the usual way of handling this is, but my first thought is that each thread should have its own RNG.

Share this post


Link to post
Share on other sites

Yes, there's no reason why each thread can't have its own generator in this sort of situation. Of course, "standard library's Random Number Generator" can mean several different things, so maybe it depends on that.

Share this post


Link to post
Share on other sites

Having a single random number generator provides some guarantees on the randomness[1], having several random number generators could introduce correlations between drawn numbers. (Due to the fact we normally use pseudo-random number generators rather than true (hardware) generators.)

This is probably mostly a theoretical issue, I doubt anyone would actually see such correlations if they happen. That said, why do you need mult-threaded random number access? You create particles only one time, right?

 

[1] Depending on the quality of the generator.

Share this post


Link to post
Share on other sites

Having a single random number generator provides some guarantees on the randomness[1], having several random number generators could introduce correlations between drawn numbers. (Due to the fact we normally use pseudo-random number generators rather than true (hardware) generators.)

This is probably mostly a theoretical issue, I doubt anyone would actually see such correlations if they happen. That said, why do you need mult-threaded random number access? You create particles only one time, right?

 

[1] Depending on the quality of the generator.

 

I need to emit a whole bunch of particles at once. I was thinking of emitting each of them as one job for the thread pool. Anyway, thanks all for your replies!

Share this post


Link to post
Share on other sites

Don't know how much calculation needs to be done for a particle, but it sounds very small for a job. Most efficient is do as little as possible task switching, so theoretically, having as many jobs as there are CPU cores is optimal. In practice, you may want to have a few more jobs.

Share this post


Link to post
Share on other sites

 

Having a single random number generator provides some guarantees on the randomness[1], having several random number generators could introduce correlations between drawn numbers. (Due to the fact we normally use pseudo-random number generators rather than true (hardware) generators.)

This is probably mostly a theoretical issue, I doubt anyone would actually see such correlations if they happen. That said, why do you need mult-threaded random number access? You create particles only one time, right?

 

[1] Depending on the quality of the generator.

 

I need to emit a whole bunch of particles at once. I was thinking of emitting each of them as one job for the thread pool. Anyway, thanks all for your replies!

 

 

Even if you synchronize your PRNG function somehow (via a job queue or by means of a mutex), race conditions will almost invariably cause different evocations to match up with different values, which will sooner or later destroy any reproducibility. 

In this case perhaps - if complete reproducibility is truly desirable - it would make sense to generate a lookup table of random values (for instance a million values, logically divided into bins depending on how many are needed per particle) and loop an atomic counter through it (possibly with an offset after each full loop to maximize the number of possible permutations). This way you will be able to exactly reproduce any behavior even in a multithreaded environment so long as you keep an individual counter locked to a single object (eg one for particles, another for behavior and yet another for something else), which does not in itself accept parallel tasks of different types (eg generating particles for effect A are guaranteed to finish before effect B is processed, even if particles are generated asynchronously on multiple threads).

Note that the objective here is not to increase performance (even though that might possibly be a side effect), but to make a potentially heavily contested operation more robust and less burdensome on the CPU due to a requirement for synchronization.

Share this post


Link to post
Share on other sites

Having a single random number generator provides some guarantees on the randomness[1], having several random number generators could introduce correlations between drawn numbers. (Due to the fact we normally use pseudo-random number generators rather than true (hardware) generators.)
This is probably mostly a theoretical issue, I doubt anyone would actually see such correlations if they happen. That said, why do you need mult-threaded random number access? You create particles only one time, right?
 
[1] Depending on the quality of the generator.

 
I need to emit a whole bunch of particles at once. I was thinking of emitting each of them as one job for the thread pool. Anyway, thanks all for your replies!

 
Even if you synchronize your PRNG function somehow (via a job queue or by means of a mutex), race conditions will almost invariably cause different evocations to match up with different values, which will sooner or later destroy any reproducibility. 
In this case perhaps - if complete reproducibility is truly desirable - it would make sense to generate a lookup table of random values (for instance a million values, logically divided into bins depending on how many are needed per particle) and loop an atomic counter through it (possibly with an offset after each full loop to maximize the number of possible permutations). This way you will be able to exactly reproduce any behavior even in a multithreaded environment so long as you keep an individual counter locked to a single object (eg one for particles, another for behavior and yet another for something else), which does not in itself accept parallel tasks of different types (eg generating particles for effect A are guaranteed to finish before effect B is processed, even if particles are generated asynchronously on multiple threads).
Note that the objective here is not to increase performance (even though that might possibly be a side effect), but to make a potentially heavily contested operation more robust and less burdensome on the CPU due to a requirement for synchronization.


No offense, but that idea of using a table is pretty bad. If you want reproducibility, use a hash function instead of a PRNG. You can feed the hash function something like the index of the particle being created (I imagine each thread gets assigned a range of indices, or something like that). A good hash function should produce high-quality pseudo-random numbers when fed consecutive integers.

Share this post


Link to post
Share on other sites

If you're talking about STL's <random> then the generators are not thread safe as they contain internal state. std::random_device may be an exception, but you shouldn't be using that except for doing science and generating random seeds.

Share this post


Link to post
Share on other sites

 

 

 

Having a single random number generator provides some guarantees on the randomness[1], having several random number generators could introduce correlations between drawn numbers. (Due to the fact we normally use pseudo-random number generators rather than true (hardware) generators.)
This is probably mostly a theoretical issue, I doubt anyone would actually see such correlations if they happen. That said, why do you need mult-threaded random number access? You create particles only one time, right?
 
[1] Depending on the quality of the generator.

 
I need to emit a whole bunch of particles at once. I was thinking of emitting each of them as one job for the thread pool. Anyway, thanks all for your replies!

 

 
Even if you synchronize your PRNG function somehow (via a job queue or by means of a mutex), race conditions will almost invariably cause different evocations to match up with different values, which will sooner or later destroy any reproducibility. 
In this case perhaps - if complete reproducibility is truly desirable - it would make sense to generate a lookup table of random values (for instance a million values, logically divided into bins depending on how many are needed per particle) and loop an atomic counter through it (possibly with an offset after each full loop to maximize the number of possible permutations). This way you will be able to exactly reproduce any behavior even in a multithreaded environment so long as you keep an individual counter locked to a single object (eg one for particles, another for behavior and yet another for something else), which does not in itself accept parallel tasks of different types (eg generating particles for effect A are guaranteed to finish before effect B is processed, even if particles are generated asynchronously on multiple threads).
Note that the objective here is not to increase performance (even though that might possibly be a side effect), but to make a potentially heavily contested operation more robust and less burdensome on the CPU due to a requirement for synchronization.

 


No offense, but that idea of using a table is pretty bad. If you want reproducibility, use a hash function instead of a PRNG. You can feed the hash function something like the index of the particle being created (I imagine each thread gets assigned a range of indices, or something like that). A good hash function should produce high-quality pseudo-random numbers when fed consecutive integers.

 

 

Thanks for the correction - I was apparently overthinking it :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!