TY - GEN
T1 - A medium-grain method for fast 2D bipartitioning of sparse matrices
AU - Pelt, Daniël M.
AU - Bisseling, Rob H.
PY - 2014/8/14
Y1 - 2014/8/14
N2 - We present a new hyper graph-based method, the medium-grain method, for solving the sparse matrix partitioning problem. This problem arises when distributing data for parallel sparse matrix-vector multiplication. In the medium-grain method, each matrix nonzero is assigned to either a row group or a column group, and these groups are represented by vertices of the hyper graph. For an m x n sparse matrix, the resulting hyper graph has m+n vertices and m+n hyper edges. Furthermore, we present an iterative refinement procedure for improvement of a given partitioning, based on the medium-grain method, which can be applied as a cheap but effective post processing step after any partitioning method. The medium-grain method is able to produce fully two-dimensional bipartitionings, but its computational complexity equals that of one-dimensional methods. Experimental results for a large set of sparse test matrices show that the medium-grain method with iterative refinement produces bipartitionings with lower communication volume compared to current state-of-the-art methods, and is faster at producing them.
AB - We present a new hyper graph-based method, the medium-grain method, for solving the sparse matrix partitioning problem. This problem arises when distributing data for parallel sparse matrix-vector multiplication. In the medium-grain method, each matrix nonzero is assigned to either a row group or a column group, and these groups are represented by vertices of the hyper graph. For an m x n sparse matrix, the resulting hyper graph has m+n vertices and m+n hyper edges. Furthermore, we present an iterative refinement procedure for improvement of a given partitioning, based on the medium-grain method, which can be applied as a cheap but effective post processing step after any partitioning method. The medium-grain method is able to produce fully two-dimensional bipartitionings, but its computational complexity equals that of one-dimensional methods. Experimental results for a large set of sparse test matrices show that the medium-grain method with iterative refinement produces bipartitionings with lower communication volume compared to current state-of-the-art methods, and is faster at producing them.
KW - hypergraph
KW - parallel computing
KW - sparse matrix-vector multiplication
UR - http://www.scopus.com/inward/record.url?scp=84906672754&partnerID=8YFLogxK
U2 - 10.1109/IPDPS.2014.62
DO - 10.1109/IPDPS.2014.62
M3 - Conference contribution
AN - SCOPUS:84906672754
SN - 9780769552071
T3 - Proceedings of the ... International Parallel and Distributed Processing Symposium
SP - 529
EP - 539
BT - Proceedings IEEE 28th International Parallel & Distributed Processing Symposium (IPDPS 2014)
PB - IEEE
T2 - 28th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2014
Y2 - 19 May 2014 through 23 May 2014
ER -