D R A F T

Document for a Standard Message-Passing Interface

Message Passing Interface Forum

May 30, 1995

This work was supported in part by ARPA and NSF under grant ASC-9310330, the

National Science Foundation Science and Technology Center Cooperative Agreement No. CCR-8809615, and by the Commission of the European Community

through Esprit project P6643.

This is the result of a LaTeX run of a draft of a single chapter of the MPIF Final Report document.

Chapter 1

Process Topologies

1.1 Introduction

This chapter discusses the MPI topology mechanism. A topology is an extra, optional attribute that one can give to an intra-communicator; topologies cannot be added to intercommunicators. A topology can provide a convenient naming mechanism for the processes of a group (within a communicator), and additionally, may assist the runtime system in mapping the processes onto hardware.

As stated in chapter ??, a process group in MPI is a collection of n processes. Each process in the group is assigned a rank between 0 and n-1. In many parallel applications a linear ranking of processes does not adequately reflect the logical communication pattern of the processes (which is usually determined by the underlying problem geometry and the numerical algorithm used). Often the processes are arranged in topological patterns such as two- or three-dimensional grids. More generally, the logical process arrangement is described by a graph. In this chapter we will refer to this logical process arrangement as the “virtual topology.”

A clear distinction must be made between the virtual process topology and the topology of the underlying, physical hardware. The virtual topology can be exploited by the system in the assignment of processes to physical processors, if this helps to improve the communication performance on a given machine. How this mapping is done, however, is outside the scope of MPI. The description of the virtual topology, on the other hand, depends only on the application, and is machine-independent. The functions that are proposed in this chapter deal only with machine-independent mapping.

Rationale. Though physical mapping is not discussed, the existence of the virtual topology information may be used as advice by the runtime system. There are wellknown techniques for mapping grid/torus structures to hardware topologies such as hypercubes or grids. For more complicated graph structures good heuristics often yield nearly optimal results [5]. On the other hand, if there is no way for the user to specify the logical process arrangement as a “virtual topology,” a random mapping is most likely to result. On some machines, this will lead to unnecessary contention in the interconnection network. Some details about predicted and measured performance improvements that result from good process-to-processor mapping on modern wormhole-routing architectures can be found in [4, 3]. Besides possible performance benefits, the virtual topology can function as a convenient, process-naming structure, with tremendous benefits for program readability

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

and notational power in message-passing programming. (End of rationale.)

1.2 Virtual Topologies

The communication pattern of a set of processes can be represented by a graph. The nodes stand for the processes, and the edges connect processes that communicate with each other. MPI provides message-passing between any pair of processes in a group. There is no requirement for opening a channel explicitly. Therefore, a “missing link” in the user-defined process graph does not prevent the corresponding processes from exchanging messages. It means rather that this connection is neglected in the virtual topology. This strategy implies that the topology gives no convenient way of naming this pathway of communication. Another possible consequence is that an automatic mapping tool (if one exists for the runtime environment) will not take account of this edge when mapping. Edges in the communication graph are not weighted, so that processes are either simply connected or not connected at all.

Rationale. Experience with similar techniques in PARMACS [1, 2] show that this information is usually sufficient for a good mapping. Additionally, a more precise specification is more difficult for the user to set up, and it would make the interface functions substantially more complicated. (End of rationale.)

Specifying the virtual topology in terms of a graph is sufficient for all applications. However, in many applications the graph structure is regular, and the detailed set-up of the graph would be inconvenient for the user and might be less efficient at run time. A large fraction of all parallel applications use process topologies like rings, two- or higher-dimensional grids, or tori. These structures are completely defined by the number of dimensions and the numbers of processes in each coordinate direction. Also, the mapping of grids and tori is generally an easier problem then that of general graphs. Thus, it is desirable to address these cases explicitly.

Process coordinates in a cartesian structure begin their numbering at 0. Row-major numbering is always used for the processes in a cartesian structure. This means that, for example, the relation between group rank and coordinates for four processes in a (2 × 2) grid is as follows.

coord (0,0): rank 0
coord (0,1): rank 1
coord (1,0): rank 2
coord (1,1): rank 3

