[MPI] Solution 6 : Random Number Generator

This material is part of the course Practical Introduction to Parallel Programming and meant for educational purposes only.

Task

Implement a parallel program that generates a stream of uniform random numbers within the range \([0,1]\) within each process.

The program should stop if it has found ten numbers that are smaller than \(\epsilon = 1 \cdot 10^{-7}\).

When the program has found ten numbers (or more), the master process (with rank zero) should collect all found numbers and print them to the terminal.

The code below implements a sequential version of the program.

Hints

Use the provided function next_random to generate the stream of random numbers. This function will set a different random seed for each process. Without this, no speedup is possible. Why not?

Use collective MPI functions to determine when the program should stop and to collect the results on the master.

Measure the parallel speedup of your program. What can you do to improve the performance?

Paste this command into your terminal:

The password to connect is

Question 1: Random Number Generator

#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>


/* ---------------------------------------------------------------------
 * next_random()
 *
 * Returns a uniform random number in the range [0,1].
 * ------------------------------------------------------------------ */


double                    next_random

  ( void )

{
  static int  initialized = 0;
  int         next;

  if ( ! initialized )
  {
    int  my_rank;
    int  flag;

    MPI_Initialized ( &flag );

    if ( flag )
    {
      MPI_Comm_rank ( MPI_COMM_WORLD, &my_rank );

      srand ( (unsigned int) my_rank );
    }

    initialized = 1;
  }

  next = rand ();

  return ((double) next / (double) RAND_MAX);
}


/* ---------------------------------------------------------------------
 * main()
 * ------------------------------------------------------------------ */


int                       main

  ( int                     argc,
    char**                  argv )

{
  const double  eps      = 1.0e-7;
  const int     N        = 10;
  const int     root     = 0;
  int           k        = 0;
  double*       recv_buf = NULL;

  double        numbers[N];
  double        start;
  int           proc_count;
  int           recv_count;
  int           my_rank;
  int           iiter;
  int           inext;
  int           i;


  MPI_Init      ( &argc, &argv );
  MPI_Comm_size ( MPI_COMM_WORLD, &proc_count );
  MPI_Comm_rank ( MPI_COMM_WORLD, &my_rank );

  if ( my_rank == 0 )
  {
    printf ( "Generating random numbers ...\n" );
  }

  for ( i = 0; i < N; i++ )
  {
    numbers[i] = -1.0;
  }

  start = MPI_Wtime ();
  inext = N;

  for ( iiter = 0; 1; iiter++ )
  {
    double  v = next_random ();

    if ( (v < eps) && (k < N) )
    {
      numbers[k++] = v;
    }

    /* Do not check each iteration to limit the communication
     * overhead. */

    if ( iiter > inext )
    {
      MPI_Allreduce ( &k, &recv_count, 1,
                      MPI_INT, MPI_SUM, MPI_COMM_WORLD );

      if ( recv_count >= N )
      {
        break;
      }

      inext = iiter + (iiter / 5);
    }
  }

  /* Collect all numbers found on the master process. */

  if ( my_rank == 0 )
  {
    recv_buf = (double*) malloc ( N * proc_count * sizeof(*recv_buf) );
  }

  MPI_Gather ( numbers, N, MPI_DOUBLE, recv_buf, N, MPI_DOUBLE,
               root, MPI_COMM_WORLD );

  if ( my_rank == 0 )
  {
    printf ( "Ready in %d iterations (%g seconds).\n",
             iiter, (MPI_Wtime() - start) );
    printf ( "Numbers found:\n\n" );

    for ( i = 0; i < (N * proc_count); i++ )
    {
      double  v = recv_buf[i];

      if ( v >= 0.0 )
      {
        printf ( "  %g\n", v );
      }
    }

    printf ( "\n" );
    free   ( recv_buf );
  }

  MPI_Finalize ();

  return 0;
}

Question 2: Number of MPI processes

Specify the number of MPI processes (1-64) that should be used for running your program (mpirun -np <nproc>)

Question 3: Command Line Argument

Specify the command line arguments that should be passed to your program when it is run. Arguments must be given in quotes and separated by commas. Leave this filed empty if you do not want to specify command line arguments.

Example: "1","int","arg=2" is interpreted as three arguments 1, int, and arg=2.

Author(s)	Erik-Jan Lingen, Matthias Möller
Deadline	No deadline
Submission limit	No limitation

Information

Sign in