Click here to go to the TACC Home Page
Topologies

In a communicator group, each of the n processes is assigned a rank between 0 and n-1. This one-dimensional mapping can be awkward when the parallelism in the problem is described more appropriately by an N-dimensional hypercube. For example, a vector might be divided into N parts and assigned to each process for manipulation (a 1-D operation). However, a 6400x6400 matrix which is mapped onto a grid of 8x8 processes, each process containing 800x800 data blocks, is more aptly described by a two-dimensional grid of numbers if the communication patterns are only between rows or columns of an 8x8 process grid. In this latter case, it is reasonable to use the virtual topology mapping routines of MPI.

   Message-Passing Interface

A virtual topology is a mapping between the process ranks and a set of N-tuples. For example, a matrix grid map which assigns processes with ranks 0, 1, 2, and 3 to the 2-tuples

{ (0,0), (0,1), (1,0), (1,1) }

is a common type of topology which labels the processes for X-Y communication patterns. It is probably optimal for you to customize your own arrangement of processes for non-standard communication patterns but it is convenient to use the MPI library for common grid topologies.

Note: the virtual topology does not necessarily map the hardware processor grid to the process grid in the most efficient manner.

For example, if a program is assigned an 8x8 hardware configuration having elements ([[alpha]], [[beta]]), and MPI assigns an 8x8 virtual topology with elements (i, j), there is no guarantee that assignments coincide, that is, that topology (1, 1) is assigned to processor (1, 1) and so forth.

The BLACS (Basic Linear Algebra Communication Subroutines), PBLAS (Parallel Basic Linear Algebra Subroutines) and ScaLAPACK also use grid topologies in which data is often distributed in a block-cyclic pattern. If you are interested in incorporating these packages into your programs, you should investigate the character of block-cyclic data distributions before using the MPI topology functions.

In the following section, only the Cartesian topology constructor and its convenience functions will be discussed. The more general graph constructor goes beyond the N-dimensional rectilinear mapping of the Cartesian topology and will not be covered here.

Cartesian Topology

An N-dimensional Cartesian map is generated by the MPI_Cart_create function, with the following syntax: 

ierr= MPI_Cart_create(icomm, ndims, ivshape, iperiod, ireorder, icartcom)

where:

Parameter Description Status
icomm (MPI_Comm) input communicator with 1D rank assignments [IN]
ndims (int) number of dimensions of Cartesian grid [IN]
ishape (int *) array of grid sizes in each dimension [IN]
iperiod (int *) integer array specifying periodicity in each dimension (true = periodic) [IN]
reorder (int) integer specifying whether rank reordering is allowed (true) or not (false) [IN]
icartcomm (MPI_Comm *) new communicator for the Cartesian grid [OUT]
ierr (int) error [OUT]

The MPI_Cart_rank function retrieves the rank from a Cartesian communicator. The syntax is: 

ierr= MPI_Cart_rank(icartcom, icoords, irank)

where:

Parameter Description Status
icartcom (MPI_Comm) Cartesian communicator [IN]
icoords (int *) array of Cartesian coordinates [IN]
irank (int) rank [IN]
ierr (int) error [OUT]
ierr (int) error [OUT]

The MPI_Cart_get function retrieves the Cartesian coordinate information from the Cartesian communicator. The syntax is: 

ierr= MPI_Cart_get(icartcom, idim, ishape, iperiod, icoords)

where:

Parameter Description Status
icartcom (MPI_Comm) Cartesian communicator [IN]
idim (int) dimension of Cartesian grid [IN]
ishape (int *) integer array of grid shape (grid sizes in each dimension) [OUT]
iperiod (int *) integer array returning periodicity in each dimension (true = periodic) [OUT]
icoords (int *) integer array containing Cartesian coordinates of processes [OUT]
ierr (int) error [OUT]

The mapping from rank to Cartesian coordinates is performed with the MPI_Cart_coords function. The syntax is: 

ierr= MPI_Cart_coords(icomm, irank, idim, icoords)

where:

Parameter Description Status
icomm communicator for irank [IN]
idim dimension of Cartesian grid [IN]
icoords array of Cartesian coordinates for irank [OUT]

The Cartesian shift function, MPI_Cart_shift, determines the source rank and destination rank for shifting data to neighbors removed by a known number of steps (hops). For instance, in a 3x3 Cartesian grid with the grid and rank assignments as shown to the right, a column shift to an adjacent processor (i.e., displacement of 1 in dimension "0") is illustrated in the following diagram. A(i,j) is a local matrix labeled by the initial processor grid, and periodic (wrap around) shifting is assumed:

     Cartesian mapping diagram

