On Two-Dimensional Sparse Matrix Partitioning: Models, Methods, and a Recipe
Ümit V. Çatalyürek, Cevdet Aykanat, Bora Uçar · SIAM Journal on Scientific Computing · 2010
We consider two-dimensional partitioning of general sparse matrices for parallel sparse matrix-vector multiply operation. We present three hypergraph-partitioning-based methods, each having unique advantages. The first one treats the nonzeros of the matrix individually and hence produces fine-grain partitions. The other two produce coarser partitions, where one of them imposes a limit on the number of messages sent and received by a single processor, and the other trades that limit for a lower communication volume. We also present a thorough experimental evaluation of the proposed two-dimensional partitioning methods together with the hypergraph-based one-dimensional partitioning methods, using an extensive set of public domain matrices. Furthermore, for the users of these partitioning methods, we present a partitioning recipe that chooses one of the partitioning methods according to some matrix characteristics.
Cited by 127 works. doi:10.1137/080737770 Open-access PDF
Authors
References
- MapReduce
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- Benchmarking optimization software with performance profiles
- Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication
- Graph partitioning models for parallel computing
- A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication
- Sparse Matrix Computations on Parallel Processor Arrays
- Distributed processing of very large datasets with DataCutter
- Partitioning Rectangular and Structurally Unsymmetric Sparse Matrices for Parallel Processing
- A new mapping heuristic based on mean field annealing