3.2.1 Equal chunks for loops with 2 methods of random number streams¶

Now let’s explore the following parallel version using OpenMP.

#include <stdio.h>  // printf()
 #include <time.h>   // time()
 #include <string.h> // C++ string comparison

#include <omp.h>

// trng YARN (yet another random number) generator class
 #include <trng/yarn2.hpp>
 #include <trng/uniform_dist.hpp> // we'll use a uniform distribution
                                 // of the random numbers

#define LEAPFROG 0
 #define BLOCKSPLIT 1

////////////////////////////////////////////////////////////
 int main(int argc, char *argv[])
 {

// set up what conditions we will use:
   //  - defult size of repetitions in the loop
   //  - whether to use a constant seed so we can repeat and
   //    get same random values in stream

int repetitions = 8;
   int useConstantSeed = 0; // for same stream, set this to 1 on cammand line with -c

// rnage for uniform distribution of random numbers
   int min = 1;
   int max = 99;

// method the random generator will use to dole out the numbers
   int doleOut = LEAPFROG;

// for openMP
   int numThreads = 1;

// gather command line arguments
   getArguments(argc, argv, &numThreads, &repetitions,
               &useConstantSeed, &doleOut);

// openMP additions +++++++++++++++++++++++++++++++++++++++++++
   int tid = 0;
   omp_set_num_threads(numThreads);
   // Print out info
   printf("trng random number stream will be split ");
   if (doleOut == LEAPFROG)
   {
     printf("using leapfrog.\n");
   }
   else
   {
     printf("into blocks.\n");
   }
   printf("The loop is partitioned into equal chunks per thread.\n");
   printf("This means that the loop indices should be consecutive per thread.\n");
   printf("the output is printed like this:\n");
   printf("thread (loop index):randNumber\n");
   // openMP additions +++++++++++++++++++++++++++++++++++++++++++++

// ///////////////  random generator setup /////////////////////

// random numbers start from a seed value
   long unsigned int seedValue; // note for trng this is long unsigned

// same constant seed will generate the same sequence of rndom numbers
   // use for testing to varify same sequence regardless of number of threads
   if (useConstantSeed)
   {
     seedValue = 888777666;
   }
   else
   {                                            // variable seed based on computer clock time
     seedValue = (long unsigned int)time(NULL); // enables variation; use for simulations
   }

// For threaded openMP version, each thread will fork and have
   // a private copy of:
   //
   //  its thread id
   //
   // These are also automatically private because they are
   // declared inside the pragma block:
   //  -the generator and the distribution
   //  -the next value that will comback from the generator via the distribution
   //  -the loop counter
   //
   //  Since seedValue and repetitions are read but not written,
   //  they are shared.
   //
   // //////////////   begin fork here by using pragma for the compiler
   #pragma omp parallel default(none) private(tid) \
     shared(seedValue, repetitions, min, max, numThreads, doleOut)
   {
     // number generation needs two things: a generator and a distribution of the numbers
     // declare the generator object
     trng::yarn2 randGen;
     // declare the distribution to use (here it is uniform with vallues in the range min to max)
     trng::uniform_dist<> uniform(min, max);

// Set the starting point of the generator by seeding it
     randGen.seed(seedValue);

// OpenMP addition: get my thread number
     tid = omp_get_thread_num();

// Addition for openMP and parallel in general: the generator must be set to give
     // the thread its portion of the random numbers.
     // Note if single thread, this isn't necessary.
     if (numThreads > 1)
     {
       if (doleOut == LEAPFROG)
       {
         // thread will get substream tid from numThread separate substreams
         randGen.split((unsigned)numThreads, tid); // this is the leapfrog setup
       }
       else
       {
         // thread will get substream as a block:
         // thread 0 starts at 0, thread 1 starts at repetitions / numThreads, etc.
         randGen.jump(tid * (repetitions / numThreads)); // block split
       }
     }
     // //////////////// end PRNG setup /////////////////////////////////

// //////////////// get a portion of the stream /////////////////////
     int nextRandValue; // holds the next value as we go through the loop

// loop to get each number in the PRNG stream and print it
     // Note here the ubiquitous for loop construction of incrementing by 1-
     //   this leads itself nicely to letting the openMP compiler split the
     //   loop into equal chunks using the pragma shown.
     int i;

#pragma omp for
     for (i = 0; i < repetitions; i++)
     {
       // get next number in the stream from the distribution
       nextRandValue = uniform(randGen);
       // print tid(i):nextRandValue
       printf("t%2d (%2d):%2d \n", tid, i, nextRandValue);
     }

} // end of parallel block

return 0;
 }

