Parallel Blocked Sparse Matrix-Vector Multiplication with Dynamic Parameter Selection Method

摘要

A blocking method is a popular optimization technique for sparse matrix-vector multiplication (SpMxV). In this paper, a new blocking method which generalizes the conventional two blocking methods and its application to the parallel environment are proposed. This paper also proposes a dynamic parameter selection method for blocked parallel SpMxV which automatically selects the parameter set according to the characteristics of the target matrix and machine in order to achieve high performance on various computational environments. The performance with dynamically selected parameter set is compared with the performance with generally-used fixed parameter sets for 12 types of sparse matrices on four parallel machines: including PentiumⅢ, Spare Ⅱ, MIPS R12000 and Itanium. The result shows that the performance with dynamically selected parameter set is the best in most cases.