Taichi: A Language for High-Performance Computation on Spatially Sparse Data Structures
Taichi: A Language for High-Performance Computation on Spatially Sparse Data Structures
复制标题
DOI：
10.1145/3355089.3356506
复制
发表时间：
2019-11-01
影响因子：
6.2
通讯作者：
Durand, Fredo
中科院分区：
文献类型：
--
作者：
Hu, Yuanming;Li, Tzu-Mao;Durand, Fredo
三维视觉计算数据通常是空间稀疏的。为了利用这种稀疏性，人们开发了分层稀疏数据结构，如多层稀疏体素网格、粒子和3D哈希表。然而，由于其固有的复杂性和开销，开发和使用这些高性能稀疏数据结构是具有挑战性的。我们提出了一种新的面向数据的编程语言太极，用于有效地创建、访问和维护这些数据结构。该语言为编写计算代码提供了一个高级的、与数据结构无关的接口。用户独立指定数据结构。我们提供了几个具有不同稀疏性属性的基本组件，可以任意组合以创建大范围的多层次稀疏数据结构。这种数据结构与计算的解耦使得在不改变计算代码的情况下很容易实验不同的数据结构，并允许用户编写计算，就好像他们正在处理一个密集的数组一样。然后，我们的编译器使用数据结构的语义和索引分析来自动优化局部性，为连贯访问删除冗余操作，维护稀疏性和内存分配，并为cpu和gpu生成有效的并行和矢量化指令。我们的方法在常见的计算内核（如模板应用程序、邻居查找和粒子散射）上产生了具有竞争力的性能。我们通过实现模拟、渲染和视觉任务来展示我们的语言，包括物质点法模拟、有限元分析、用于压力投影的多网格泊松求解器、体积路径跟踪和稀疏网格上的3D卷积。我们的计算-数据结构解耦使我们能够快速试验不同的数据安排，并开发针对特定计算任务量身定制的高性能数据结构。与手工优化的参考实现相比，我们只使用了1/10的代码行，平均性能提高了4.55倍。
3D visual computing data are often spatially sparse. To exploit such sparsity, people have developed hierarchical sparse data structures, such as multilevel sparse voxel grids, particles, and 3D hash tables. However, developing and using these high-performance sparse data structures is challenging, due to their intrinsic 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.Our approach yields competitive performance on common computational kernels such as stencil applications, neighbor lookups, and particle scattering. We demonstrate our language by implementing simulation, rendering, and vision tasks including a material point method simulation, finite element analysis, a multigrid Poisson solver for pressure projection, volumetric path tracing, and 3D convolution on sparse grids. Our computation-data structure decoupling allows us to quickly experiment with different data arrangements, and to develop high-performance data structures tailored for specific computational tasks. With 1/10 th as many lines of code, we achieve 4.55x higher performance on average, compared to hand-optimized reference implementations.