This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Mellor-Crummey, J. Articles by Garvin, J. Search for Related Content Social Bookmarking                         What's this?

Optimizing Sparse Matrix–Vector Product Computations Using Unroll and Jam

DEPARTMENT OF COMPUTER SCIENCE, RICE UNIVERSITY, HOUSTON, USA

John Garvin

DEPARTMENT OF COMPUTER SCIENCE, RICE UNIVERSITY, HOUSTON, USA

Large-scale scientific applications frequently compute sparse matrix–vector products in their computational core. For this reason, techniques for computing sparse matrix– vector products efficiently on modern architectures are important. In this paper we describe a strategy for improving the performance of sparse matrix–vector product computations using a loop transformation known as unrollandjam. We describe a novel sparse matrix representation that enables us to apply this transformation. Our approach is best suited for sparse matrices that have rows with a small number of predictable lengths. This work was motivated by sparse matrices that arise in SAGE, an application from Los Alamos National Laboratory. We evaluate the performance benefits of our approach using sparse matrices produced by SAGE for a pair of sample inputs. We show that our strategy is effective for improving sparse matrix–vector product performance using these matrices on MIPS R12000, Alpha Ev67, IBM Power 3, and Itanium 2 processors. Our measurements show that for this class of sparse matrices, our strategy improves sparse matrix–vector product performance from a low of 41% on MIPS to well over a factor of 2 on Itanium.

Key Words: Sparse matrices • matrix vector product • performance optimization • sparse matrix format • microfactors • data structures

International Journal of High Performance Computing Applications, Vol. 18, No. 2, 225-236 (2004)
DOI: 10.1177/1094342004038951


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?