Virtual Topologies - Faculty of Science, HKBU

Virtual Topologies

Virtual Topologies

Introduction Many computational science and engineering problems reduce at the end to either a series of matrix or some form of grid operations, be it through differential, integral or other methods the dimensions of the matrices or grids are often determined by the physical problems Frequently in multiprocessing these matrices or grids are partitioned, or domain-decomposed so that each partition (or subdomain) is assigned to a process One such example is an m x n matrix decomposed into p g x n submatrices with each assigned to be worked on by one of the p processes

Introduction • Many computational science and engineering problems reduce at the end to either a series of matrix or some form of grid operations, be it through differential, integral or other methods. The dimensions of the matrices or grids are often determined by the physical problems. • Frequently in multiprocessing, these matrices or grids are partitioned, or domain-decomposed, so that each partition (or subdomain) is assigned to a process. • One such example is an m x n matrix decomposed into p q x n submatrices with each assigned to be worked on by one of the p processes

Introduction In this case, each process represents one distinct submatrix in a straightforward manner. However, an algorithm might dictate that the matrix be decomposed into a pxg logical grid, whose elements are themselves each an rx s matrix. This requirement might be due to a number of reasons: efficiency considerations, ease in code mplementation code clarity to name a few Although it is still possible to refer to each of these pxq subdomains by a linear rank number, it is obvious that a mapping of the linear process rank to a 2D virtual rank numbering would facilitate a much clearer and natural computational representation To address the needs of this and other topological layouts, the MPl library provides two types of topology routines Cartesian and graph topologies. Only Cartesian topology and the associated routines will be discussed in this chapter

Introduction • In this case, each process represents one distinct submatrix in a straightforward manner. However, an algorithm might dictate that the matrix be decomposed into a pxq logical grid, whose elements are themselves each an r x s matrix. This requirement might be due to a number of reasons: efficiency considerations, ease in code implementation, code clarity, to name a few. • Although it is still possible to refer to each of these pxq subdomains by a linear rank number, it is obvious that a mapping of the linear process rank to a 2D virtual rank numbering would facilitate a much clearer and natural computational representation. • To address the needs of this and other topological layouts, the MPI library provides two types of topology routines: Cartesian and graph topologies. Only Cartesian topology and the associated routines will be discussed in this chapter

MPI Topology Routines

MPI Topology Routines

Virtual Topology MPI Routines Some of the MPl topology routines are MPI CART CREATE MPI CART COORDS MPI CART RANK MPI CART SUB MPI CARTDIM GET MPI CART GET MPI CART SHIFT These routines are discussed in the following sections

Virtual Topology MPI Routines • Some of the MPI topology routines are – MPI_CART_CREATE – MPI_CART_COORDS – MPI_CART_RANK – MPI_CART_SUB – MPI_CARTDIM_GET – MPI_CART_GET – MPI_CART_SHIFT • These routines are discussed in the following sections

