Minimizing Communication Cost in Fine-Grain Partitioning of Sparse Matrices

Bora Uçar and Cevdet Aykanat

Abstract.We show a two-phase approach for minimizing various communication-cost metrics in fine-grain partitioning of sparse matrices for parallel processing. In the first phase, we obtain a partitioning with the existing tools on the matrix to determine computational loads of the processor. In the second phase, we try to minimize the communication-cost metrics. For this purpose, we develop communication-hypergraph and partitioning models. We experimentally evaluate the contributions on a PC cluster.

Key words. parallel computing, sparse matrix-vector multiply, sparse matrix partitioning, fine grain partitioning