Generating Piecewise-Regular Code from Irregular Structures
Irregular data structures, as exemplified with sparse matrices, have proved to be essential in modern computing. Numerous sparse formats have been investigated to improve the overall performance of Sparse Matrix-Vector multiply (SpMV). But in this work we propose instead to take a fundamentally different approach: to automatically build sets of regular sub-computations by mining for regular sub-regions in the irregular data structure.
Our approach leads to code that is specialized to the sparsity structure of the input matrix, but which does not need anymore any indirection array, thereby improving SIMD vectorizability. We particularly focus on small sparse structures (below 10M nonzeros), and demonstrate substantial performance improvements and compaction capabilities compared to a classical CSR implementation and Intel MKL IE's SpMV implementation, evaluating on 200+ different matrices from the SuiteSparse repository.
Conference DayTue 25 JunDisplayed time zone: Tijuana, Baja California change
10:00 - 11:00
|Sparse Computation Data Dependence Simplification for Efficient Compiler-Generated Inspectors|
PLDI Research Papers
Mahdi Soltan MohammadiUniversity of Arizona, Eddie C. DavisBoise State University, USA, Mary HallUniversity of Utah, Maryam Mehri DehnaviUniversity of Toronto, Payal NandyUniversity of Utah, USA, Catherine R. M. OlschanowskyBoise State University, USA, Anand VenkatUniversity of Utah, Tomofumi Yuki, Kazem CheshmiUniversity of Toronto, Michelle StroutUniversity of ArizonaLink to publication DOI Pre-print Media Attached
|Modular Divide-and-Conquer Parallelization of Nested Loops|
PLDI Research PapersMedia Attached
|Generating Piecewise-Regular Code from Irregular Structures|
PLDI Research Papers
Travis AugustineColorado State University, USA, Janarthanan SarmaColorado State University, USA, Louis-Noël PouchetColorado State University, Gabriel RodríguezUniversidade da Coruña, SpainLink to publication DOI