1.3 Embedding in MPI

The support for virtual topologies as defined in this chapter is consistent with other parts of MPI, and, whenever possible, makes use of functions that are defined elsewhere. Topology information is associated with communicators. It is added to communicators using the caching mechanism described in Chapter ??.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

1.4 Overview of the Functions

The functions MPI GRAPH CREATE and MPI CART CREATE are used to create general (graph) virtual topologies and cartesian topologies, respectively. These topology creation functions are collective. As with other collective calls, the program must be written to work correctly, whether the call synchronizes or not.

The topology creation functions take as input an existing communicator comm old, which defines the set of processes on which the topology is to be mapped. A new communicator comm topol is created that carries the topological structure as cached information (see Chapter ??). In analogy to function MPI COMM CREATE, no cached information propagates from comm old to comm topol.

MPI CART CREATE can be used to describe cartesian structures of arbitrary dimension. For each coordinate direction one specifies whether the process structure is periodic or not. Note that an n-dimensional hypercube is an n-dimensional torus with 2 processes per coordinate direction. Thus, special support for hypercube structures is not necessary. The local auxiliary function MPI DIMS CREATE can be used to compute a balanced distribution of processes among a given number of dimensions.

Rationale. Similar functions are contained in EXPRESS [6] and PARMACS. (End of rationale.)

The function MPI TOPO TEST can be used to inquire about the topology associated with a communicator. The topological information can be extracted from the communicator using the functions MPI GRAPHDIMS GET and MPI GRAPH GET, for general graphs, and MPI CARTDIM GET and MPI CART GET, for cartesian topologies. Several additional functions are provided to manipulate cartesian topologies: the functions MPI CART RANK and MPI CART COORDS translate cartesian coordinates into a group rank, and vice-versa; the function MPI CART SUB can be used to extract a cartesian subspace (analogous to MPI COMM SPLIT). The function MPI CART SHIFT provides the information needed to communicate with neighbors in a cartesian dimension. The two functions MPI GRAPH NEIGHBORS COUNT and MPI GRAPH NEIGHBORS can be used to extract the neighbors of a node in a graph. The function MPI CART SUB is collective over the input communicator’s group; all other functions are local.

Two additional functions, MPI GRAPH MAP and MPI CART MAP are presented in the last section. In general these functions are not called by the user directly. However, together with the communicator manipulation functions presented in Chapter ??, they are sufficient to implement all other topology functions. Section 1.5.7 outlines such an implementation.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

1.5 Topology Constructors

1.5.1 Cartesian Constructor

MPI CART CREATE(comm old, ndims, dims, periods, reorder, comm cart)

IN  comm old  input communicator (handle)
IN  ndims  number of dimensions of cartesian grid (integer)
IN  dims  integer array of size ndims specifying the number of

processes in each dimension

IN  periods  logical array of size ndims specifying whether the grid

is periodic (true) or not (false) in each dimension

IN  reorder  ranking may be reordered (true) or not (false) (logical)
OUT  comm cart  communicator with new cartesian topology (handle)

int MPI Cart create(MPI Comm comm old, int ndims, int *dims, int *periods,
             int reorder, MPI Comm *comm cart)
MPI CART CREATE(COMM OLD, NDIMS, DIMS, PERIODS, REORDER, COMM CART, IERROR)
    INTEGER COMM OLD, NDIMS, DIMS(*), COMM CART, IERROR
    LOGICAL PERIODS(*), REORDER

MPI CART CREATE returns a handle to a new communicator to which the cartesian topology information is attached. If reorder = false then the rank of each process in the new group is identical to its rank in the old group. Otherwise, the function may reorder the processes (possibly so as to choose a good embedding of the virtual topology onto the physical machine). If the total size of the cartesian grid is smaller than the size of the group of comm, then some processes are returned MPI COMM NULL, in analogy to MPI COMM SPLIT. The call is erroneous if it specifies a grid that is larger than the group size.

1.5.2 Cartesian Convenience Function: MPI DIMS CREATE

For cartesian topologies, the function MPI DIMS CREATE helps the user select a balanced distribution of processes per coordinate direction, depending on the number of processes in the group to be balanced and optional constraints that can be specified by the user. One use is to partition all the processes (the size of MPI COMM WORLD’s group) into an n-dimensional topology.

