Generating Fast Sparse Matrix Vector Multiplication from a High Level Generic Functional IR

Federico Pizzuti, Michel Steuwer, Christophe Dubach

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

Abstract

Usage of high-level intermediate representations promises the generation of fast code from a high-level description, improving the productivity of developers while achieving the performance traditionally only reached with low-level programming approaches.

High-level IRs come in two flavors: 1) domain-specific IRs designed only for a specific application area; or 2) generic high-level IRs that can be used to generate high-performance code across many domains. Developing generic IRs is more challenging but offers the advantage of reusing a common compiler infrastructure across various applications.

In this paper, we extend a generic high-level IR to enable efficient computation with sparse data structures. Crucially, we encode sparse representation using reusable dense building blocks already present in the high-level IR. We use a form
of dependent types to model sparse matrices in CSR format by expressing the relationship between multiple dense arrays explicitly separately storing the length of rows, the column indices, and the non-zero values of the matrix.

We achieve high-performance compared to sparse low-level library code using our extended generic high-level code generator. On an Nvidia GPU, we outperform the highly tuned Nvidia cuSparse implementation of SpMV (Sparsematrix vector multiplication) multiplication across 28 sparse matrices of varying sparsity on average by 1.7×.
Original languageEnglish
Title of host publicationCC 2020: Proceedings of the 29th International Conference on Compiler Construction
PublisherACM Association for Computing Machinery
Pages85-95
Number of pages11
ISBN (Print)9781450371209
DOIs
Publication statusPublished - 22 Feb 2020
EventACM SIGPLAN 2020 International Conference on Compiler Construction - San Diego, United States
Duration: 22 Feb 202023 Feb 2020
Conference number: 29
https://conf.researchr.org/home/CC-2020

Conference

ConferenceACM SIGPLAN 2020 International Conference on Compiler Construction
Abbreviated titleCC 2020
Country/TerritoryUnited States
CitySan Diego
Period22/02/2023/02/20
Internet address

Keywords

  • Software and its engineering
  • Parallel programming languages
  • Compilers
  • Sparse Matrix
  • Code Generation
  • Dependent Types

Fingerprint

Dive into the research topics of 'Generating Fast Sparse Matrix Vector Multiplication from a High Level Generic Functional IR'. Together they form a unique fingerprint.

Cite this