Next: 9.5.5 Performance Versus Scattering Up: LU Factorization of Previous: 9.5.3 Reduced-Communication Pivoting

9.5.4 New Data Distributions

We introduce new closed-form -time, -memory data distributions  useful for sparse matrix  factorizations and the problems that generate such matrices. We quantify evaluation costs in Table 9.3.

Table 9.3: Evaluation Times for Three Data Distributions

Every concurrent data structure is associated with a logical process grid at creation (cf., Figure 9.12 and [Skjellum:90a;90c]). Vectors are either row- or column-distributed within a two-dimensional process grid. Row-distributed vectors are replicated in each process column, and distributed in the process rows. Conversely, column-distributed vectors are replicated in each process row, and distributed in the process columns. Matrices are distributed both in rows and columns, so that a single process owns a subset of matrix rows and columns. This partitioning follows the ideas proposed by Fox et al. [Fox:88a] and others. Within the process grid, coefficients of vectors and matrices are distributed according to one of several data distributions. Data distributions are chosen to compromise between load-balancing requirements and constraints on where information can be calculated in the ensemble.

Definition 1 (Data-Distribution Function) A data-distribution function maps three integers where , is the global name of a coefficient, P is the number of processes among which all coefficients are to be partitioned, and M is the total number of coefficients. The pair represents the process p () and local (process-p) name i of the coefficient (). The inverse distribution function transforms the local name i back to the global coefficient name I.

The formal requirements for a data-distribution function are as follows. Let be the set of global coefficient names associated with process , defined implicitly by a data distribution function . The following set properties must hold:

The cardinality of the set , is given by .

The linear and scatter data-distribution functions are most often defined. We generalize these functions (by blocking  and scattering parameters) to incorporate practically important degrees of freedom. These generalized distribution functions yield optimal static load balance  as do the unmodified functions described in [Velde:90a] for unit block size, but they differ in coefficient placement. This distinction is technical, but necessary for efficient implementations.

Definition 2 (Generalized Block-Linear) The definitions for the generalized block-linear distribution function, inverse, and cardinality function are:

while

where B denotes the coefficient block size,

and where .

For B=1, a load-balance-equivalent variant of the common linear data-distribution function is recovered. The general block-linear distribution function divides coefficients among the P processes so that each is a set of coefficients with contiguous global names, while optimally load-balancing the b blocks among the P sets. Coefficient boundaries between processes are on multiples of B. The maximum possible coefficient imbalance between processes is B. If , the last block in process P-1 will be foreshortened.

Definition 3 (Parametric Functions) To allow greater freedom in the distribution of coefficients among processes, we define a new, two-parameter distribution function family, . The B blocking  parameter (just introduced in the block-linear function) is mainly suited to the clustering of coefficients that must not be separated by an interprocess boundary (again, see [Skjellum:90c] for a definition of general block-scatter, ). Increasing B worsens the static load balance. Adding a second scaling parameter S (of no impact on the static load balance) allows the distribution to scatter coefficients to a greater or lesser degree, directly as a function of this one parameter. The two-parameter distribution function, inverse and cardinality function are defined below. The one-parameter distribution function family, , occurs as the special case B=1, also as noted below:

where

with

and where r, b, etc. are as defined above. The inverse distribution function is defined as follows:

with

For S = 1, a block-scatter distribution results, while for , the generalized block-linear distribution function is recovered. See also [Skjellum:90c].

Definition 4 (Data Distributions) Given a data-distribution function family (), a process list of P (Q), M (N) as the number of coefficients, and a row (respectively, column) orientation, a row (column) data distribution () is defined as:

respectively,

A two-dimensional data distribution may be identified as consisting of a row and column distribution defined over a two-dimensional process grid of processes, as .

Further discussion and detailed comparisons on data-distribution functions are offered in [Skjellum:90c]. Figure 9.13 illustrates the effects of linear and scatter data-distribution functions on a small rectangular array of coefficients.

Next: 9.5.5 Performance Versus Scattering Up: LU Factorization of Previous: 9.5.3 Reduced-Communication Pivoting

Guy Robinson
Wed Mar 1 10:19:35 EST 1995