Adaptive Runtime Tuning of Parallel Sparse Matrix-Vector Multiplication on Distributed Memory Systems

TitleAdaptive Runtime Tuning of Parallel Sparse Matrix-Vector Multiplication on Distributed Memory Systems
Publication TypeConference Paper
Year of Publication2008
AuthorsLee, Seyong, and Eigenmann Rudolf
Conference NameACM International Conference on Supercomputing (ICS08)
Date Published06/2008
Abstract

Sparse matrix-vector (SpMV) multiplication is a widely used kernel in scientific applications. In these applications, the SpMV multiplication is usually deeply nested within multiple loops and thus executed a large number of times. We have observed that there can be significant performance variability, due to irregular memory access patterns. Static performance optimizations are difficult because the patterns may be known only at runtime. In this paper, we propose adaptive runtime tuning mechanisms to improve the parallel performance on distributed memory systems. Our adaptive iteration-to-process mapping mechanism balances computational load at runtime with negligible overhead (1% on average), and our runtime communication selection algorithm searches for the best communication method for a given data distribution and mapping. Actual runs on 26 real matrices show that our runtime tuning system reduces execution time up to 68.8% (30.9% on average) over a base block-distributed parallel algorithm on distributed systems with 32 nodes.

DOI10.1145/1375527.1375558
File: