3.3.1 Unequal blocks of RNs to match unequal chunks in loops¶

The method of splitting the stream of random numbers into blocks that are used by each thread is quite useful, but as we saw with our previous examples, it can behave unexpectedly if the needed numbers in the stream are not evenly divided by the number of threads or processes we use. Luckily, we can get around this fairly easily by deciding for ourselves what starting position in the stream each thread should use.

Let’s consider this example stream of numbers:

Now suppose that we would like to use the block splitting method with three threads. We had a problem with the technique that we used before because the blocks would not be of equal size. However, we can get around this and be able to get this assignment of the numbers to three threads:

../_images/Stream-8-RNs-block-3threads.png

We do this by using the following helper function, getChunkStartStopValues, to decide where the start and stop indices of a block should be, given the thread id, the total number of threads, and the number of values in the stream.

#include <math.h>   // ceil()

/* Calculate the start and stop values for this PE's
 *  contiguous chunk of a range of values, 0..N-1,
 *  so that each process chunk-sizes are equal (or nearly so).
 *
 * @param: id, an int
 * @param: P, an int
 * @param: N, a const unsigned
 * Precondition: id == this process's MPI rank or thread ID.
 *            && P == the number of PEs (threads or MPI processes)
 *            && N == the total number of 0-based loop iterations needed
 *            && P <= N
 *            && N < 2^32
 * @param: start, the address of the unsigned variable through which the
 *          starting value of this process's chunk should be returned
 * @param: stop, the address of the unsigned variable through which the
 *          stopping value of this process's chunk should be returned
 * Postcondition: *start = this process's first iteration value
 *             && *stop = this process's last iteration value + 1.
 */
 void getChunkStartStopValues(int id, int P, const unsigned N,
                             unsigned* start, unsigned* stop) {

// compute the chunk size that works in many cases
 unsigned chunkSize1 = (long)ceil(((double)N) / P);
 unsigned begin = id * chunkSize1;
 unsigned end = begin + chunkSize1;

// see if there are any leftover iterations
 int remainder = N % P;

// If remainder == 0, chunkSize1 = chunk-size for all processes;
 // If remainder != 0, chunkSize1 = chunk-size for p_0..p_remainder-1
 //   but for processes p_remainder..p_numProcs-1
 //   recompute begin and end using a smaller-by-1 chunk size, chunkSize2.
 if (remainder > 0 && id >= remainder) {
     unsigned chunkSize2 = chunkSize1 - 1;
     unsigned remainderBase = remainder * chunkSize1;
     unsigned processOffset = (id-remainder) * chunkSize2;
     begin = remainderBase + processOffset;
     end = begin + chunkSize2;
 }

// pass back this PE's begin and end values via start and stop
 *start = begin;
 *stop = end;
 }

With this function we can now provide a correct starting index in the stream to the trng generator’s jump function used for splitting the stream into blocks, like this:

unsigned start, stop;
getChunkStartStopValues(tid, numThreads, (const unsigned)repetitions,
                        &start, &stop);

randGen.jump(start); // block split slightly unevenly

In this code snippet above, the number of repetitions of the loop is the number of random numbers we need to generate.

The complete example for looping and creating random numbers is given below. It is the same as the previous “equal chunks” example, except for this above change in how we use the jump function. In the previous example, we simply did the following, which assumes the repetitions is divisible by the number of threads:

randGen.jump(tid * (repetitions / numThreads)); // block split

By calculating a different starting index in the stream of random numbers per each thread, we can accurately use the blocking assignment of those numbers per thread.

For the following example, we also still use the same 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).

TO DO:

Try executing the code as is with one thread, to observe the 8 integer numbers in the stream.
Then change to 3 threads. What do you observe?
Find the change to the code near line 129 that illustrates this improvement.

#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 command 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);

//check ifvalid number of threads vs repetitions
     if (numThreads > repetitions) {
         printf("\n*** Number of threads (%u) exceeds repetitions (%u)\n", numThreads, repetitions);
         printf("*** Please run with -t value less than or equal to %u\n\n", repetitions);

return 0;
     }

// 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 possibly slightly unequal 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:
                 // Each thread gets a slightly different number of random numbers from
                 // the stream depending on whether repetitions divides evenly by numThreads
                 unsigned start, stop;
                 getChunkStartStopValues(tid, numThreads, (const unsigned)repetitions,
                                     &start, &stop);
                 printf("tid, jump val: %d %d\n", tid, start); // uncomment to check jump value
                 randGen.jump(start); // block split slightly unevenly
             }
         }
         // //////////////// 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);
             printf("t%2d (%2d):%2d \n", tid, i, nextRandValue);
         }

} // end of parallel block

return 0;
 }

Scroll to the bottom of this code example near line 146 and notice the simplest way of using the OpenMP for pragma inside this parallel block in front of a loop written just the way we normally would for a sequential version. By adding the function to determine where each block of random numbers in the stream should start, we can use the block splitting method of obtaining numbers from the stream.

To illustrate this further, suppose you try increasing the number of repetitions to 10 by changing the -n value above. Then use 4 threads. You should see that the assignment of loop indexes and indexes into the stream of numbers should look like this:

../_images/Stream-10-RNs-block-4threads.png

Note

So we now have the capability of matching the slightly unequal decomposition of the parallel for loop by OpenMP to the decomposition of the blocks using the block splitting technique. In the next section, we will see a use of this to place the random numbers into an array. Following that, we will see an even more important use of this: 2-dimensional grid structures with nested loops.

Command line code for reference¶

This code block below has code for handling the command line arguments for the parallel versions in this subsection and the previous one. It hasn’t changed.

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