Loading [MathJax]/jax/output/CommonHTML/jax.js

Introduction to MPI


Reductions - exercise 2

In the last exercise we have been computing a reduction on one process. In this one, we will use the MPI_Allreduce operator to compute a reduction on all processes and use the given result.

Consider the following problem. We have a list of N points in three dimensions (so with three coordinates). We want to compute the distance of each point to the barycentre of the set. For this, we will use M processes in parallel having NM points each. The algorithm will have to proceed in four steps :

  • Each process will compute the sum of all of its own points (sum avery coordinate
  • The program will then call the reduction to get the sum of all the points on all processes.
  • Then, the barycentre position is given by dividing this sum by the number of points
  • Finally, every process will compute the distance of each point to the barycentre, and print the result on stdout.


As stated in the lesson, MPI_Allreduce computes a reduction just like MPI_Reduce but instead of storing the result on only one process, the result will be sent back to every process. The prototype is the following :

int MPI_Allreduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm);

As you can see, the prototype is the same as for MPI_Reduce except we don't need to specify a root on which the result will be stored.

Euclidian distance

The distance that you are asked to compute is the Euclidian distance. For those of you who don't remember this distance, here is the formula :


Where (x,y,z) are the coordinates of the current point and (bx,by,bz) are the coordinates of the barycentre.

You have all you need to do the exercise. Good luck.

Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
void compute(int total_count, int my_count, float my_points[][3]) {
// total_count is the total number of points
// my_count is the number of points for this process
// my_points is a float table of shape [my_count][3]
// 1- Sum over all the points in local_sum
float local_sum[3] = {0.0f, 0.0f, 0.0f};
// 2- Reduce the sum of all the points on the variable barycentre
float barycentre[3];
// 3- Divide every component of the barycentre by the number of points
// For every point
for (int i=0; i < my_count; ++i) {
float dist = 0.0f;
// 4- Compute the distance for every point
// And printing the result
std::cout << rank << " " << dist << std::endl;
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
Online Participants