Sparsity-Specific Code Optimization using Expression Trees
Sparsity-Specific Code Optimization using Expression Trees
复制标题
DOI：
10.1145/3520484
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Philipp Herholz;Xuan Tang;T. Schneider;Shoaib Kamil;Daniele Panozzo;O. Sorkine-Hornung
中科院分区：
文献类型：
--
作者：
Philipp Herholz;Xuan Tang;T. Schneider;Shoaib Kamil;Daniele Panozzo;O. Sorkine-Hornung
我们介绍了一个代码生成器，它将在稀疏数据上操作的未优化的c++代码转换为矢量化和并行的CPU或GPU内核。我们的方法将计算展开到一个大规模的表达式图中，执行冗余表达式消除、分组，然后生成一个特定于体系结构的内核来解决相同的问题，假设稀疏性模式是固定的，这是计算机图形学和科学计算中的许多应用程序中的常见场景。我们表明，与一组手动优化的CPU基线相比，我们的方法可以扩展到大型问题，并且可以在CPU上实现两个数量级的速度，在gpu上实现三个数量级的速度。为了证明我们的方法的实际适用性，我们使用它来优化流行的算法，并应用于物理模拟和交互式网格变形。
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.