MPI CART CREATE Definition of mPl cart create Used to create cartesian coordinate structures of arbitrary dimensions, on the processes. The new communicator receives no cached information The MP cart create routine creates a new communicator using a Cartesian topology int MPl Cart create(MPI Comm old comm, int ndims int *dim size, int*periods, int reorder, MPI Comm new comm The function returns an int error flag

MPI_CART_CREATE • Definition of MPI_CART_CREATE – Used to create Cartesian coordinate structures, of arbitrary dimensions, on the processes. The new communicator receives no cached information. • The MPI_CART_CREATE routine creates a new communicator using a Cartesian topology. int MPI_Cart_create(MPI_Comm old_comm, int ndims, int *dim_size, int *periods, int reorder, MPI_Comm *new_comm) • The function returns an int error flag

MPI CART CREATE Variable C Type In/out Description Name old comm MPI Comm Input Communicator handle Indies Input Number of dimensions dim size Input Array of size dims providing length in each dimension periods int Input Array of size dims specifying periodicity status of each dimension reorder int Input whether process rank reordering by MPI is permitted new comm MPI Comm* Output Communicator handle

MPI_CART_CREATE Variable Name C Type In/Out Description old_comm MPI_Comm Input Communicator handle ndims int Input Number of dimensions dim_size int * Input Array of size ndims providing length in each dimension periods int * Input Array of size ndims specifying periodicity status of each dimension reorder int Input whether process rank reordering by MPI is permitted new_comm MPI_Comm * Output Communicator handle

MPI CART CREATE ude" stdio. h #include"mpi. h MPI Comm old comm, new comm tint ndis, reorder, periods [2], dim size[2] old comm= MPI COMM WORLD dims 2 2D matrix/grid*/ dim size[0]=3:/rows*/ dim size[1]=2;/*columns*/ periods[0]=1; /row periodic(each column forms a ring)*/ periods[1]=0; /columns non-periodic * reorder =1; / allows processes reordered for efficiency * MPI Cart create(old comm, ndims, dim size, periods, reorder, &new comm)

MPI_CART_CREATE #include "stdio.h" #include "mpi.h" MPI_Comm old_comm, new_comm; int ndims, reorder, periods[2], dim_size[2]; old_comm = MPI_COMM_WORLD; ndims = 2; /* 2D matrix/grid */ dim_size[0] = 3; /* rows */ dim_size[1] = 2; /* columns */ periods[0] = 1; /* row periodic (each column forms a ring) */ periods[1] = 0; /* columns non-periodic */ reorder = 1; /* allows processes reordered for efficiency */ MPI_Cart_create(old_comm, ndims, dim_size, periods, reorder, &new_comm);

MPI CART CREATE In the above example we use MPI CART CREATE to map 0,0(0) 0,1(1) or rename)6 processes from a linear ordering(0, 1, 2, 3, 4, 5) into a two-dimensional matrix ordering of 3 rows by 2 1,0(2 1,1(3) columns(ie.,(0,0),(0,1), 2,1) Figure 8.1(a)depicts the resulting cartesian grid representation for the 2,0(4) 2,1(5) processes. The index pair i, represent row"iand column j. The corresponding(inear) rank number is enclosed in Figure 8.1(a). Cartesian parentheses Grid

MPI_CART_CREATE • In the above example we use MPI_CART_CREATE to map (or rename) 6 processes from a linear ordering (0,1,2,3,4,5) into a two-dimensional matrix ordering of 3 rows by 2 columns ( i.e., (0,0), (0,1), ..., (2,1) ). • Figure 8.1 (a) depicts the resulting Cartesian grid representation for the processes. The index pair "i,j" represent row "i" and column "j". The corresponding (linear) rank number is enclosed in parentheses. 0,0 (0) 0,1 (1) 1,0 (2) 1,1 (3) 2,0 (4) 2,1 (5) Figure 8.1 (a). Cartesian Grid

MPI CART CREATE With processes renamed in a 2d. No periodicity is imposed on the grid topology, we are able to second dimension( periods[1]=0) assign or distribute work,or Any reference to the column index distinguish among the processes by their grid topology rather than outside of its defined range(in this by their linear process ranks case 0 to 1)will result in a Additionally, we have imposed negative process rank(equal to periodicity along the first MPI PROC NULL Which is-1), dimension( periods[0]=1), which which signifies that it is out of means that any reference beyond range the first or last entry of any column Similarly, if periodicity was defined will be wrapped around cyclically only for the column index (i.e For example, row index i=-1, due periods[0]=0 periods[1]=1), each to periodicity, corresponds to i=2 row would wrap around itself Similarly. i=-2 maps onto i=1 Likewise,i=3 is the same asi=0

MPI_CART_CREATE • With processes renamed in a 2D grid topology, we are able to assign or distribute work, or distinguish among the processes by their grid topology rather than by their linear process ranks. • Additionally, we have imposed periodicity along the first dimension ( periods[0]=1 ), which means that any reference beyond the first or last entry of any column will be wrapped around cyclically. • For example, row index i = -1, due to periodicity, corresponds to i = 2. Similarly, i = -2 maps onto i = 1. Likewise, i = 3 is the same as i = 0. • No periodicity is imposed on the second dimension ( periods[1]=0 ). Any reference to the column index outside of its defined range (in this case 0 to 1) will result in a negative process rank (equal to MPI_PROC_NULL which is -1), which signifies that it is out of range. • Similarly, if periodicity was defined only for the column index (i.e., periods[0]=0; periods[1]=1), each row would wrap around itself