Code Synthesis for Sparse Tensor Format Conversion and Optimization

Tobi Popoola, Tuowen Zhao, Aaron St. George, Kalyan Bhetwal, Michelle Mills Strout, Mary Hall, Catherine Olschanowsky

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

1 Scopus citations

Abstract

Many scientific applications compute using sparse data and store that data in a variety of sparse formats because each format has unique space and performance benefits. Optimizing applications that use sparse data involves translating the sparse data into the chosen format and transforming the computation to iterate over that format. This paper presents a formal definition of sparse tensor formats and an automated approach to synthesize the transformation between formats. This approach is unique in that it supports ordering constraints not supported by other approaches and synthesizes the transformation code in a high-level intermediate representation suitable for applying composable transformations such as loop fusion and temporary storage reduction. We demonstrate that the synthesized code for COO to CSR with optimizations is 2.85x faster than TACO, Intel MKL, and SPARSKIT while the more complex COO to DIA is 1.4x slower than TACO but faster than SPARSKIT and Intel MKL using the geometric average of execution time.

Original languageEnglish (US)
Title of host publicationCGO 2023 - Proceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization
EditorsChristophe Dubach, Derek Bruening, Ben Hardekopf
PublisherAssociation for Computing Machinery, Inc
Pages28-40
Number of pages13
ISBN (Electronic)9798400701016
DOIs
StatePublished - Feb 17 2023
Event21st ACM/IEEE International Symposium on Code Generation and Optimization, CGO 2023 - Montreal, Canada
Duration: Feb 25 2023Mar 1 2023

Publication series

NameCGO 2023 - Proceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization

Conference

Conference21st ACM/IEEE International Symposium on Code Generation and Optimization, CGO 2023
Country/TerritoryCanada
CityMontreal
Period2/25/233/1/23

Keywords

  • Code synthesis
  • Index array properties
  • Polyhedral compilation
  • Sparse Format Conversion
  • Sparser Format Descriptors
  • Transformations
  • Uninterpreted functions

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Hardware and Architecture
  • Software
  • Applied Mathematics
  • Control and Optimization

Fingerprint

Dive into the research topics of 'Code Synthesis for Sparse Tensor Format Conversion and Optimization'. Together they form a unique fingerprint.

Cite this