Материал готовится,

пожалуйста, возвращайтесь позднее

пожалуйста, возвращайтесь позднее

HypergraphPartitioning forParallel Iterative Solutionof General Sparse Linear Systems∗

Masha Sosonkina† Bora Uc.ar‡ Yousef Saad§

February 1, 2007

Abstract

The efﬁciencyof parallel iterative methods for solving linear systems, arising from real-life applications, depends greatly on matrix characteristics and on the amount of parallel overhead. It is often viewed that a major part of this overhead can be caused by parallel matrix-vector multiplications. However, fordifﬁcult large linear systems, the precondition¬ing operations needed to accelerate convergence are to be performed in parallel and may also incur substantial overhead. To obtain an efﬁcient preconditioning, it is desirable to consider certain matrix numerical properties in the matrix partitioning process.

In general, graph partitioners consider the nonzero structure of a matrix to balance the number of unknowns and to decrease communication volume among parts. The present workbuilds uponhypergraph partitioning techniques because of their ability to handle non-symmetric and irregular structured matrices and because they correctly minimize commu¬nicationvolume. First, severalhyperedge weight schemes are proposed to account for the numerical matrix property called diagonal dominance of rows and columns. Then, an algo¬rithm for the independent partitioning of certain submatrices followed by the matching of the obtained parts is presented in detail along with a proof that it correctly minimizes the total communicationvolume.Forthe proposedvariantsofhypergraph partitioning models, numer¬ical experiments compare the iterations to converge, investigate the diagonal dominance of the obtained parts, and show the values of the partitioning cost functions.

1 Introduction

Although iterative linear system solution techniques require relatively little effort to parallelize, achieving good performance may not be straightforward. Of particular importance for the perfor¬mance are the matrix-vector product and the quality ofthe preconditioner. While the structure of the sparse matrix governs the former, the latter is heavily based on the matrix numerical properties andaffectstheconvergence behaviorofthe iterative method. Conversely, bothfactors dependon how the sparse matrix is partitioned, which, in general, is dictated by a graph partitioning algo¬rithm employed andby the representationofa matrixina graph form.

∗This work was supported in part by NERSC and in part by NSF under grant NSF/ACI-0305120.

†Ames Laboratory/DOE, Iowa State University, Ames, IA 50011,(masha@scl.ameslab.gov).

‡Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322 (ubora@mathcs.emory.edu).

§Department of Computer Science and Engineering, University of Minnesota, 200 Union Street S.E., Minneapolis, MN 55455,(saad@cs.umn.edu).

The ﬁrststepin representingthe patternofamatrixis oftento symmetrizeit,so thatan undirected graph is obtained Then, each equation and corresponding unknown is represented by a vertex and each nonzero entry is represented by an edge between the vertices it couples. This “symmetric” graph representationis widely usedbyavarietyof graph partitioners, such as Chaco [21], Distributed Set Expansion (DSE) [34], and MeTiS [23]. By attempting to minimize edge cuts, these algorithms may reduce the lengthof the boundary partbut not necessarily the number of communications, as shown, e.g., in [19].

Masha Sosonkina† Bora Uc.ar‡ Yousef Saad§

February 1, 2007

Abstract

The efﬁciencyof parallel iterative methods for solving linear systems, arising from real-life applications, depends greatly on matrix characteristics and on the amount of parallel overhead. It is often viewed that a major part of this overhead can be caused by parallel matrix-vector multiplications. However, fordifﬁcult large linear systems, the precondition¬ing operations needed to accelerate convergence are to be performed in parallel and may also incur substantial overhead. To obtain an efﬁcient preconditioning, it is desirable to consider certain matrix numerical properties in the matrix partitioning process.

In general, graph partitioners consider the nonzero structure of a matrix to balance the number of unknowns and to decrease communication volume among parts. The present workbuilds uponhypergraph partitioning techniques because of their ability to handle non-symmetric and irregular structured matrices and because they correctly minimize commu¬nicationvolume. First, severalhyperedge weight schemes are proposed to account for the numerical matrix property called diagonal dominance of rows and columns. Then, an algo¬rithm for the independent partitioning of certain submatrices followed by the matching of the obtained parts is presented in detail along with a proof that it correctly minimizes the total communicationvolume.Forthe proposedvariantsofhypergraph partitioning models, numer¬ical experiments compare the iterations to converge, investigate the diagonal dominance of the obtained parts, and show the values of the partitioning cost functions.

1 Introduction

Although iterative linear system solution techniques require relatively little effort to parallelize, achieving good performance may not be straightforward. Of particular importance for the perfor¬mance are the matrix-vector product and the quality ofthe preconditioner. While the structure of the sparse matrix governs the former, the latter is heavily based on the matrix numerical properties andaffectstheconvergence behaviorofthe iterative method. Conversely, bothfactors dependon how the sparse matrix is partitioned, which, in general, is dictated by a graph partitioning algo¬rithm employed andby the representationofa matrixina graph form.

∗This work was supported in part by NERSC and in part by NSF under grant NSF/ACI-0305120.

†Ames Laboratory/DOE, Iowa State University, Ames, IA 50011,(masha@scl.ameslab.gov).

‡Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322 (ubora@mathcs.emory.edu).

§Department of Computer Science and Engineering, University of Minnesota, 200 Union Street S.E., Minneapolis, MN 55455,(saad@cs.umn.edu).

The ﬁrststepin representingthe patternofamatrixis oftento symmetrizeit,so thatan undirected graph is obtained Then, each equation and corresponding unknown is represented by a vertex and each nonzero entry is represented by an edge between the vertices it couples. This “symmetric” graph representationis widely usedbyavarietyof graph partitioners, such as Chaco [21], Distributed Set Expansion (DSE) [34], and MeTiS [23]. By attempting to minimize edge cuts, these algorithms may reduce the lengthof the boundary partbut not necessarily the number of communications, as shown, e.g., in [19].

Загрузка...

Выбрать следующее задание

Ты добавил

Выбрать следующее задание

Ты добавил