Variable-Sized Blocks for Locality-Aware SpMV

Naveen Namashivavam, Sanyam Mehta, Pen Chung Yew

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Blocking is an important optimization option available to mitigate the data movement overhead and improve the temporal locality in SpMV, a sparse BLAS kernel with irregular memory reference pattern. In this work, we propose an analytical model to determine the effective block size for highly irregular sparse matrices by factoring the distribution of non-zeros in the sparse dataset. As a result, the blocks generated by our scheme are variable-sized as opposed to constant-sized in most existing SpMV algorithms. We demonstrate our blocking scheme using Compressed Vector Blocks (CVB), a new column-based blocked data format, on Intel Xeon Skylake-X multicore processor. We evaluated the performance of CVB-based SpMV with variable-sized blocks using extensive set of matrices from Stanford Network Analysis Platform (SNAP). Our evaluation shows a speedup of up to 2.62X (with an average of 1.73X) and 2.02X (with an average of 1.18X) over the highly vendor tuned SpMV implementation in Intel's Math Kernel Library (MKL) on single and multiple Intel Xeon cores respectively.

Original languageEnglish (US)
Title of host publicationCGO 2021 - Proceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization
EditorsJae W. Lee, Mary Lou Soffa, Ayal Zaks
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages211-221
Number of pages11
ISBN (Electronic)9781728186139
DOIs
StatePublished - Feb 27 2021
Event19th IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2021 - Virtual, Korea, Korea, Republic of
Duration: Feb 27 2021Mar 3 2021

Publication series

NameCGO 2021 - Proceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization

Conference

Conference19th IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2021
CountryKorea, Republic of
CityVirtual, Korea
Period2/27/213/3/21

Bibliographical note

Publisher Copyright:
© 2021 IEEE.

Keywords

  • blocking schemes
  • data-movement
  • sparse matrix kernels
  • SpMV
  • vectorization
  • wide width SIMD vector register units

Fingerprint Dive into the research topics of 'Variable-Sized Blocks for Locality-Aware SpMV'. Together they form a unique fingerprint.

Cite this