Sparsity-Specific Code Optimization using Expression Trees
Open Access
- 13 May 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 41 (5) , 1-19
Abstract
We introduce a code generator that converts unoptimized C++ code operating on sparse data into vectorized and parallel CPU or GPU kernels. Our approach unrolls the computation into a massive expression graph, performs redundant expression elimination, grouping, and then generates an architecture-specific kernel to solve the same problem, assuming that the sparsity pattern is fixed, which is a common scenario in many applications in computer graphics and scientific computing. We show that our approach scales to large problems and can achieve speedups of two orders of magnitude on CPUs and three orders of magnitude on GPUs, compared to a set of manually optimized CPU baselines. To demonstrate the practical applicability of our approach, we employ it to optimize popular algorithms with applications to physical simulation and interactive mesh deformation.Keywords
All Related Versions
Funding Information
- NSF CAREER (1652515)
- NSF (OAC-1835712, OIA-1937043, CHS-1908767, CHS-1901091)
- NSERC (DGECR-2021-00461 and RGPIN-2021-03707)
- European Research Council (101003104)
This publication has 33 references indexed in Scilit:
- Loop and data transformations for sparse matrix code2015
- BLIS: A Framework for Rapidly Instantiating BLAS FunctionalityACM Transactions on Mathematical Software, 2015
- Halide2013
- Decoupling algorithms from schedules for easy optimization of image processing pipelinesACM Transactions on Graphics, 2012
- Anatomy of high-performance matrix multiplicationACM Transactions on Mathematical Software, 2008
- OSKI: A library of automatically tuned sparse matrix kernelsJournal of Physics: Conference Series, 2005
- Large steps in cloth simulation1998
- On automatic data structure selection and code generation for sparse computations1994
- Uniform techniques for loop optimization1991
- Array expansion1988