8

When I try the following code

double start = omp_get_wtime();

long i;

#pragma omp parallel for
    for (i = 0; i <= 1000000000; i++) {
        double x = rand();
    }

    double end = omp_get_wtime();

    printf("%f\n", end - start);

Execution time is about 168 seconds, while the sequential version only spends 20 seconds.

I'm still a newbie in parallel programming. How could I get a parallel version that's faster that the sequential one?

Islam Hassan
  • 1,736
  • 4
  • 26
  • 42

1 Answers1

15

The random number generator rand(3) uses global state variables (hidden in the (g)libc implementation). Access to them from multiple threads leads to cache issues and also is not thread safe. You should use the rand_r(3) call with seed parameter private to the thread:

long i;
unsigned seed;

#pragma omp parallel private(seed)
{
    // Initialise the random number generator with different seed in each thread
    // The following constants are chosen arbitrarily... use something more sensible
    seed = 25234 + 17*omp_get_thread_num();
    #pragma omp for
    for (i = 0; i <= 1000000000; i++) {
       double x = rand_r(&seed);
    }
}

Note that this will produce different stream of random numbers when executed in parallel than when executed in serial. I would also recommend erand48(3) as a better (pseudo-)random number source.

Hristo Iliev
  • 72,659
  • 12
  • 135
  • 186
  • It should also be noted that since `double x = rand()` does not modify external state, the compiler might be tempted to optimize the loop out in the sequential version. In general, you should test with code that can't be optimized out. – Vanwaril May 16 '12 at 19:13
  • 2
    @Vanwaril, `rand()` is not an intrinsic. The compiler doesn't know if it is a pure function or not (it is _not_) and hence should not optimize the call out. – Hristo Iliev May 16 '12 at 19:20
  • Thanks very much. Now parallel version spends 5 seconds while sequential one spends 9 seconds. – Islam Hassan May 16 '12 at 19:27
  • @HristoIliev, the compiler might identify the state `rand()` modifies, and without external calls to `rand()`, its quite possible it can determine that it doesn't affect the output/outcome of the program. – Vanwaril May 16 '12 at 19:30
  • `rand()` is an external library function. Its declaration in `stdlib.h` no way says if it modifies an external state or not and besides its code is hidden in an already compiled library. GCC provides the `__atribute__ ((pure))` explicit annotation for pure external functions. Just try to compile the serial version with max optimisations enabled and see for yourself. – Hristo Iliev May 16 '12 at 19:36
  • Is it okay to use the loop iterator value to set the seed? The idea is to minimize the number of calculations. – Rajith Gun Hewage Jan 05 '16 at 12:54
  • @rajeerc, as long as it won't result in correlated pseudorandom sequences. It depends a lot on the properties of the PRNG. – Hristo Iliev Jan 05 '16 at 15:20