Column shifting diagram
An example of column shifting

A row shift to adjacent processes (displacement of 1, in dimension "1") is illustrated below. Matrix B(i,j) is a local matrix labelled by the initial process grid, and periodic (wrap around) shifting is assumed:

Row shifting diagram
An example of row shifting

A displacement of 1 in the rows (with periodic shifting) will send information from 0 to 3; 3 to 6; 6 to 0; 1 to 4; 4 to 7; 7 to 1; 2 to 5; 5 to 8, and 8 to 2. If n is a process rank, then

mod(n+3, 9) is the destination (send to rank) and
mod(n+6,9) is the source (receive from rank)

for the send and receive calls of a process. A displacement of 2 will send a message to neighbors once removed, that is, with destination=mod(n+3*idisp, 9) and source=mod(n(9-3*idisp), 9).

The example program below illustrates how to set up a 3x3 processor grid, determine the source and destination ranks for a row shift (as in the B matrix example above), and find the source and destination ranks for a column shift (as in the A matrix example above). After the program, the source and destination ranks on each process of the grid are printed for the row and column shifts.

Explanation: NP is the order of the (square) 2-D process grid. The MPI_Cart_create function generates a new (grid) communicator containing the grid information. Both the shape of the grid, as well as the periodic/nonperiodic numbering information are supplied in the integer ivdim and ivper arrays (see DATA statements at the beginning of the program). The first MPI_Cart_shift function call determines the source and destination for a +1 shift (right) in the columns (dimension 1) and the second call determines the source and destination for a +1 shift (up) in the rows (dimension 0). The results of a 9 processor calculation (NP=3) are tabulated at the end. 

#include <mpi.h>
#include <stdio.h>
#define NP 3

main(int argc, char **argv){
/*
   Grid setup for Fox Matrix Multiply (3x3 Grid)
   Create square 2-D Cartesian Grid of order NP
   Find Source and Destination for row right-shift (of local matrix A)
   Find Source and Destination for column up-shifts(of local matrix B)
                                               [matrices not declared]
*/
   int npes, mype, ierr, myrow, mycol;
   int isrca, isrcb, idesa, idesb;
   MPI_Comm IWCOMM = MPI_COMM_WORLD, igcomm;
/*                               MPI Cartesian Grid information */
   int  ivdim[2] = {NP,NP}, ivper[2]={1,1};
   int ivdimx[2],          ivperx[2], mygrid[2];

   ierr = MPI_Init(&argc, &argv);
   ierr = MPI_Comm_size(IWCOMM, &npes);
   ierr = MPI_Comm_rank(IWCOMM, &mype);

/*  Create Cartesian Grid and extract information */

      ierr= MPI_Cart_create(IWCOMM,2,ivdim ,ivper, 0,&igcomm);
      ierr= MPI_Cart_get(   igcomm,2,ivdimx,ivperx, mygrid);
      ierr= MPI_Cart_shift( igcomm,1,1, &isrca,&idesa);
      ierr= MPI_Cart_shift( igcomm,0,1, &isrcb,&idesb);
 
      myrow=mygrid[0];
      mycol=mygrid[1];
      printf("A (%d) [%d,%d]: %2d ->%2d\n",mype,myrow,mycol,isrca,idesa);
      printf("B (%d) [%d,%d]: %2d ->%2d\n",mype,myrow,mycol,isrcb,idesb);
      ierr= MPI_Finalize();
}

Results
A:B:
srcmypegriddest srcmypegriddest
01[ 0 , 1 ]-> 2 71[ 0 , 1 ]-> 4
12[ 0 , 2 ]-> 0 82[ 0 , 0 ]-> 5
20[ 0 , 0 ]-> 1 60[ 0 , 0 ]-> 3
34[ 1 , 1 ]-> 5 14[ 1 , 1 ]-> 7
45[ 1 , 2 ]-> 3 25[ 1 , 2 ]-> 8
53[ 1 , 0 ]-> 4 03[ 1 , 0 ]-> 6
67[ 2 , 1 ]-> 8 47[ 2 , 1 ]-> 1
78[ 2 , 2 ]-> 6 58[ 2 , 2 ]-> 2
86[ 2 , 0 ]-> 7 36[ 2 , 0 ]-> 0

July 20, 2008
Office of the Vice President for Research
© Copyright 2002 The University of Texas at Austin