next up previous contents
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 tex2html_wrap_inline12361 and tex2html_wrap_inline12363 be permutations so that


Here tex2html_wrap_inline12365 and tex2html_wrap_inline12367 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 tex2html_wrap_inline12373 , tex2html_wrap_inline12375 and tex2html_wrap_inline12377 are assigned to tex2html_wrap_inline12379 . 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 tex2html_wrap_inline12383 and corresponding blocks of columns of tex2html_wrap_inline12385 .



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

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 tex2html_wrap_inline12393 mesh, tex2html_wrap_inline12395 , with tex2html_wrap_inline12397 and tex2html_wrap_inline12399 . 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 tex2html_wrap_inline12401 and tex2html_wrap_inline12403 , this can always be enforced.) The distribution of A is now induced by requiring block of columns tex2html_wrap_inline12407 to be assigned to the same column of nodes as sub-vector tex2html_wrap_inline12409 , and block of rows tex2html_wrap_inline12411 to the same row of nodes as sub-vector tex2html_wrap_inline12413 (and thus tex2html_wrap_inline12415 ). 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 tex2html_wrap_inline12433 to be assigned to the same column of nodes as sub-vector tex2html_wrap_inline12435 , and block or rows tex2html_wrap_inline12437 to the same row of nodes as sub-vector tex2html_wrap_inline12439 (and thus tex2html_wrap_inline12441 ). This is also illustrated in Figure 1.2. Notice that the wrapping of the vectors induces a tight wrapping of blocks of rows of tex2html_wrap_inline12443 , and a looser wrapping (by a factor of r ) of the blocks of columns of tex2html_wrap_inline12447 .

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 tex2html_wrap_inline12453 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:

next up previous contents
Next: 1.4 Redistributing and Duplicating Up: 1 Introduction Previous: 1.2 Natural Description of