POSTER: Optimizing Sparse Computations Jointly

Kazem Cheshmi, Michelle Mills Strout, Maryam Mehri Dehnavi

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

Abstract

This work proposes a framework called FuSy that analyzes the data dependence graphs (DAGs) of two sparse kernels and creates an efficient schedule to execute the kernels in combination. Sparse kernels are frequently used in scientific codes and in machine learning algorithms and very often they are used in combination. Iterative linear system solvers are an example where kernels such as sparse triangular solver (SpTRSV) and sparse matrix-vector multiplication (SpMV) are called consecutively in each iteration of the solver. Prior approaches typically optimize these sparse kernels independently leading to high synchronization overheads and low locality. We propose an approach that analyzes the DAGs of two sparse kernels and then creates a new order of execution that enables running the two kernels efficiently in parallel. To investigate the efficiency of our approach, we compare it with the state-of-the-art MKL library for two kernel combinations, SpTRSV-SpMV and SpMV-SpTRSV which are commonly used in iterative solvers. Experimental results show that our approach is on average 2.6X and 1.8X faster than the MKL library for a set of matrices from the Suitesparse matrix repository.

Original languageEnglish (US)
Title of host publicationPPoPP 2022 - Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
PublisherAssociation for Computing Machinery
Pages459-460
Number of pages2
ISBN (Electronic)9781450392044
DOIs
StatePublished - Apr 2 2022
Externally publishedYes
Event27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2022 - Virtual, Online, Korea, Republic of
Duration: Apr 2 2022Apr 6 2022

Publication series

NameProceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP

Conference

Conference27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2022
Country/TerritoryKorea, Republic of
CityVirtual, Online
Period4/2/224/6/22

Keywords

  • loop fusion
  • loop-carried dependence
  • sparse matrix code

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'POSTER: Optimizing Sparse Computations Jointly'. Together they form a unique fingerprint.

Cite this