Improving the Mondriaan vector distribution

Abstract

Mondriaan is a hypergraph based matrix partitioner, used to distribute the matrix and vectors in parallel sparse matrix-vector multiplication (SpMV) when calculating the product $u=Av$. In this study, we investigate the problem of distributing the input vector $v$ over our $P$ processors, in order to reduce the number of messages, while keeping the communication volume more or less equal. A novel method assigning each vector element to the lowest numbered processor gives us significantly lower total message count, while keeping the communication volume constant. Another method, a novel hypergraph based heuristic, roughly halves the total amount of messages, while it increases the communication volume. Both newly developed methods provide large reductions in the total amount of messages and can hence be considered as alternative vector distribution methods.