MPI DIMS CREATE(nnodes, ndims, dims)

IN  nnodes  number of nodes in a grid (integer)
IN  ndims  number of cartesian dimensions (integer)

INOUT dims integer array of size ndims specifying the number of nodes in each dimension

int MPI Dims create(int nnodes, int ndims, int *dims)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

MPI DIMS CREATE(NNODES, NDIMS, DIMS, IERROR)
    INTEGER NNODES, NDIMS, DIMS(*), IERROR

The entries in the array dims are set to describe a cartesian grid with ndims dimensions and a total of nnodes nodes. The dimensions are set to be as close to each other as possible, using an appropriate divisibility algorithm. The caller may further constrain the operation of this routine by specifying elements of array dims. If dims[i] is set to a positive number, the routine will not modify the number of nodes in dimension i; only those entries where dims[i] = 0 are modified by the call.

Negative input values of dims[i] are erroneous. An error will occur if nnodes is not a

multiple of ∏_{i,dims[i]≠0} dims[i].

For dims[i] set by the call, dims[i] will be ordered in non-increasing order. Array dims is suitable for use as input to routine MPI CART CREATE. MPI DIMS CREATE is local.

Example 1.1

dims  function call  dims
before call  on return
(0,0)  MPI DIMS CREATE(6, 2, dims) (3,2)
(0,0)  MPI DIMS CREATE(7, 2, dims) (7,1)
(0,3,0)  MPI DIMS CREATE(6, 3, dims) (2,3,1)
(0,3,0)  MPI DIMS CREATE(7, 3, dims) erroneous call

1.5.3 General (Graph) Constructor

MPI GRAPH CREATE(comm old, nnodes, index, edges, reorder, comm graph) ⊤

IN  comm old  input communicator topology (handle)  ⊥
IN  nnodes  number of nodes in graph (integer)
IN  index  array of integers describing node degrees (see below)
IN  edges  array of integers describing graph edges (see below)
IN  reorder  ranking may be reordered (true) or not (false) (logical)
OUT  comm graph  communicator with graph topology added (handle)

int MPI Graph create(MPI Comm comm old, int nnodes, int *index, int *edges,
             int reorder, MPI Comm *comm graph)
MPI GRAPH CREATE(COMM OLD, NNODES, INDEX, EDGES, REORDER, COMM GRAPH,
             IERROR)
    INTEGER COMM OLD, NNODES, INDEX(*), EDGES(*), COMM GRAPH, IERROR
    LOGICAL REORDER

MPI GRAPH CREATE returns a handle to a new communicator to which the graph topology information is attached. If reorder = false then the rank of each process in the new group is identical to its rank in the old group. Otherwise, the function may reorder the

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

processes. If the size, nnodes, of the graph is smaller than the size of the group of comm, then some processes are returned MPI COMM NULL, in analogy to MPI CART CREATE and MPI COMM SPLIT. The call is erroneous if it specifies a graph that is larger than the group size of the input communicator.

The three parameters nnodes, index and edges define the graph structure. nnodes is the number of nodes of the graph. The nodes are numbered from 0 to nnodes-1. The ith entry of array index stores the total number of neighbors of the first i graph nodes. The lists of neighbors of nodes 0, 1, …, nnodes-1 are stored in consecutive locations in array edges. The array edges is a flattened representation of the edge lists. The total number of entries in index is nnodes and the total number of entries in edges is equal to the number of graph edges.

The definitions of the arguments nnodes, index, and edges are illustrated with the following simple example.

Example 1.2 Assume there are four processes 0, 1, 2, 3 with the following adjacency matrix:

process neighbors
0  1, 3
1  0
2  3
3  0, 2

Then, the input arguments are:

nnodes = 4
index = 2, 3, 4, 6
edges = 1, 3, 0, 3, 0, 2

Thus, in C, index[0] is the degree of node zero, and index[i] - index[i-1] is the degree of node i, i=1, …, nnodes-1; the list of neighbors of node zero is stored in edges[j], for 0 ≤ j ≤ index[0] − 1 and the list of neighbors of node i, i > 0, is stored in

