Next: 1.4 Redistributing and Duplicating Up: 1 Introduction Previous: 1.2 Natural Description of

# 1.3 Physically Based Matrix Distribution

We postulate that one should never start by considering how to decompose the matrix. Rather, one should start by considering how to decompose the physical problem to be solved. Notice that it is the elements of vectors that are typically associated with data of physical significance and it is therefore their distribution to nodes that is directly related to the distribution of the problem to be solved. A matrix (discretized operator)   merely represents the relation between two vectors (discretized spaces):

Since it is more natural to start with distributing the problem to nodes, we partition x and y , and assign portions of these vectors to nodes. The matrix A should then be distributed to nodes in a fashion consistent with the distribution of the vectors, as we shall show next. We will call a   matrix distribution physically based   if the layout of the vectors which induce the distribution of A to nodes is consistent with where an application would naturally want them. We will use the abbreviation PBMD   for Physically Based Matrix Distribution.

As discussed, we must start by describing the distribution of the vectors, x and y , to nodes, after which we will show how the matrix distribution is induced   (derived) by the vector distribution. Let and be permutations so that

Here and are the permutations that order the elements of x and y , respectively, that are to be assigned to the first node first, then the ones assigned to the second node, and so forth. Thus if the nodes are labeled , and are assigned to . Notice that the above discussion links the linear algebra object ``vector'' to a mapping to the nodes. In most other approaches to matrix distribution, vectors appear as special cases of matrices, or as somehow linked to the rows and columns of matrices, after the distribution of matrices is already specified. We will also link rows and columns of matrices to vectors, but only after the distribution of the vectors has been determined, as prescribed by the application. We again emphasize that this means we inherently start with the (discretized) physical problem, rather than the (discretized) operator.

Next, we partition matrix A conformally:

Notice that

and thus

This exposes a natural tie between sub-vectors of and corresponding blocks of columns of .

Also

so there is a natural tie between sub-vectors of and corresponding blocks of rows of .

It has been well documented [, ] that for scalability reasons, it is often important to assign matrices to nodes of a distributed memory architecture using a so-called   two-dimensional matrix distribution. To do so, the p = rc nodes are viewed as a logical mesh, , with and . This requires us to decide how to distribute the sub-vectors to the two-dimensional mesh. We will assume this is done in column-major order. (Notice that by appropriate choice of and , this can always be enforced.) The distribution of A is now induced by requiring block of columns to be assigned to the same column of nodes as sub-vector , and block of rows to the same row of nodes as sub-vector (and thus ). This is illustrated in Figure 1.1.

Often, for   load balancing reasons, it becomes important to over-decompose the vectors and matrices, and   wrap the sub-blocks onto the node mesh. This can be described by now partitioning x and y so that

where N >> p . Partitioning A conformally yields the blocked matrix

An explicitly   two-dimensional wrapped distribution for the matrix can now be obtained by wrapping the blocks of x and y , which induces a wrapping in the distribution of A , as illustrated in Figure 1.2. Again, the sub-vectors are assigned to the node mesh in column-major order, wrapping as necessary. As before, the distribution of A is now induced by requiring block of columns to be assigned to the same column of nodes as sub-vector , and block or rows to the same row of nodes as sub-vector (and thus ). This is also illustrated in Figure 1.2. Notice that the wrapping of the vectors induces a tight wrapping of blocks of rows of , and a looser wrapping (by a factor of r ) of the blocks of columns of .

We emphasize that the distributions described in Figures  1.1 and 1.2 may appear to be special cases of Physically Based Matrix Distribution, since corresponding sub-blocks of x and y are assigned to the same node. Notice that by choosing in Equation 1.2, a general distribution can be attained [].

Having just stated that we can achieve total generality, we need to also clearly state that in the initial implementation of PLAPACK, we actually only implement a special case:

• we do not permute x and y , i.e., , the identity matrix, and
• we require all sub-vectors and to be of the same fixed length, the     distribution blocking size .

Next: 1.4 Redistributing and Duplicating Up: 1 Introduction Previous: 1.2 Natural Description of

rvdg@cs.utexas.edu