|Optimal Algorithm Selection of Parallel Sparse Matrix-Vector Multiplication Is Important|
|Makoto Kudoh - Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo|
Hisayasu Kuroda - Computer Centre Division, Information Technology Center, The University of Tokyo
Takahiro Katagiri - PRESTO, Japan Science and Technology Corporation(JST)
Yasumasa Kanada - Computer Centre Division, Information Technology Center, The University of Tokyo
The computational performance of parallel sparse matrix-vector multiplication (SpMxV) depends highly on the non-zero structure of the target matrix and the architectonic character of the machine. Therefore it is important to select the best optimization technique according to these characteristics not like conventional libraries which use uniform optimization technique for all matrices and machines. In this paper, our parallel SpMxV routine which includes several optimization algorithms is described. The performance with optimal algorithm is compared to that with uniform default algorithm on five kinds of parallel machines: PC-cluster, SMP machines including Ultra Sparc II, MIPS R12000, Alpha 21264, and Itanium. The average speed-up of 1.36 is obtained.