Taichi: A Language for High-Performance Numerical Simulation and Differentiable Programming on Sparse Data Structures

Abstract:
3D volumetric data are often spatially sparse. To exploit such sparsity, people have developed hierarchical sparse voxel data structures such as SPGrid and VDB. However, developing and using these high-performance sparse data structures is challenging, due to the intrinsic data structure complexity and overhead. We propose Taichi, a new data-oriented programming language for efficiently authoring, accessing, and maintaining such data structures. The language offers a high-level, data structure-agnostic interface for writing computation code. The user independently specifies the data structure. We provide several elementary components with different sparsity properties that can be arbitrarily composed to create a wide range of multi-level sparse data structures. This decoupling of data structures from computation makes it easy to experiment with different data structures without changing computation code, and allows users to write computation as if they are working with a dense array. Our compiler then uses the semantics of the data structure and index analysis to automatically optimize for locality, remove redundant operations for coherent accesses, maintain sparsity and memory allocations, and generate efficient parallel and vectorized instructions for CPUs and GPUs. With 1/10th as many lines of code, we achieve 4.55× higher performance on average, compared to hand-optimized reference implementations. We have also developed a differentiable programming extension to this language.

Bio:
Yuanming Hu is a third-year Ph.D. student at MIT CSAIL with Fredo Durand and Bill Freeman. His research interests are compilers, high-performance computing, physical simulation, and computational photography. He designed and implemented the Taichi programming language for spatially sparse visual computing (http://taichi.graphics/me/).