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. Distributions that achieve good load balance and locality are hard to compute and also lead to further indirection in locating distributed data. This paper evaluates alternative distribution strategies which trade off the quality of load-balance and locality for lower decomposition costs and efficient lookup. The proposed techniques are compared with previous strategies for parallelizing sparse matrix problems and the relative merits of each method is 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, particularly using automated compiler techniques. This is because sparse matrices are repre..