edges[j], index[i − 1] ≤ j ≤ index[i] − 1.

In Fortran, index(1) is the degree of node zero, and index(i+1) - index(i) is the degree of node i, i=1, …, nnodes-1; the list of neighbors of node zero is stored in edges(j), for 1 ≤ j ≤ index(1) and the list of neighbors of node i, i > 0, is stored in

edges(j), index(i) + 1 ≤ j ≤ index(i + 1).

Advice to implementors. The following topology information is likely to be stored with a communicator:

• Type of topology (cartesian/graph),

• For a cartesian topology:

1. ndims (number of dimensions),

2. dims (numbers of processes per coordinate direction),

3. periods (periodicity information),

4. own_position (own position in grid, could also be computed from rank and

dims)

• For a graph topology:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

          1. index,
          2. edges,

which are the vectors defining the graph structure.

For a graph structure the number of nodes is equal to the number of processes in the group. Therefore, the number of nodes does not have to be stored explicitly. An additional zero entry at the start of array index simplifies access to the topology information. (End of advice to implementors.)

1.5.4 Topology inquiry functions

If a topology has been defined with one of the above functions, then the topology information can be looked up using inquiry functions. They all are local calls.

MPI TOPO TEST(comm, status)

IN  comm  communicator (handle)
OUT  status  topology type of communicator comm (choice)

int MPI Topo test(MPI Comm comm, int *status)
MPI TOPO TEST(COMM, STATUS, IERROR)
    INTEGER COMM, STATUS, IERROR

The function MPI TOPO TEST returns the type of topology that is assigned to a communicator.

The output value status is one of the following:

MPI GRAPH graph topology

MPI CART cartesian topology

MPI UNDEFINED no topology

MPI GRAPHDIMS GET(comm, nnodes, nedges)

IN  comm  communicator for group with graph structure (handle)
OUT  nnodes  number of nodes in graph (integer) (same as number

of processes in the group)

OUT  nedges  number of edges in graph (integer)

int MPI Graphdims get(MPI Comm comm, int *nnodes, int *nedges)
MPI GRAPHDIMS GET(COMM, NNODES, NEDGES, IERROR)
    INTEGER COMM, NNODES, NEDGES, IERROR

Functions MPI GRAPHDIMS GET and MPI GRAPH GET retrieve the graph-topology information that was associated with a communicator by MPI GRAPH CREATE.

The information provided by MPI GRAPHDIMS GET can be used to dimension the vectors index and edges correctly for the following call to MPI GRAPH GET.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

8 CHAPTER 1. PROCESS TOPOLOGIES

MPI GRAPH GET(comm, maxindex, maxedges, index, edges)

IN  comm  communicator with graph structure (handle)
IN  maxindex  length of vector index in the calling program

(integer)

IN  maxedges  length of vector edges in the calling program

(integer)

OUT  index  array of integers containing the graph structure (for

details see the definition of MPI GRAPH CREATE)

OUT  edges  array of integers containing the graph structure

int MPI Graph get(MPI Comm comm, int maxindex, int maxedges, int *index,
            int *edges)
MPI GRAPH GET(COMM, MAXINDEX, MAXEDGES, INDEX, EDGES, IERROR)
  INTEGER COMM, MAXINDEX, MAXEDGES, INDEX(*), EDGES(*), IERROR

MPI CARTDIM GET(comm, ndims)

IN  comm  communicator with cartesian structure (handle)
OUT  ndims  number of dimensions of the cartesian structure (inte-

ger)

int MPI Cartdim get(MPI Comm comm, int *ndims)
MPI CARTDIM GET(COMM, NDIMS, IERROR)
  INTEGER COMM, NDIMS, IERROR

The functions MPI CARTDIM GET and MPI CART GET return the cartesian topology information that was associated with a communicator by MPI CART CREATE.

MPI CART GET(comm, maxdims, dims, periods, coords)

IN  comm  communicator with cartesian structure (handle)
IN  maxdims  length of vectors dims, periods, and coords in the

calling program (integer)

OUT  dims  number of processes for each cartesian dimension (ar-

ray of integer)

