HDagg: Hybrid Aggregation of Loop-carried Dependence Iterations in Sparse Matrix Computations

Behrooz Zarebavani, Kazem Cheshmi, Bangtian Liu, Michelle Mills Strout, Maryam Mehri Dehnavi

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

3 Scopus citations

Abstract

This paper proposes a novel aggregation algorithm, called Hybrid DAG Aggregation (HDagg), that groups iterations of sparse matrix computations with loop carried dependence to improve their parallel execution on multicore processors. Prior approaches to optimize sparse matrix computations fail to provide an efficient balance between locality, load balance, and synchronization and are primarily optimized for codes with a tree-structure data dependence. HDagg is optimized for sparse matrix computations that their data dependence graphs (DAGs) do not have a tree structure, such as incomplete matrix factorization algorithms. It uses a hybrid approach to aggregate vertices and wavefronts in the DAG of a sparse computation to create well-balanced parallel workloads with good locality. Across three sparse kernels, triangular solver, incomplete Cholesky, and incomplete LU, HDagg outperforms existing sparse libraries such as MKL with an average speedup of 3.56× and is faster than state-of-the-art inspector-executor approaches that optimize sparse computations, i.e. DAGP, LBC, wavefront parallelism techniques, and SpMP by an average speedup of 3.87×, 3.41×, 1.95×, and 1.43× respectively.

Original languageEnglish (US)
Title of host publicationProceedings - 2022 IEEE 36th International Parallel and Distributed Processing Symposium, IPDPS 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1217-1227
Number of pages11
ISBN (Electronic)9781665481069
DOIs
StatePublished - 2022
Event36th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2022 - Virtual, Online, France
Duration: May 30 2022Jun 3 2022

Publication series

NameProceedings - 2022 IEEE 36th International Parallel and Distributed Processing Symposium, IPDPS 2022

Conference

Conference36th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2022
Country/TerritoryFrance
CityVirtual, Online
Period5/30/226/3/22

Keywords

  • Loop-carried Dependence
  • Parallelism
  • Sparse Matrix Computations

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'HDagg: Hybrid Aggregation of Loop-carried Dependence Iterations in Sparse Matrix Computations'. Together they form a unique fingerprint.

Cite this