EGGS: Sparsity-Specific Code Generation

Xuan Tang, Teseo Schneider, Shoaib Kamil, Aurojit Panda, Jinyang Li, Daniele Panozzo

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)209-219
Number of pages11
JournalComputer Graphics Forum
Volume39
Issue number5
DOIs
StatePublished - Aug 1 2020

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'EGGS: Sparsity-Specific Code Generation'. Together they form a unique fingerprint.

Cite this