As a reference, here is the set of numbers when using one thread with a given constant seed:

t 0( 0):83
t 0( 1):63
t 0( 2):97
t 0( 3):21
t 0( 4):62
t 0( 5):54
t 0( 6):14
t 0( 7):46

This is an OpenMP version with the following command line arguments:

-t indicates number of threads to use.
-n indicates the number of repetitions of the loop (default is 8).
-c indicates that a fixed seed will be used, resulting in the same
   stream of numbers each time this is run.
-d indicates whether the trng generator will dole out numbers in
   block or in leapfrog fashion. (default is leapfrog).

Study the code by reading the comments. Note in particular:

The pragma for the parallel block where the threads fork is separated from a pragma for the parallel for loop.
All threads are executing setup code for the generation of random numbers.
You must NOT indicate block splitting or leapfrog if you are only using one thread. This is assured by code beginning on line 109.

Note

This is an important new aspect of how we can and need to change this type of code by separating some lines of code that are done on each thread when they fork before the loop is decomposed onto each thread (requiring a second pragma).

This syntax is tricky for newcomers to OpenMP. The inner pramga is simply ‘#pragma omp for’ without the keyword parallel, which has already been placed in the previous pragma to indicate where the threads fork.

Try running the code above with these arguments (which are the original ones on this page if you reload it):

['-c', '-n 8', '-d block', '-t 1']

You should see that we are able to replicate the same set of numbers as the sequential version using this OpenMP version with one thread.

Now try changing the command line arguments in the above code block to use two threads, like this:

['-c', '-n 8', '-d block', '-t 2']

You should still get the same set of numbers. Now try using 4 threads, like this:

['-c', '-n 8', '-d block', '-t 4']

These examples have been using block splitting for the method of doling out portions of the stream of numbers to the threads. One important rule about using this particular method is that the set of numbers must be equally divisible by the number of threads that you use. To see how this method can fail, try this:

['-c', '-n 8', '-d block', '-t 3']

What do you observe?

Warning

You must be very careful when using this version of block splitting, because the code will run, but the results for this example are incorrect when the number of random numbers in the stream is not divisible by the number of threads. We will see how to fix this later.

Leapfrog to get random values per thread¶

Next try leapfrog by trying these command line arguments:

['-c', '-n 8', '-d leapfrog', '-t 1']
['-c', '-n 8', '-d leapfrog', '-t 2']

Notice a couple of things about using 2 threads with leapfrogging:

Thread 0 should get every other number starting from loop index 0: 83, 97, 62, 14
Thread 1 should get every other number starting from loop index 1: 63, 21, 54, 46
Since the OpenMP pragma and the for loop uses data decomposition of equal chunks of the loop per thread, then thread 0 gets loop indices 0, 1, 2, and 3, and thread 1 gets loop indices 4, 5, 6, and 7.
The order in which the threads complete is not guaranteed. Luckily, many applications do not rely on this (it’s random numbers, after all).

Now try different numbers of threads, like this:

['-c', '-n 8', '-d leapfrog', '-t 4']
['-c', '-n 8', '-d leapfrog', '-t 3']

Study the results of each to see that the leapfrogging is working as you would expect.

Notice that although the total number of numbers in the stream is not divisible by 3 threads, the set of numbers generated is the same.

Note

These last few examples show that leapfrogging can be a safer alternative when you may vary how many numbers you generate and how many threads you use. The issue with block splitting is due to the way it is implemented above on line 120. The number of repetitions must be equally divided by the number of threads, otherwise the value sent to the trng jump function is incorrect. HOWEVER, in later examples we will see how to fix this.

Command line code for reference¶

This code block below has code for handling the command line arguments for the parallel versions in this subsection. You can study it if you want to see how it was done.

