Experimental Evaluation of Efficient Sparse Matrix Distributions

Sparse matrix problems are difficult to parallelize efficiently on distributed memory machines since non-zero elements are unevenly scattered and are accessed via multiple levels of indirection. Irregular distributions that achieve good load balance and locality are hard to compute, have high memory overheads and also lead to further indirection in locating distributed data. This paper evaluates alternative semi-regular distribution strategies which trade off the quality of loadbalance and locality for lower decomposition overheads and efficient lookup. The proposed techniques are compared to an irregular sparse matrix partitioner and the relative merits of each distribution method are outlined. 1 Introduction Sparse matrices are used in a large number of important scientific codes, such as molecular dynamics, CFD solvers, finite element methods and climate modelling. Unfortunately, these applications are hard to parallelize efficiently. This is because sparse matrices are represente..