Skip to content

MPI topologies

In many parallel applications, a linear ranking of processes does not adequately reflect the logical communication pattern of the processes. Often the processes are arranged in topological patterns such as two- or three-dimensional grids.

MPI offer som functions to create virtual topologies so that the way the ranks are organized matches more closely the actual topology of the problem we try to solve. Going over

Map processes on a Cartesian grid

The first step in creating a virtual topology is to assign a certain number of processes to each coordinate direction. For that, we can use MPI_Dims_create which is a convenience function in the creation of Cartesian topologies. It has the following signature:

int MPI_Dims_create(int nnodes, int ndims, int dims[])

where nnodes is the number of nodes (ranks) in the grid and ndims the number of Cartesian dimensions. dims is the array in which store the number of processes assigned to each dimension. The array passed must already contain values that will be used as potential restrictions:

  • dimensions that are initialized to 0 have no restriction and allow MPI to allocate any number of processes to it
  • if a non-zero value is provided, MPI must find a decomposition such that these dimensions contain exactly the number of processes indicated. However, certain decompositions may become impossible due to restrictions, in which case this routine will return an erroneous code.

For example, if we use the MPI_Dims_create function to a two-dimensional problem running with 6 rank:

int dims[2] = {0, 0};
int MPI_Dims_create(6, 2, dims);

then, after the call to the function, the value stored in dims[0] will be 3 the one stored in dims[1] will be 2. The values returned in dims should be balanced to minimize the difference in the number of processes assigned to each dimension.

Now that we have determined the number of processes in each dimension of our virtual Cartesian topology, we need to create it. This is done by calling the MPI_Cart_create which will create a new communicator for our topology. This function which has the following signature:

int MPI_Cart_create(MPI_Comm comm_old, int ndims, const int dims[],
                    const int periods[], int reorder, MPI_Comm * comm_cart)

where comm_old is a communicator containing the processes to use in the creation of the new communicator comm_cart. ndims is the number of Cartesian dimensions and dims an array with the number of processes in each dimension. The periods array indicates the periodicity in a particular dimension. A value of 0 means that the dimension is non-periodic while a value of 1 indicates that periodicity. Finally, the reorder parameter indicates if the processes must preserve their rank from the old communicator to the new one. If reorder is 1, MPI has the flexibility to decide what ranks assign to the processes in the new communicator.

Below is an example call to MPI_Cart_create for a two-dimensional problem with three processes in the first dimension and two processes in the second dimension. The first dimension is non-periodic while the second one is. We do not allow MPI to reorder the rank (reorder = 0).

int    dims[2] = {3, 2};
int periods[2] = {0, 1};

MPI_Comm cart_comm;

MPI_Cart_create(MPI_COMM_WORLD, 2, dims, periods, 0, &cart_comm);

Now that we have created a new communicator for our two-dimensional topology, we still need to determine the coordinates of the process for this Cartesian topology. The reason why we want to get this information is that, if we use MPI_Comm_rank, the rank is still organized in a linear fashion.

In order to get the two-dimensional coordinates of our rank, we can use the MPI_Cart_coords function which has the following signature:

int MPI_Cart_coords(MPI_Comm comm, int rank, int ndims, int coords[])

where comm is the communicator that has a Cartesian topology and rank, the rank for which we want to obtain the coordinates. ndims is the number of dimensions. coords is what we are interested in. It's an array in which the coordinates of the process in the Cartesian topology will be stored.

int cart_rank;
int coords[2];

MPI_Comm_rank(cart_comm, &cart_rank);
MPI_Cart_coords(cart_comm, cart_rank, 2, coords);

After the call, the coords array will contain the coordinates of our rank in the 2D Cartesian topology of cart_comm. Below is an illustration of the result of an MPI_Cart_coords call for an application running with 16 processes (4 processes in each Cartesian dimension).

MPI_Cart_create result MPI_Cart_create result

Rank coordinates when using a 2D Cartesian virtual topology with 4 processes in each dimension

Get the rank of the neighbors

In addition to the coordinates of a rank in a Cartesian topology, we might also be interested in determining the rank of the neighbors. This can easily be done using the MPI_Cart_shift convenience function which has the following signature:

int MPI_Cart_shift(MPI_Comm comm, int direction, int disp, 
                   int *rank_source, int *rank_dest)

where comm is the communicator for the topology we are interested in. The direction parameter indicates the dimension in which the shift will be made. The dimensions are numbered from 0 to NUM_DIMS-1, where NUM_DIMS is the number of dimensions. disp is the number of units by which we virtually move the topology.

  • rank_source will be the rank of process disp lower in the direction direction.
  • rank_dest will be the rank of process disp higher in the direction direction.

For example, depedending on the direction, the rank returned in rank_source can be the process on top, on the left of or at the front of the calling process. rank_dest will be the process down, on the right or at the back of the calling process.

If there is no neighbor, the value MPI_PROC_NULL may be returned in rank_source or rank_dest.

The illustration below shows the effect of the direction and disp parameters. For a code example, see the next section.

MPI_Cart_shift result MPI_Cart_shift result

Effect of the direction and disp parameters 2D Cartesian virtual topology

There is also, the possibility to get the rank of a process in a topology from its coordinates using the MPI_Cart_rank function:

int MPI_Cart_rank(MPI_Comm comm, const int coords[], int *rank)

where comm is the communicator and coords is an array with the coordinates of the process. rank will contain the rank of the process at the coordinates provided by coords.

Example

The example below summarize this chapter by creating a two-dimensional virtual topology and for each rank, determine the coordinates in the Cartesian topology as well as the ranks of the four neighbors (up, down, left and right).

Source code for this example

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

typedef enum neighbor {
  UP    = 0,
  DOWN  = 1,
  LEFT  = 2,
  RIGHT = 3

} neighbor_t;

int main(int argc, char **argv) {
  int world_size;
  int rank, cart_rank;

  int dims[2]    = {0, 0};
  int periods[2] = {0, 0};

  int reorder = 0;

  int coords[2];
  int neighbors[4];

  MPI_Comm cart_comm;

  MPI_Init(&argc,&argv);
  MPI_Comm_size(MPI_COMM_WORLD, &world_size);
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);

  MPI_Dims_create(world_size, 2, dims);

  MPI_Cart_create(MPI_COMM_WORLD, 2, dims, periods, reorder, &cart_comm);
  MPI_Comm_rank(cart_comm, &cart_rank);

  MPI_Cart_coords(cart_comm, cart_rank, 2, coords);

  MPI_Cart_shift(cart_comm, 0, 1, 
                  &neighbors[ UP], &neighbors[DOWN]);

  MPI_Cart_shift(cart_comm, 1, 1, 
                  &neighbors[LEFT], &neighbors[RIGHT]);

  printf("Rank = %4d - Coords = (%3d, %3d)"
         " - Neighbors (up, down, left, right) = (%3d, %3d, %3d, %3d)\n",
            rank, coords[0], coords[1], 
            neighbors[UP], neighbors[DOWN], neighbors[LEFT], neighbors[RIGHT]);

  MPI_Finalize();

  return 0;
}