void getArguments(int argc, char *argv[],
                 int * numThreads, int * N, int * useConstantSeed, int * doleOut);

int isNumber(char s[]);
 void exitWithError(char cmdFlag, char ** argv);
 void invalidChoice(char cmdFlag, char ** argv);
 void Usage(char *program);

#include <stdio.h>
 #include <unistd.h>
 #include <stdlib.h>
 #include <ctype.h>
 #include <string.h>  // C++ string comparison

#define LEAPFROG 0
 #define BLOCKSPLIT 1

void getArguments(int argc, char *argv[],
                   int * numThreads, int * N, int * useConstantSeed, int * doleOut)
 {

int c;        // result from getopt calls

// The : after a character means a value is expected
   // No colon means it is simply a flag with no associated value
   while ((c = getopt (argc, argv, "n:t:d:hc")) != -1) {

// getopt implicitly sets a value to a char * (string) called optarg
 // to what the user typed after -n
     switch (c)
       {
       // character string entered after the -N needs to be a number
       case 'n':
         if (isNumber(optarg)) {
           *N = atoi(optarg);
         } else {
           exitWithError(c, argv);
         }
         break;

// character string entered after the -t needs to be a number
       case 't':
         if (isNumber(optarg)) {
           *numThreads = atoi(optarg);
         } else {
           exitWithError(c, argv);
         }
         break;

case 'd':
         if (strcmp(optarg, "block") == 0) {
           *doleOut = BLOCKSPLIT;
         } else if (strcmp(optarg, "leapfrog") == 0) {
           *doleOut = LEAPFROG;
         } else {
           invalidChoice(c, argv);
         }
         break;
       // If the -h is encountered, then we provide usage
       case 'h':
         Usage(argv[0]);
         exit(0);
         break;

// If the -c is encountered, then we change the constant seed flag
       case 'c':
         *useConstantSeed = 1;
         break;

case ':':
         printf("Missing arg for %c\n", optopt);
         Usage(argv[0]);
         exit(EXIT_FAILURE);
         break;

case '?':
         if (
             (optopt == 'v') ||
             (optopt == 't')
           )
         {
           Usage(argv[0]);
           exit(EXIT_FAILURE);
         } else if (isprint (optopt)) {
           fprintf (stderr, "Unknown option `-%c'.\n", optopt);
           Usage(argv[0]);
           exit(EXIT_FAILURE);
         } else {
           fprintf (stderr,
                   "Unknown non-printable option character `\\x%x'.\n",
                   optopt);
           Usage(argv[0]);
           exit(EXIT_FAILURE);
         }
         break;

}
   }
 }

// Check a string as a number containing all digits
 int isNumber(char s[])
 {
     for (int i = 0; s[i]!= '\0'; i++)
     {
         if (isdigit(s[i]) == 0)
               return 0;
     }

return 1;
 }

// Called when isNumber() fails
 void exitWithError(char cmdFlag, char ** argv) {
   fprintf(stderr, "Option -%c needs a number value\n", cmdFlag);
   Usage(argv[0]);
   exit(EXIT_FAILURE);
 }

void invalidChoice(char cmdFlag, char ** argv) {
   fprintf(stderr, "unrecognized value for Option -%c needs 'block' or 'leapfrog'\n", cmdFlag);
   Usage(argv[0]);
   exit(EXIT_FAILURE);
 }

void Usage(char *program) {
   fprintf(stderr, "This program demonstrates use of a loop to create a stream of random numbers in parallel.\n");
   fprintf(stderr, "Usage: %s [-h] [-t numThreads] [-n numReps][-c] [-d block|leapfrog]\n", program);
   fprintf(stderr, "   -h shows this message and exits.\n");
   fprintf(stderr, "   -t indicates number of threads to use.\n");
   fprintf(stderr, "   -n indicates the number of repetitions of the loop (default is 8).\n");
   fprintf(stderr, "   -c indicates that a fixed seed will be used, resulting in the same stream of numbers each time this is run.\n");
   fprintf(stderr, "   -d indicates whether the trng generator will dole out numbers in blocks or in leapfrog fashion. default is leapfrog.\n");
 }

You have attempted of activities on this page