OUT  periods  periodicity (true/false) for each cartesian dimension

(array of logical)

OUT  coords  coordinates of calling process in cartesian structure

(array of integer)

int MPI Cart get(MPI Comm comm, int maxdims, int *dims, int *periods,
            int *coords)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

MPI CART GET(COMM, MAXDIMS, DIMS, PERIODS, COORDS, IERROR)
    INTEGER COMM, MAXDIMS, DIMS(*), COORDS(*), IERROR
    LOGICAL PERIODS(*)

MPI CART RANK(comm, coords, rank)

IN  comm  communicator with cartesian structure (handle)
IN  coords  integer array (of size ndims) specifying the cartesian

coordinates of a process

OUT  rank  rank of specified process (integer)

int MPI Cart rank(MPI Comm comm, int *coords, int *rank)
MPI CART RANK(COMM, COORDS, RANK, IERROR)
    INTEGER COMM, COORDS(*), RANK, IERROR

For a process group with cartesian structure, the function MPI CART RANK translates the logical process coordinates to process ranks as they are used by the point-to-point routines.

For dimension i with periods(i) = true, if the coordinate, coords(i), is out of range, that is, coords(i) < 0 or coords(i) ≥ dims(i), it is shifted back to the interval 0 ≤ coords(i) < dims(i) automatically. Out-of-range coordinates are erroneous for non-periodic dimensions.

MPI CART COORDS(comm, rank, maxdims, coords)

IN  comm  communicator with cartesian structure (handle)
IN  rank  rank of a process within group of comm (integer)
IN  maxdims  length of vector coord in the calling program (integer)
OUT  coords  integer array (of size ndims) containing the cartesian

coordinates of specified process (integer)

int MPI Cart coords(MPI Comm comm, int rank, int maxdims, int *coords)
MPI CART COORDS(COMM, RANK, MAXDIMS, COORDS, IERROR)
    INTEGER COMM, RANK, MAXDIMS, COORDS(*), IERROR

The inverse mapping, rank-to-coordinates translation is provided by MPI CART-COORDS.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

MPI GRAPH NEIGHBORS COUNT(comm, rank, nneighbors)

IN  comm  communicator with graph topology (handle)
IN  rank  rank of process in group of comm (integer)
OUT  nneighbors  number of neighbors of specified process (integer)

int MPI Graph neighbors count(MPI Comm comm, int rank, int *nneighbors)
MPI GRAPH NEIGHBORS COUNT(COMM, RANK, NNEIGHBORS, IERROR)
    INTEGER COMM, RANK, NNEIGHBORS, IERROR

MPI GRAPH NEIGHBORS COUNT and MPI GRAPH NEIGHBORS provide adjacency information for a general, graph topology.

MPI GRAPH NEIGHBORS(comm, rank, maxneighbors, neighbors)

IN  comm  communicator with graph topology (handle)
IN  rank  rank of process in group of comm (integer)
IN  maxneighbors  size of array neighbors (integer)
OUT  neighbors  ranks of processes that are neighbors to specified pro-

cess (array of integer)

int MPI Graph neighbors(MPI Comm comm, int rank, int maxneighbors,
             int *neighbors)
MPI GRAPH NEIGHBORS(COMM, RANK, MAXNEIGHBORS, NEIGHBORS, IERROR)
    INTEGER COMM, RANK, MAXNEIGHBORS, NEIGHBORS(*), IERROR

Example 1.3 Suppose that comm is a communicator with a shuffle-exchange topology. The group has 2^{n} members. Each process is labeled by a_{1}, …, a_{n} with a_{i} ∈ {0, 1}, and has three neighbors: exchange(a_{1}, …, a_{n}) = a_{1}, …, a_{n−1}, ā_{n} (ā = 1 − a), shuffle(a_{1}, …, a_{n}) = a_{2}, …, a_{n}, a_{1}, and unshuffle(a_{1}, …, a_{n}) = a_{n}, a_{1}, …, a_{n−1}. The graph adjacency list is illustrated below for n = 3.

