Well balanced sparse matrix-vector multiplication on a parallel heterogeneous system

This paper discusses well balanced implementations of sparse matrix-vector multiplication on heterogeneous environments. A new heuristic is proposed for balancing the computing load over the processors proportionally to their power. This is done by defining a distribution model which splits the sparse matrix in k-way partitions, in order to minimize the total execution time. An implementation of the sparse matrix vector multiplication in heterogeneous environment using parallel object-oriented programming model POP-C++ shows that this ID-partitioning heuristic improve greatly the performance of the product, in comparison with block row decomposition