Automating Wavefront Parallelization for Sparse Matrix Codes
SessionCompilation for Enhanced Parallelism
Session ChairHironori Kasahara
Event Type
Paper
Intermediate
Performance
Programming Systems
TimeWednesday, November 16th2:30pm - 3pm
Location355-D
DescriptionThis paper presents a compiler and runtime framework for parallelizing sparse matrix computations that have loop-carried dependences. Our approach automatically generates a runtime inspector to collect data dependence information and achieves wavefront parallelization of the computation, where iterations within a wavefront execute in parallel, and synchronization is required across wavefronts. A key contribution of this paper involves dependence simplification, which reduces the time and space overhead of the inspector. This is implemented within a polyhedral compiler framework, extended for sparse matrix codes. Results demonstrate the feasibility of using automatically-generated inspectors and executors to optimize ILU factorization and symmetric Gauss-Seidel relaxations, which are part of the Preconditioned Conjugate Gradient (PCG) computation. Our implementation achieves a median speedup of 2.97x and 2.82x over the reference sequential PCG implementation and PCG parallelized with the Intel Math Kernel Library (MKL) respectively and are within 7% of the median performance of manually tuned code.