node  exchange  shuffle  unshuffle
neighbors(1) neighbors(2) neighbors(3)
0 (000)  1  0  0
1 (001)  0  2  4
2 (010)  3  4  1
3 (011)  2  6  5
4 (100)  5  1  2
5 (101)  4  3  6
6 (110)  7  5  3
7 (111)  6  7  7

Suppose that the communicator comm has this topology associated with it. The following code fragment cycles through the three types of neighbors and performs an appropriate permutation for each.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

C  assume: each process has stored a real number A.
C  extract neighborhood information
      CALL MPI_COMM_RANK(comm, myrank, ierr)
      CALL MPI_GRAPH_NEIGHBORS(comm, myrank, 3, neighbors, ierr)
C  perform exchange permutation
      CALL MPI_SENDRECV_REPLACE(A, 1, MPI_REAL, neighbors(1), 0,
     +     neighbors(1), 0, comm, status, ierr)
C  perform shuffle permutation
      CALL MPI_SENDRECV_REPLACE(A, 1, MPI_REAL, neighbors(2), 0,
     +     neighbors(3), 0, comm, status, ierr)
C  perform unshuffle permutation
      CALL MPI_SENDRECV_REPLACE(A, 1, MPI_REAL, neighbors(3), 0,
     +     neighbors(2), 0, comm, status, ierr)

1.5.5 Cartesian Shift Coordinates

If the process topology is a cartesian structure, a MPI SENDRECV operation is likely to be used along a coordinate direction to perform a shift of data. As input, MPI SENDRECV takes the rank of a source process for the receive, and the rank of a destination process for the send. If the function MPI CART SHIFT is called for a cartesian process group, it provides the calling process with the above identifiers, which then can be passed to MPI SENDRECV. The user specifies the coordinate direction and the size of the step (positive or negative). The function is local.

MPI CART SHIFT(comm, direction, disp, rank source, rank dest)

IN  comm  communicator with cartesian structure (handle)
IN  direction  coordinate dimension of shift (integer)
IN  disp  displacement (> 0: upwards shift, < 0: downwards

shift) (integer)

OUT  rank source  rank of source process (integer)
OUT  rank dest  rank of destination process (integer)

int MPI Cart shift(MPI Comm comm, int direction, int disp, int *rank source,
             int *rank dest)
MPI CART SHIFT(COMM, DIRECTION, DISP, RANK SOURCE, RANK DEST, IERROR)
    INTEGER COMM, DIRECTION, DISP, RANK SOURCE, RANK DEST, IERROR

⊤

The direction argument indicates the dimension of the shift, i.e., the coordinate which value is modified by the shift. The coordinates are numbered from 0 to ndims-1, when ndims is the number of dimensions. ⊥

Depending on the periodicity of the cartesian group in the specified coordinate direction, MPI CART SHIFT provides the identifiers for a circular or an end-off shift. In the case of an end-off shift, the value MPI PROC NULL may be returned in rank source or rank dest, indicating that the source or the destination for the shift is out of range.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

Example 1.4 The communicator, comm, has a two-dimensional, periodic, cartesian topology associated with it. A two-dimensional array of REALs is stored one element per process, in variable A. One wishes to skew this array, by shifting column i (vertically, i.e., along the column) by i steps.

....
C find process rank
      CALL MPI_COMM_RANK(comm, rank, ierr))
C find cartesian coordinates
      CALL MPI_CART_COORDS(comm, rank, maxdims, coords, ierr)
C compute shift source and destination
      CALL MPI_CART_SHIFT(comm, 0, coords(2), source, dest, ierr)
C skew array
      CALL MPI_SENDRECV_REPLACE(A, 1, MPI_REAL, dest, 0, source, 0, comm,
     +                          status, ierr)

⊤

Advice to users. In Fortran, the dimension indicated by DIRECTION = i has DIMS(i+1) nodes, where DIMS is the array that was used to create the grid. In C, the dimension indicated by direction = i is the dimension specified by dims[i]. (End of advice to users.)

⊥

1.5.6 Partitioning of Cartesian structures

MPI CART SUB(comm, remain dims, newcomm)

IN  comm  communicator with cartesian structure (handle)
IN  remain dims  the ith entry of remain dims specifies whether the

