Paper Info
Title
Using sampled information: is it enough for the sparse matrix-vector product locality optimization?
Abstract
One of the main factors that affect the performance of the sparse matrix-vector product (SpMV) is the low data reuse caused by the irregular and indirect memory access patterns. Different strategies to deal with this problem such as data reordering techniques have been proposed. The computational cost of these techniques is typically high because they consider all the nonzeros of the sparse matrix in order to find an appropriate permutation of rows and columns that improves the SpMV performance. In this paper, we analyze the possibility of increasing the locality of the SpMV using incomplete information in the reordering process. This partial information comes as a consequence of considering only a subset of the nonzero elements of the matrix. These nonzeros are obtained from the original matrix through a sampling process. In particular, two different sampling methods have been considered: a random sampling and an event-based sampling using hardware counters. We have detected that a small number of samples is enough to obtain quality reorderings. As a consequence, using sampling-based reorderings leads to noticeable performance improvements with respect to the non-reordered matrices, reaching speedup values up to 2.1x. In addition, an important reduction in the computational time required by the reordering technique has been observed. Copyright (c) 2012 John Wiley & Sons, Ltd.
Year
DOI
Venue
2014
10.1002/cpe.2949
CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE
Keywords
DocType
Volume
sparse matrix,locality,hardware counters,sampling,performance
Journal
26
Issue
ISSN
Citations 
1
1532-0626
0
PageRank 
References 
Authors
0.34
18
5
Name
Order
Citations
PageRank
Juan Carlos Pichel1406.66
Juan Angel Lorenzo211.11
Francisco F. Rivera317726.17
Dora Blanco Heras45111.46
Tomás F. Pena56816.56