Sparsity-Specific Code Optimization using Expression Trees
OPEN ACCESS
Loading...
Author / Producer
Date
2022-10
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
41 (5)
Pages / Article No.
175
Publisher
Association for Computing Machinery
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Code optimisation; Sparse computation
Organisational unit
03911 - Sorkine Hornung, Olga / Sorkine Hornung, Olga
Notes
Funding
101003104 - Sustainable Algorithmic Modeling of Personalized Garments (EC)