Reduction

Introduction

Performing a reduction using MPI_Reduce is useful in many contexts (e.g., finding the maximum value or adding the values together across several ranks).

The syntax is as follows:

int MPI_Reduce(const void *sendbuf, 
		void *recvbuf, 
		int count, 
		MPI_Datatype datatype,
		MPI_Op op, 
		int root, 
		MPI_Comm comm)

The operators are as follows:

    Name                Meaning
    ---------           --------------------
    MPI_MAX             maximum
    MPI_MIN             minimum
    MPI_SUM             sum
    MPI_PROD            product
    MPI_LAND            logical and
    MPI_BAND            bit-wise and
    MPI_LOR             logical or
    MPI_BOR             bit-wise or
    MPI_LXOR            logical xor
    MPI_BXOR            bit-wise xor
    MPI_MAXLOC          max value and location
    MPI_MINLOC          min value and location

Connection to Modules

• This module may be useful for the distance matrix module.

Files Required

• reduction_starter.c

Finding the Minimum Element Part 1: Implementing a reduction using Send and Recv

In this exercise, rank 0 will generate an array of size $N$. There are $p$ process ranks. We assume $N~\mathrm{mod}~p=0$, i.e., $N/p$ divides evenly.

We will compute the minimum value in an array of size $N$ using $p$ ranks. Using MPI_Send you will send chunks of size $N/p$ to each process rank from rank 0. Each rank will find the minimum element in its chunk of $N/p$ elements and will send the minimum element to rank 0 using MPI_Send. At the end, rank 0 will compute the minimum of the values received by the ranks and output the result.

In this exercise, we will only use MPI_Send and MPI_Recv.

To get started, use the file reduction_starter.c.

Figure 1 shows an example where the data has already been sent to each rank, and each rank computes the local minimum value of its array of size $N/p=3$. Each rank then sends its local minimum value to rank 0.

Finding the Minimum Element Part 2: Using Scatter and Reduce

Copy your code from Part 1. This time, implement the program using MPI_Scatter and MPI_Reduce without using MPI_Send or MPI_Recv.