Take the 2-minute tour ×
void NetClass::Modulate(vector <synapse> & synapses )
    int size = synapses.size();
    int split = 200 * 0.5;

    for(int w=0; w < size; w++)
            synapses[w].rmod = ((rand_r(seedp) % 200 - split ) / 1000.0);

The function rand_r(seedp) is seriously bottle-necking my program. Specifically, its slowing me by 3X when run serialy, and 4.4X when run on 16 cores. rand() is not an option because its even worse. Is there anything I can do to streamline this? If it will make a difference, I think I can sustain a loss in terms of statistical randomness. Would pre-generating (before execution) a list of random numbers and then loading to the thread stacks be an option?

share|improve this question
You'll need to tell us whether pre-generating all your random numbers is an option! –  Oliver Charlesworth Nov 27 '11 at 11:00
I wouldn't know, but did you check the boost random number generators? There is also hardware that generates random numbers, but that might not be faster. At any rate, since the core of the loop is just generating the random number, I would not really call it a 3x slow down... And at this point you will need to decide whether you want random numbers or not. –  David Rodríguez - dribeas Nov 27 '11 at 11:00
Also check out GSL (GNU scientific library) if GPL is OK for you. –  KennyTM Nov 27 '11 at 11:08
@David This loop is only a very small part of the overall computation in my program. And having random numbers is essential. –  Matt Munson Nov 27 '11 at 11:08
@OliC I guess I was more asking whether its likely to speed things up under any conditions. Have you ever heard of it being done before etc. –  Matt Munson Nov 27 '11 at 11:10

7 Answers 7

up vote 4 down vote accepted

Problem is that seedp variable (and its memory location) is shared among several threads. Processor cores must synchronize their caches each time they access this ever changing value, which hampers performance. The solution is that all threads work with their own seedp, and so avoid cache synchronization.

share|improve this answer
great A, prob you also need to mention that maybe possibly false sharing can also be a problem if somebody uses seedp[N_THREADS]... –  NoSenseEtAl Nov 15 '13 at 10:24
@NoSenseEtAl good comment. Small thread-specific variables (like seedp here) should live in thread's stack. Large structures should be separated in memory from structures of other threads. The code has to know about cache size to separate them properly. –  Dialecticus Nov 15 '13 at 10:45

It depends on how good the statistical randomness needs to be. For high quality, the Mersenne twister, or its SIMD variant, is a good choice. You can generate and buffer a large block of pseudo-random numbers at a time, and each thread can have its own state vector. The Park-Miller-Carta PRNG is extremely simple - these guys even implemented it as a CUDA kernel.

share|improve this answer
HAHA! Eureka! The Park-Miller-Carta algorithm works like a charm. Speeds up serial execution by 24% and 16 core execution by 10X, yielding benefits up to the ~14th core. I highly recommend for anyone with similar needs to give this a try. Very easy to implement. –  Matt Munson Nov 27 '11 at 14:27
How can Park-Miller-Carta be faster than rand_r? Is there any chance that seedp in your code is shared between all threads? In that case cores must synchronize their caches in order to be able to access the same memory location, and that takes time. Give each thread its own seedp and see what happens. –  Dialecticus Nov 28 '11 at 23:07
@Dialecticus I meant to post the following a long time ago. Yes, you are exactly right. The problem was that I did not have a seperate seedp for each thread. I changed that and the speed increased to at least as good as the PMC generator mentioned above (I can't actually remember the exact difference). Everyone please disregard my earlier comment; I would strongly recommend using rand_r over PMC. –  Matt Munson May 5 '12 at 0:27
@Dialecticus, I feel like your comment should be posted as an answer, and that answer accepted. –  Richard Dec 13 '12 at 14:32
Happy to oblige :) –  Dialecticus Dec 14 '12 at 0:09

Marsaglia's xor-shift generator is the probably fastest "reasonable quality" generator that you can use. It does not quite have the same "quality" as MT19937 or WELL, but honestly these differences are academic sophistries.
For all real, practical uses, there is no observable difference, except 1-2 orders of magnitude difference in execution speed, and 3 orders of magnitude of difference in memory consumption.