ith dimension is kept in the subgrid (true) or is dropped (false) (logical vector)

OUT  newcomm  communicator containing the subgrid that includes

the calling process (handle)

int MPI Cart sub(MPI Comm comm, int *remain dims, MPI Comm *newcomm)
MPI CART SUB(COMM, REMAIN DIMS, NEWCOMM, IERROR)
    INTEGER COMM, NEWCOMM, IERROR
    LOGICAL REMAIN DIMS(*)

If a cartesian topology has been created with MPI CART CREATE, the function MPI CART SUB can be used to partition the communicator group into subgroups that form lower-dimensional cartesian subgrids, and to build for each subgroup a communicator with the associated subgrid cartesian topology. (This function is closely related to MPI COMM SPLIT.)

Example 1.5 Assume that MPI CART CREATE(..., comm) has defined a (2×3×4) grid.

Let remain dims = (true, false, true). Then a call to,
     MPI_CART_SUB(comm, remain_dims, comm_new),

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

will create three communicators each with eight processes in a 2 × 4 cartesian topology. If remain dims = (false, false, true) then the call to MPI CART SUB(comm, remain dims, comm new) will create six non-overlapping communicators, each with four processes, in a one-dimensional cartesian topology.

1.5.7 Low-level topology functions

The two additional functions introduced in this section can be used to implement all other topology functions. In general they will not be called by the user directly, unless he or she is creating additional virtual topology capability other than that provided by MPI.

MPI CART MAP(comm, ndims, dims, periods, newrank)

IN  comm  input communicator (handle)
IN  ndims  number of dimensions of cartesian structure (integer)
IN  dims  integer array of size ndims specifying the number of

processes in each coordinate direction

IN  periods  logical array of size ndims specifying the periodicity

specification in each coordinate direction

OUT  newrank  reordered rank of the calling process; MPI UNDEFINED

if calling process does not belong to grid (integer)

int MPI Cart map(MPI Comm comm, int ndims, int *dims, int *periods,
             int *newrank)
MPI CART MAP(COMM, NDIMS, DIMS, PERIODS, NEWRANK, IERROR)
    INTEGER COMM, NDIMS, DIMS(*), NEWRANK, IERROR
    LOGICAL PERIODS(*)

MPI CART MAP computes an “optimal” placement for the calling process on the physical machine. A possible implementation of this function is to always return the rank of the calling process, that is, not to perform any reordering.

Advice to implementors. The function MPI CART CREATE(comm, ndims, dims, periods, reorder, comm cart), with reorder = true can be implemented by calling MPI CART MAP(comm, ndims, dims, periods, newrank), then calling MPI COMM SPLIT(comm, color, key, comm cart), with color = 0 if newrank ≠

     MPI UNDEFINED, color = MPI UNDEFINED otherwise, and key = newrank.

The function MPI CART SUB(comm, remain dims, comm new) can be implemented by a call to MPI COMM SPLIT(comm, color, key, comm new), using a single number encoding of the lost dimensions as color and a single number encoding of the preserved dimensions as key.

All other cartesian topology functions can be implemented locally, using the topology information that is cached with the communicator. (End of advice to implementors.)

The corresponding new function for general graph structures is as follows.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

MPI GRAPH MAP(comm, nnodes, index, edges, newrank)

IN  comm  input communicator (handle)
IN  nnodes  number of graph nodes (integer)
IN  index  integer array specifying the graph structure, see

MPI GRAPH CREATE

IN  edges  integer array specifying the graph structure
OUT  newrank  reordered rank of the calling process; MPI UNDEFINED

if the calling process does not belong to graph (integer)

int MPI Graph map(MPI Comm comm, int nnodes, int *index, int *edges,
             int *newrank)
MPI GRAPH MAP(COMM, NNODES, INDEX, EDGES, NEWRANK, IERROR)
    INTEGER COMM, NNODES, INDEX(*), EDGES(*), NEWRANK, IERROR

Advice to implementors. The function MPI GRAPH CREATE(comm, nnodes, index, edges, reorder, comm graph), with reorder = true can be implemented by calling MPI GRAPH MAP(comm, nnodes, index, edges, newrank), then calling MPI COMM SPLIT(comm, color, key, comm graph), with color = 0 if newrank ≠

     MPI UNDEFINED, color = MPI UNDEFINED otherwise, and key = newrank.

