Custom High-Performance Vector Code Generation for Data-Specific Sparse Computations
Custom High-Performance Vector Code Generation for Data-Specific Sparse Computations
复制标题
DOI：
10.1145/3559009.3569668
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Marcos Horro;L. Pouchet;Gabriel Rodríguez;J. Touriño
中科院分区：
文献类型：
--
作者：
Marcos Horro;L. Pouchet;Gabriel Rodríguez;J. Touriño
稀疏的计算，例如稀疏矩阵密集的矢量乘法，由于其不规则性和记忆力结合度，很难优化。已经提出了改善稀疏计算性能的解决方案，从基于硬件的基于聚会片段说明等软件，例如诸如概括和专用的稀疏格式之类的软件，以及用于不同硬件目标的专用执行程序。这些稀疏的计算通常是在仅读取的稀疏结构上执行的：虽然数据本身是可变的，但稀疏结构本身不会改变。实际上，诸如CSR之类的稀疏格式通常具有较高的成本来插入/删除表示中的非零元素。典型的用例是不要在相同的稀疏结构上重复计算过程中修改稀疏性。在这项工作中，我们利用了生成专门针对输入矩阵特定稀疏结构的专业执行程序的可能性。它创造了删除间接阵列并合成此类计算的常规，可矢量化的代码的机会。但是，与此同时，它引入了代码大小和指令生成以及有效的SIMD矢量化方面的挑战。我们提出了新颖的技术和广泛的实验结果，以有效地生成针对数据特定稀疏计算的SIMD矢量代码，并与Intel MKL（如Intel MKL）相比，研究了我们技术的适用性和性能方面的限制。
Sparse computations, such as sparse matrix-dense vector multiplication, are notoriously hard to optimize due to their irregularity and memory-boundedness. Solutions to improve the performance of sparse computations have been proposed, ranging from hardware-based such as gather-scatter instructions, to software ones such as generalized and dedicated sparse formats, used together with specialized executor programs for different hardware targets. These sparse computations are often performed on read-only sparse structures: while the data themselves are variable, the sparsity structure itself does not change. Indeed, sparse formats such as CSR have a typically high cost to insert/remove nonzero elements in the representation. The typical use case is to not modify the sparsity during possibly repeated computations on the same sparse structure. In this work, we exploit the possibility to generate a specialized executor program dedicated to the particular sparsity structure of an input matrix. It creates opportunities to remove indirection arrays and synthesize regular, vectorizable code for such computations. But, at the same time, it introduces challenges in code size and instruction generation, as well as efficient SIMD vectorization. We present novel techniques and extensive experimental results to efficiently generate SIMD vector code for data-specific sparse computations, and study the limits in terms of applicability and performance of our techniques compared to state-of-practice high-performance libraries like Intel MKL.