Virtual Topologies

Cartesian and graph topologies

Cartesian virtual topologies, suitable for grid-like (with or without cyclic boundaries), in which each process is "connected" to its neighbors in a virtual grid.
MPI also allows for general graph virtual topologies, in which a process may be "connected" to any number of other processes and the numbering is arbitrary. These are similar to cartesian's but no concept of coordinates.

Creating a cartesian virtual topology

MPI_Cart_create (comm_old, process_dimensions, divisions, periods, reorder, cartesian_communicator)

MPI_Cart_create takes and existing communicator comm_old and returns a new communicator cartesian_communicator with the virtual topology associated with it.
The cartesian grid can be of any dimension and may be periodic or not in any dimension, so torus, 3D grids, rings, are all supported.
The process_dimensions argument contains the number of dimensions.
The number of processes in each dimension is specified in the array divisions and periods is an array of TRUE (or 1) or FALSE (or 0) specifying whether that dimension has cyclic boundaries or not.
The reorder argument is an interesting one. It takes one of two values:
- FALSE: if your data is already distributed to the processes. In this case the process ranks remain exactly as in old_comm and what you gain is access to the rank-coordinate mapping functions.
- TRUE: if your data is not yet distributed. In this case it is open to MPI to renumber the process ranks. MPI may choose to match the virtual topology to a physical topology to optimize communication. The new communicator can then be used to scatter the data.
MPI_Cart_create creates a new communicator and like all communicator-creating routines, it may or may not synchronize the processes involved.
The routine MPI_Topo_test can be used to test if a virtual topology is already associated with a communicator.

Cartesian mapping functions

MPI_Cart_rank routine converts process grid coordinates to process rank. This might be used to determine the rank of a particular process whose grid coordinates are known, in order to send a message to it or receive a message from it. If the process lies in the same row or column as the calling process then MPI_Cart_shift might be more appropriate.
If the coordinates are off the grid, the value will be MPI_NULL_PROC for non-periodic dimensions, and will automatically be wrapped correctly for periodic.

MPI_Cart_rank (comm, coords, rank)
The inverse function MPI_Cart_coords routine converts process rank to process grid coordinates. It might be used to determine the grid coordinates of a particular process from which a message has just been received.

MPI_Cart_coords (comm, rank, maxdims, coords)
The maxdims argument is needed to specify the length of the array coords, usually is process_dimensions.
MPI_Cart_shift (comm, direction, disp, rank_source, rank_dest)
This routine does not actually perform a "shift" (more on this later). What it does do is return the correct ranks for a shift which can then be included directly as arguments to MPI_Send, MPI_Recv, MPI_Sendrecv, etc. to perform the actual shift.
- The user specifies the dimension in which the shift should be made in the direction argument (a value between 0 and process_dimensions - 1).
- The displacement disp is the number of process coordinates in that direction in which to shift (a positive or negative number).
- The routine returns 2 results:
  - rank_source is where the calling process should receive a message from during the shift,
  - rank_dest is the process to send a message to.
- The value will be MPI_NULL_PROC if the respective coordinates are off the grid.
- Unfortunately, there is no provision for a diagonal "shift", although MPI_Cart_rank can be used instead.
The following virtual topology shows MPI_cart_shift called on process 20 with direction = 0 and disp = 2.

The following topology shows an MPI_Cart_shift also called on process 20 but direction = 1 and disp = -1. Note the effect of the periodic boundary condition.

Shifts and MPI_Sendrecv

A shift involves a set of processes passing data to each other in a chain-like fashion (or a circular fashion). Each process sends a maximum of one message and receives a maximum of one message.
Here is an example of two shifts. MPI_Sendrecv could be used for both.
MPI_Sendrecv provides a convenient way of expressing this communication pattern in one routine call without causing any deadlock.
Note that MPI_Sendrecv is just an extension of point-to-point communication. It is completely compatible with point-to-point communication in the sense that messages sent with MPI_sendrecv can be received by a usual point-to-point receive and vice versa.
In fact, all MPI_Sendrecv does is to combine a send and receive into a single MPI call and make them happen simultaneously to avoid deadlock.
It has nothing to do with collective communication and need not involve all processes in the communicator.
As one might expect, the arguments to MPI_Sendrecv are basically the union of the arguments to a send and receive call:

MPI_Sendrecv(sendbuff, sendcount, sendtype, dest, sendtag, recvbuff, recvcount, recvtype, source, recvtag, comm, status)
In the above figure, process 1 only receives, process 6 only sends and process 3 does neither.
A nice trick is to use MPI_NULL_PROC which makes the code more symmetric. The communication in the above figure could work with MPI_Sendrecv: