Abstract

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.

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.

Last update: Wed Jun 12 14:26:52 2002 WEST