[MPI] Solution 4 : Circular Shift

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

Task

Use non-blocking point-to-point communication operations to implement a parallel, circular array shift.

Here is the serial implementation of the algorithm:

const int  N = 100;
double     a[N];
double     t;
int        i;

t = a[N - 1];

for ( i = N - 1; i >= 1; i-- )
    a[i] = a[i - 1];

a[0] = t;

In the parallel implementation of the program each process stores a sub-section of the array a. The processes need to exchange data in order to process the first and last element in their sub-array.

Try to start the non-blocking receive operations as soon as possible.

The original array and the shifted array are printed by the program. Try to print the array elements in the correct order. That is, the processes should print their sub-section one after another.

Paste this command into your terminal:

The password to connect is

Question 1: Circular Shift

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

int main ( int argc, char** argv )
{
  const int    N    = 20;
  const int    tag1 = 1;
  const int    tag2 = 2;
  int          flag = 0;

  MPI_Request  req[2];
  double*      data;
  double       recv_buf, send_buf;
  int          my_rank, left_rank, right_rank;
  int          proc_count;
  int          i, k, n;

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

  if ( proc_count > N )
  {
    fprintf ( stderr, "Error: too many processes.\n" );
    return 1;
  }

  /* Determine the left and right neighbors of this process. */

  if ( my_rank == 0 )
  {
    left_rank = proc_count - 1;
  }
  else
  {
    left_rank = my_rank - 1;
  }

  right_rank = (my_rank + 1) % proc_count;

  /* Initialize the sub-array for this process. */

  n    = N / proc_count;
  data = (double*) malloc ( n * sizeof(*data) );
  k    = my_rank * n;

  for ( i = 0; i < n; i++ )
  {
    data[i] = k + i;
  }

  /* Start the non-blocking receive for the first (left-most)
   * array element from the left neighbor of this process. */

  MPI_Irecv ( &recv_buf, 1, MPI_DOUBLE, left_rank, tag1,
              MPI_COMM_WORLD, &req[0] );

  /* Print the initial array. */

  if ( my_rank == 0 )
  {
    printf ( "Initial array:\n\n" );
  }
  else
  {
    /* Wait until the previous process has printed its sub-array.
     * Note that a different tag is used to make sure the send
     * operation does not match the non-blocking receive operation
     * started above. */

    MPI_Recv ( &flag, 1, MPI_INT, left_rank, tag2,
               MPI_COMM_WORLD, MPI_STATUS_IGNORE );
  }

  for ( i = 0; i < n; i++ )
  {
    printf ( "a[%2d] = %g\n", i + k, data[i] );
  }

  if ( proc_count > 1 )
  {
    /* Signal that the next process may print is sub-array. Again,
     * note that a different tag is used. */

    MPI_Send ( &flag, 1, MPI_INT, right_rank, tag2, MPI_COMM_WORLD );

    if ( my_rank == 0 )
    {
      /* Wait until the last process has printed its sub-array. */

      MPI_Recv ( &flag, 1, MPI_INT, left_rank, tag2,
                 MPI_COMM_WORLD, MPI_STATUS_IGNORE );
    }
  }

  /* Start the non-blocking send operation for the last (righ-most) array
   * element. */

  send_buf = data[n - 1];

  MPI_Isend ( &send_buf, 1, MPI_DOUBLE, right_rank, tag1,
              MPI_COMM_WORLD, &req[1] );

  /* Shift the sub-array on this process. */

  for ( i = n - 1; i > 0; i-- )
  {
    data[i] = data[i - 1];
  }

  /* Wait for all non-blocking operations to complete. */

  MPI_Waitall ( 2, req, MPI_STATUSES_IGNORE );

  /* Set the first array element to the correct value. */

  data[0] = recv_buf;

  /* Print the final array. */

  if ( my_rank == 0 )
  {
    printf ( "\nFinal array:\n\n" );
  }
  else
  {
    /* Wait until the previous process has printed its sub-array. */

    MPI_Recv ( &flag, 1, MPI_INT, left_rank, tag2,
               MPI_COMM_WORLD, MPI_STATUS_IGNORE );
  }

  for ( i = 0; i < n; i++ )
  {
    printf ( "a[%2d] = %g\n", i + k, data[i] );
  }

  if ( my_rank < (proc_count - 1) )
  {
    /* Signal that the next process may print is sub-array. */

    MPI_Send ( &flag, 1, MPI_INT, right_rank, tag2, MPI_COMM_WORLD );
  }

  free ( data );

  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	Geen deadline
Submission limit	No limitation

Information

Sign in