TY - JOUR
T1 - EGGS
T2 - Sparsity-Specific Code Generation
AU - Tang, Xuan
AU - Schneider, Teseo
AU - Kamil, Shoaib
AU - Panda, Aurojit
AU - Li, Jinyang
AU - Panozzo, Daniele
N1 - Funding Information:
This work was supported in part through the NYU IT High Performance Computing resources, services, and staff expertise. This work was partially supported by the NSF CAREER award 1652515, the NSF grants IIS‐1320635, OAC‐1835712, OIA‐1937043, CHS‐1908767, CHS‐1901091, CNS‐1816717, a gift from Adobe Research, a gift from nTopology, a gift from VMware, a gift from NVIDIA, and a gift from Advanced Micro Devices, Inc.
Funding Information:
This work was supported in part through the NYU IT High Performance Computing resources, services, and staff expertise. This work was partially supported by the NSF CAREER award 1652515, the NSF grants IIS-1320635, OAC-1835712, OIA-1937043, CHS-1908767, CHS-1901091, CNS-1816717, a gift from Adobe Research, a gift from nTopology, a gift from VMware, a gift from NVIDIA, and a gift from Advanced Micro Devices, Inc.
Publisher Copyright:
© 2020 The Author(s) Computer Graphics Forum © 2020 The Eurographics Association and John Wiley & Sons Ltd. Published by John Wiley & Sons Ltd.
PY - 2020/8/1
Y1 - 2020/8/1
N2 - Sparse matrix computations are among the most important computational patterns, commonly used in geometry processing, physical simulation, graph algorithms, and other situations where sparse data arises. In many cases, the structure of a sparse matrix is known a priori, but the values may change or depend on inputs to the algorithm. We propose a new methodology for compile-time specialization of algorithms relying on mixing sparse and dense linear algebra operations, using an extension to the widely-used open source Eigen package. In contrast to library approaches optimizing individual building blocks of a computation (such as sparse matrix product), we generate reusable sparsity-specific implementations for a given algorithm, utilizing vector intrinsics and reducing unnecessary scanning through matrix structures. We demonstrate the effectiveness of our technique on a benchmark of artificial expressions to quantitatively evaluate the benefit of our approach over the state-of-the-art library Intel MKL. To further demonstrate the practical applicability of our technique we show that our technique can improve performance, with minimal code changes, for mesh smoothing, mesh parametrization, volumetric deformation, optical flow, and computation of the Laplace operator.
AB - Sparse matrix computations are among the most important computational patterns, commonly used in geometry processing, physical simulation, graph algorithms, and other situations where sparse data arises. In many cases, the structure of a sparse matrix is known a priori, but the values may change or depend on inputs to the algorithm. We propose a new methodology for compile-time specialization of algorithms relying on mixing sparse and dense linear algebra operations, using an extension to the widely-used open source Eigen package. In contrast to library approaches optimizing individual building blocks of a computation (such as sparse matrix product), we generate reusable sparsity-specific implementations for a given algorithm, utilizing vector intrinsics and reducing unnecessary scanning through matrix structures. We demonstrate the effectiveness of our technique on a benchmark of artificial expressions to quantitatively evaluate the benefit of our approach over the state-of-the-art library Intel MKL. To further demonstrate the practical applicability of our technique we show that our technique can improve performance, with minimal code changes, for mesh smoothing, mesh parametrization, volumetric deformation, optical flow, and computation of the Laplace operator.
UR - http://www.scopus.com/inward/record.url?scp=85089364777&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089364777&partnerID=8YFLogxK
U2 - 10.1111/cgf.14080
DO - 10.1111/cgf.14080
M3 - Article
AN - SCOPUS:85089364777
VL - 39
SP - 209
EP - 219
JO - Computer Graphics Forum
JF - Computer Graphics Forum
SN - 0167-7055
IS - 5
ER -