Reduction

Table of contents

1. Introduction
2. Connection to Modules
3. Files Required
4. Finding the Minimum Element Part 1: Implementing a reduction using Send and Recv
5. Finding the Minimum Element Part 2: Using Scatter and Reduce

---

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.

Figure 1: Example of sending the local minimum element at each rank to rank 0, where \(N=12\), and \(p=4\).

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.