A model for predicting the performance of sparse matrix vector multiply (SpMV) using memory bandwidth requirements and data locality
Date
2012
Authors
Dinkins, Stephanie, author
Strout, Michelle Mills, advisor
Rajopadhye, Sanjay V., committee member
Mueller, Jennifer L., committee member
Journal Title
Journal ISSN
Volume Title
Abstract
Sparse matrix vector multiply (SpMV) is an important computation that is used in many scientific and structural engineering applications. Sparse computations like SpMV require the use of special sparse data structures that efficiently store and access non-zeros. However, sparse data structures can tax the memory bandwidth of a machine and limit the performance of a computation, which for these computations is typically less than 10% of a processor's peak floating point performance. The goal of this thesis was to understand the trade-off between memory bandwidth needs and data locality for SpMV performance. We construct three performance models based on memory bandwidth requirements and the data locality that is associated with the non-zero orderings within a sparse data structure. Our approach uses metrics that can be applied to any sparse data structure to model SpMV performance. We use a data locality metric termed Manhattan distance to predict the data locality execution time of each non-zero ordering, which produced strong per matrix results. Based on the per matrix results for the Manhattan distance we constructed a model that computes a linear fit for multiple parameters, but those results were not promising. We found that the memory bandwidth requirement for a data structure is a key component to predicting performance. Our final model uses memory bandwidth pressure and an averaged predicted data locality time to accurately predict the fastest performing data structure 73-84% of the time, depending upon the machine. Our results indicate that often the sparse data structure with the least taxation on the memory bandwidth produces the fastest execution times.
Description
Rights Access
Subject
data locality
Manhattan distance
performance model
sparse matrices
sparse matrix vector multiply
SpMV