Sparsity-Specific Code Optimization using Expression Trees

Philipp Herholz, Xuan Tang, Teseo Schneider, Shoaib Kamil, Daniele Panozzo, Olga Sorkine-Hornung

TL;DR

This paper introduces a novel code generator that transforms unoptimized C++ code dealing with sparse data into highly efficient, vectorized, and parallel CPU/GPU kernels. By analyzing and optimizing expression trees derived from the code, they achieve significant speedups (up to 2-3 orders of magnitude) for applications in computer graphics and scientific computing, outperforming manual optimizations and existing methods like EGGS.

What Problem Does This Paper Address?

Optimizing numerical code, especially for sparse data structures, is a significant challenge. While dense matrix operations benefit from highly optimized libraries like BLAS, sparse matrix operations are more complex and often lack readily available, general-purpose optimization tools. Existing sparse matrix libraries have limitations, often supporting only specific operations or formats, and struggle with compound operations or implicit transpositions. Furthermore, manually optimizing sparse code for modern parallel architectures (CPUs and GPUs) is time-consuming and requires deep expertise. This paper addresses the need for an automated approach to generate efficient, architecture-specific code for complex sparse expressions, particularly when the sparsity pattern is fixed.

Methods

The core of the approach is symbolic execution of C++ code. Instead of directly executing numerical operations, the system uses a custom Symbolic type that overloads operators to build expression trees. These trees represent the computation graph. The key novelties lie in how these trees are processed and optimized:

  • Expression Decomposition: The system breaks down large expression trees into smaller, reusable sub-expressions (both locally within a kernel and globally across different kernels). This is crucial for handling complex computations and reducing redundant work.
  • Expression Grouping: Structurally equivalent expression trees are grouped together. This allows for the generation of a single, optimized template kernel that can evaluate all expressions within a group by simply substituting the correct leaf values (variables and constants).
  • Leaf Harvesting: For each group, the system identifies and stores all unique leaf variables and constants in a table. This information is vital for generating efficient code.
  • Expression Simplification: A set of algebraic simplification rules are applied to the expression trees to reduce their complexity.
  • Code Generation: Finally, the system generates architecture-specific C++ or CUDA code. This includes optimizing memory access patterns (e.g., for coalesced access on GPUs), vectorization (using compiler intrinsics and pragmas), and parallelization (e.g., using OpenMP or TBB).
  • Symbolic Differentiation: The expression tree representation naturally supports automatic differentiation, allowing the generation of code for gradients and Hessians.

Datasets

The paper does not explicitly mention training datasets. Instead, it focuses on optimizing existing C++ codebases for various applications. The "datasets" in this context are the input data structures and sparsity patterns used in the evaluated algorithms, such as mesh data for geometry processing and physical simulation.

Key Insights and Ideas

  • Expression Trees as a Universal Representation: Representing computations as expression trees provides a powerful abstraction that allows for sophisticated analysis and optimization, independent of the original code's structure.
  • Fixed Sparsity Pattern is Key: The assumption of a fixed sparsity pattern is critical. It enables the system to pre-analyze and generate highly specialized kernels, which would be impossible with dynamic sparsity.
  • Decomposition is Crucial for Complexity: Breaking down complex expressions into smaller, reusable parts (both locally and globally) is essential for achieving significant performance gains, especially for computations that would otherwise lead to an explosion of kernels or redundant calculations.
  • Leveraging Compiler Optimizations: The system doesn't reinvent low-level optimizations but rather generates code that allows standard C++ compilers to effectively apply vectorization and parallelization.
  • Symbolic Differentiation is a Natural Extension: The expression tree representation makes it straightforward to implement automatic differentiation, which is highly valuable for many scientific computing tasks.

Key Results

The paper demonstrates substantial performance improvements across various applications:

  • Speedups: Up to two orders of magnitude on CPUs and three orders of magnitude on GPUs compared to manually optimized baselines.
  • Sparse Matrix Operations: Outperforms EGGS by a significant margin, especially for complex expressions, achieving up to a 6x speedup (100x with 16 threads) for a sparse matrix power calculation.
  • GPU Performance: Achieves competitive or superior performance compared to dedicated GPU libraries like rocSPARSE, while being more general.
  • Automatic Differentiation: Generated code for Hessians and gradients is competitive with hand-optimized implementations and significantly faster than other automatic differentiation techniques.
  • Code Generation Efficiency: The generated code is highly optimized for specific architectures, leading to substantial speedups in areas like cloth simulation and volumetric Laplacian construction.

Limitations and Future Work

  • Input Code Requirements: The input C++ code needs to be templated to work with the Symbolic type. Automatically handling non-templated code would improve usability.
  • Compilation Time and Memory: The current compilation process is serial and can be time- and memory-intensive, especially for large problems. Optimizing the pipeline and compressing expression trees are suggested improvements.
  • Manual Annotation: Explicitly tagging dense blocks for evaluation within a single kernel can be beneficial but requires manual effort. Automating this detection is a future direction.
  • Targeting Heterogeneous Systems: Extending the approach to target multiple processors and accelerators, and generating optimal execution policies for distributed systems, is a significant area for future work.
  • Integration with Compilers: While the current approach generates C++ code, integrating with compiler infrastructures like LLVM could offer further optimization opportunities.

Summary updated

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.
BibTeX
@article{herholz2022sparsity,
  author = {Philipp Herholz and Xuan Tang and Teseo Schneider and Shoaib Kamil and Daniele Panozzo and Olga Sorkine-Hornung},
  title = {{Sparsity-Specific Code Optimization using Expression Trees}},
  journal = {ACM Trans. Graphics},
  year = {2022},
  url = {https://openreview.net/forum?id=hDkoejv3Qu},
}
Figure