All other graph topology functions can be implemented locally, using the topology information that is cached with the communicator. (End of advice to implementors.)

1.6 An Application Example

Example 1.6 The example in figure 1.1 shows how the grid definition and inquiry functions can be used in an application program. A partial differential equation, for instance the Poisson equation, is to be solved on a rectangular domain. First, the processes organize themselves in a two-dimensional structure. Each process then inquires about the ranks of its neighbors in the four directions (up, down, right, left). The numerical problem is solved by an iterative method, the details of which are hidden in the subroutine relax.

In each relaxation step each process computes new values for the solution grid function at all points owned by the process. Then the values at inter-process boundaries have to be exchanged with neighboring processes. For example, the exchange subroutine might contain a call like MPI SEND(...,neigh rank(1),...) to send updated values to the left-hand neighbor

(i-1,j).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

integer ndims, num neigh
logical reorder
parameter (ndims=2, num neigh=4, reorder=.true.)
integer comm, comm cart, dims(ndims), neigh def(ndims), ierr
integer neigh rank(num neigh), own position(ndims), i, j
logical periods(ndims)
real∗8 u(0:101,0:101), f(0:101,0:101)
data dims / ndims ∗ 0 /
comm = MPI COMM WORLD
C    Set process grid size and periodicity
call MPI DIMS CREATE(comm, ndims, dims,ierr)
periods(1) = .TRUE.
periods(2) = .TRUE.
C    Create a grid structure in WORLD group and inquire about own position
call MPI CART CREATE (comm, ndims, dims, periods, reorder, comm cart,ierr)
call MPI CART GET (comm cart, ndims, dims, periods, own position,ierr)
C    Look up the ranks for the neighbors.  Own process coordinates are (i,j).
C    Neighbors are (i-1,j), (i+1,j), (i,j-1), (i,j+1)
i = own position(1)
j = own position(2)
neigh def(1) = i-1
neigh def(2) = j
call MPI CART RANK (comm cart, neigh def, neigh rank(1),ierr)
neigh def(1) = i+1
neigh def(2) = j
call MPI CART RANK (comm cart, neigh def, neigh rank(2),ierr)
neigh def(1) = i
neigh def(2) = j-1
call MPI CART RANK (comm cart, neigh def, neigh rank(3),ierr)
neigh def(1) = i
neigh def(2) = j+1
call MPI CART RANK (comm cart, neigh def, neigh rank(4),ierr)
C    Initialize the grid functions and start the iteration
call init (u, f)
do 10 it=1,100
  call relax (u, f)
C    Exchange data with neighbor processes
  call exchange (u, comm cart, neigh rank, num neigh)
10   continue
call output (u)
end

Figure 1.1: Set-up of process structure for two-dimensional parallel Poisson solver.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

Bibliography

[1] Luc Bomans and Rolf Hempel. The Argonne/GMD macros in FORTRAN for portable parallel programming and their implementation on the Intel iPSC/2. Parallel Computing, 15:119–132, 1990.

[2] Robin Calkin, Rolf Hempel, Hans-Christian Hoppe, and Peter Wypior. Portable programming with the parmacs message–passing library. Parallel Computing, Special issue on message–passing interfaces, to appear.

[3] S. Chittor and R. J. Enbody. Performance evaluation of mesh–connected wormhole– routed networks for interprocessor communication in multicomputers. In Proceedings of the 1990 Supercomputing Conference, pages 647–656, 1990.

[4] S. Chittor and R. J. Enbody. Predicting the effect of mapping on the communication performance of large multicomputers. In Proceedings of the 1991 International Conference on Parallel Processing, vol. II (Software), pages II–1 – II–4, 1991.

[5] O. Krämer and H. Mühlenbein. Mapping strategies in message–based multiprocessor systems. Parallel Computing, 9:213–225, 1989.

[6] Parasoft Corporation, Pasadena, CA. Express User’s Guide, version 3.2.5 edition, 1992.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47