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.

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 subroutines.

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 subroutine, with the following syntax:

call mpi_cart_create (icomm, ivshape, lperiod, lreorder, icartcom, ierr)

where:

Parameter	Description	Status
icomm	input communicator with 1D rank assignments	[IN]
ishape	array of grid sizes in each dimension	[IN]
lperiod	logical array specifying periodicity in each dimension (TRUE = periodic)	[IN]
lreorder	logical array specifying whether rank reordering is allowed (TRUE) or not (FALSE)	[IN]
icartcomm	new communicator for the Cartesian grid	[OUT]

The mpi_cart_rank subroutine retrieves the rank from a Cartesian communicator. The syntax is:

call mpi_cart_rank (icartcom, icoords, irank, ierr )

where:

Parameter	Description	Status
icartcom	Cartesian communicator	[IN]
icoords	array of Cartesian coordinates	[IN]
irank	rank	[IN]

The mpi_cart_get subroutine retrieves the Cartesian coordinate information from the Cartesian communicator. The syntax is:

call mpi_cart_get (icartcom, idim, ishape, lperiod, icoords, ierr)

where:

Parameter	Description	Status
icartcom	Cartesian communicator	[IN]
idim	dimension of Cartesian grid	[IN]
ishape	integer array of grid shape (grid sizes in each dimension)	[OUT]
lperiod	logical array returning periodicity in each dimension (TRUE = periodic)	[OUT]
icoords	array containing Cartesian coordinates of processes	[OUT]

The mapping from rank to Cartesian coordinates is performed with the mpi_cart_coords subroutine. The syntax is:

call mpi_cart_coords (icomm, irank, idim, icoords, ierr)

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 subroutine, 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 row 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:

An example of column shifting

A column 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:

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 subroutine 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 logical lvper arrays (see DATA statements at the beginning of the program). The first mpi_cart_shift subroutine call determines the source and destination for a +1 shift in the columns (dimension 1) and the second call determines the source and destination for a +1 shift in the rows (dimension 0). The results of a 9 processor calculation (NP=3) are tabulated at the end.

      program cart
C
C  Grid setup for Fox Matrix Multiply (3x3 Grid)
C  Create square 2-D Cartesian Grid of order NP
C  Find Source and Destination for row right-shift (of local matrix A)
C  Find Source and Destination for column up-shifts(of local matrix B)
C                                              [matrices not declared]
      parameter(NP=3)
C
C  Declare MPI status and buffer arrays.
C
      include 'mpif.h'
C
C  MPI Cartesian Grid information
C
      logical   lvper(2), lvperx(2)
      dimension ivdim(2), ivdimx(2), mygrid(2)
      data      ivdim /NP,NP/,   lvper /.true., .true./
C
C  MPI Parameters
C
      iwcomm=MPI_COMM_WORLD
C
C  MPI Get size & rank, attach buffer.
C
      call mpi_init(ierr)
      call mpi_comm_rank(iwcomm,mype,ierr)
      call mpi_comm_size(iwcomm,npes,ierr)
C
      call mpi_cart_create(iwcomm,2,ivdim ,lvper, .false.,igcomm,ierr)
      call mpi_cart_get(   igcomm,2,ivdimx,lvperx, mygrid,       ierr)
      call mpi_cart_shift(igcomm,1,1, isrca,idesa, ierr)
      call mpi_cart_shift(igcomm,0,1, isrcb,idesb, ierr)
C
      myrow=mygrid(1)
      mycol=mygrid(2)
      print*,'A: ',isrca,')- ',mype,'[',myrow,',',mycol,'] ->',idesa,
     & '      B: ',isrcb,')- ',mype,'[',myrow,',',mycol,'] ->',idesb
      call mpi_finalize(ierr)
      end

Results

A:				B:
src	mype	grid	dest	src	mype	grid	dest
0	1	[ 0 , 1 ]	-> 2	7	1	[ 0 , 1 ]	-> 4
1	2	[ 0 , 2 ]	-> 0	8	2	[ 0 , 0 ]	-> 5
2	0	[ 0 , 0 ]	-> 1	6	0	[ 0 , 0 ]	-> 3
3	4	[ 1 , 1 ]	-> 5	1	4	[ 1 , 1 ]	-> 7
4	5	[ 1 , 2 ]	-> 3	2	5	[ 1 , 2 ]	-> 8
5	5	[ 1 , 0 ]	-> 4	0	3	[ 1 , 0 ]	-> 6
6	7	[ 2 , 1 ]	-> 8	4	7	[ 2 , 1 ]	-> 1
7	8	[ 2 , 2 ]	-> 6	5	8	[ 2 , 2 ]	-> 2
8	6	[ 2 , 0 ]	-> 7	3	6	[ 2 , 0 ]	-> 0