Sparse computation data dependence simplification for efficient compiler-generated inspectors

Mahdi Soltan Mohammadi, Eddie C. Davis, Payal Nandy, Tomofumi Yuki, Mary Hall, Catherine Olschanowsky, Michelle Mills Strout, Kazem Cheshmi, Maryam Mehri Dehnavi, Anand Venkat

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

11 Scopus citations

Abstract

This paper presents a combined compile-time and runtime loop-carried dependence analysis of sparse matrix codes and evaluates its performance in the context of wavefront paral-lellism. Sparse computations incorporate indirect memory accesses such as x[col[j]] whose memory locations cannot be determined until runtime. The key contributions of this paper are two compile-time techniques for significantly reducing the overhead of runtime dependence testing: (1) identifying new equality constraints that result in more efficient runtime inspectors, and (2) identifying subset relations between dependence constraints such that one dependence test subsumes another one that is therefore eliminated. New equality constraints discovery is enabled by taking advantage of domain-specific knowledge about index arrays, such as col[j]. These simplifications lead to automatically-generated inspectors that make it practical to parallelize such computations. We analyze our simplification methods for a collection of seven sparse computations. The evaluation shows our methods reduce the complexity of the runtime inspectors significantly. Experimental results for a collection of five large matrices show parallel speedups ranging from 2x to more than 8x running on a 8-core CPU.

Original languageEnglish (US)
Title of host publicationPLDI 2019 - Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation
EditorsKathryn S. McKinley, Kathleen Fisher
PublisherAssociation for Computing Machinery
Pages594-609
Number of pages16
ISBN (Electronic)9781450367127
DOIs
StatePublished - Jun 8 2019
Externally publishedYes
Event40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2019 - Phoenix, United States
Duration: Jun 22 2019Jun 26 2019

Publication series

NameProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Conference

Conference40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2019
Country/TerritoryUnited States
CityPhoenix
Period6/22/196/26/19

Keywords

  • Data dependence simplification
  • Dependence analysis
  • Inspector-executor strategies
  • Presburger arithmetic with uninterpreted functions
  • SMT solvers
  • Sparse matrices

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Sparse computation data dependence simplification for efficient compiler-generated inspectors'. Together they form a unique fingerprint.

Cite this