ParSy: Inspection and Transformation of Sparse Matrix Computations for Parallelism

Authors: Kazem Cheshmi (University of Toronto), Shoaib Kamil (Adobe Research), Michelle Mills Strout (University of Arizona), Maryam Mehri Dehnavi (University of Toronto)

Abstract: In this work, we describe ParSy, a framework that uses a novel inspection strategy along with a simple code transformation to optimize parallel sparse algorithms for shared memory processors. Unlike existing approaches that can suffer from load imbalance and excessive synchronization, ParSy uses a novel task coarsening strategy to create well-balanced tasks that can execute in parallel, while maintaining locality of memory accesses. Code using the ParSy inspector and transformation outperforms existing highly-optimized sparse matrix algorithms such as Cholesky factorization on multi-core processors with speedups of 2.8× and 3.1× over the MKL Pardiso and PaStiX libraries respectively.


Presentation: file


Back to Technical Papers Archive Listing