Runtime Composition of Iterations for Fusing Loop-carried Sparse Dependence

Kazem Cheshmi, Michelle Strout, Maryam Mehri Dehnavi

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

Abstract

Dependence between iterations in sparse computations causes inefficient use of memory and computation resources. This paper proposes sparse fusion, a technique that generates efficient parallel code for the combination of two sparse matrix kernels, where at least one of the kernels has loop-carried dependencies. Existing implementations optimize individual sparse kernels separately. However, this approach leads to synchronization overheads and load imbalance due to the irregular dependence patterns of sparse kernels, as well as inefficient cache usage due to their irregular memory access patterns. Sparse fusion uses a novel inspection strategy and code transformation to generate parallel fused code optimized for data locality and load balance. Sparse fusion outperforms the best of unfused implementations using ParSy and MKL by an average of 4.2× and is faster than the best of fused implementations using existing scheduling algorithms, such as LBC, DAGP, and wavefront by an average of 4× for various kernel combinations.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2023
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9798400701092
DOIs
StatePublished - Nov 12 2023
Event2023 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2023 - Denver, United States
Duration: Nov 12 2023Nov 17 2023

Publication series

NameProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2023

Conference

Conference2023 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2023
Country/TerritoryUnited States
CityDenver
Period11/12/2311/17/23

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Runtime Composition of Iterations for Fusing Loop-carried Sparse Dependence'. Together they form a unique fingerprint.

Cite this