The xor-shift generator is also naturally thread-safe (in the sense that it will produce non-deterministic, pseudorandom results, and it will not crash) without anything special, and it can be trivially made thread-safe in another sense (in the sense that it will generate per-thread independent, deterministic, pseudorandom numbers) by having one instance per thread.
It could also be made threadsafe in yet another sense (generate a deterministic, pseudorandom sequence handed out to threads as they come) using atomic compare-exchange, but I don't think that's very useful.

The only three notable issues with the xor-shift generator are:

  • It is not k-distributed for up to 623 dimensions, but honestly who cares. I can't think in more than 4 dimensions (and even that's a lie!), and can't imagine many applications where more than 10 or 20 dimensions could possibly matter. That would have to be some quite esoteric simulation.
  • It passes most, but not ever pedantic statistic test. Again, who cares. Most people use a random generator that does not even pass a single test and never notice.
  • A zero seed will produce a zero sequence. This is trivially fixed by adding a non-zero constant to one of the temporaries (I wonder why Marsaglia never thought of that?). Having said that, MT19937 also behaves extremely badly given a zero seed, and does not recover nearly as well.
share|improve this answer
Really? You can't think of ever needing more than 10 or 20 dimensions? How many questions were on the last poll or survey you took? How many possibly physically important variables do you think go into a process needing simulation (fluid mechanics, driving, etc) –  McBeth Nov 29 '11 at 13:48
@McBeth: Fluid simulation is one of the very few applications where such things may really matter. Also note that I am not saying I can't think of ever needing more than 10 or 20 dimensions. I said I can't think of needing more than 10 or 20 dimensions which are randomized and need to have no pattern between the dimensions. Note that the OP's code contains a % 200, so much for patterns. If you really need 500 or 600 provably independently distributed dimensions in your simulation, fine, xor-shift is not what you want, use WELL. But I'm saying that most people don't really need this. –  Damon Nov 29 '11 at 13:56

Have a look at Boost: http://www.boost.org/doc/libs/1_47_0/doc/html/boost_random.html It has a number of options which vary in complexity (= speed) and randomness (cycle length).

If you don't need maximum randomness, you might get away with a simple Mersenne Twister.

share|improve this answer
To clarify: Neither of these is more random than the other. They both have zero randomness. –  Oliver Charlesworth Nov 27 '11 at 11:12
Randomness as used for simulations (uncorrelated with the actual process): yes. Randomness as required for cryptography: no. –  Anony-Mousse Nov 27 '11 at 11:13

do you absolutely need to have 1 shared random?

I had a similar contention problem a while ago, the solution that worked best for me was to create a new Random class (I was working in C#) for each thread. they're dead cheap anyway.

If you seed them properly to make sure you don't create duplicate seeds you should be fine. Then you won't have shared state so you don't need to use the threadsafe function.

Regards GJ

share|improve this answer
That is what rand_r does. –  Oliver Charlesworth Nov 27 '11 at 11:25
Ok thanks, updated answer. –  gjvdkamp Nov 27 '11 at 11:29
@gjvdkamp how do I create a random class and ensure that the randomization is indeed kept to seperate threads. I was under the impression that this could not be done with rand(). –  Matt Munson Nov 27 '11 at 11:48
I'm afraid I'm going to have to leave that to the c++ people in this thread, my c++ and library knowledge is very limited. If rand is just a function you'd need to replace that with a RNG that is implemented as a class, I'm sure there are plenty. –  gjvdkamp Nov 27 '11 at 12:05

maybe you don't have to call it in every iteration? you could initialize an array of pre-randomized elements and make successive use of it...

share|improve this answer

I think you can use OpenMP for paralleling like this:

#pragma omp parallel
share|improve this answer
I don't think you've understood what the OP's question is... –  Oliver Charlesworth Nov 27 '11 at 11:35

Your Answer


