Distributed Sum on a 2D mesh using MPI

For a recent class project, we had to implement an algorithm to sum an array of integers on a computer cluster. This problem is one of the easiest applications of the map-reduce approach: Since a sum is an associative operation, we can simply assign a portion of the array to each of our processing resources, and incrementally collect and merge all the partial sums until we get the final result. The Message Passing Interface (MPI) actually has primitives that support map-reduce algorithms directly.

To make the project a little more challenging, we had to implement our distributed algorithm considering this additional requirements:

• We could only use MPI_Send and MPI_Recv primitives: in other words, all communication needed to be explicit, point-to-point messaging.
• We had to assume our computational resources were organized as a 2D mesh: each computation element would have an index (i, j) and could only communicate with elements on its same row or column.
• We wanted to minimize  the total distance traveled by messages (assuming each hop would have a cost): for instance, sending all partial sums in a row to the first element in the row is less efficient that summing neighbor nodes together iteratively (recursive halving)

We had to run the algorithm on a 16-node system and collect a few performance measures. An interesting (and expected) result is that depending on how many numbers we have to sum, distribution may or may not be convenient, due to message passing costs.

Read the full project report here!