Generating piecewise-regular code from irregular structures
Generating piecewise-regular code from irregular structures
复制标题
DOI：
10.1145/3314221.3314615
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
T. Augustine;Janarthanan Sarma;L. Pouchet;Gabriel Rodríguez
中科院分区：
文献类型：
--
作者：
T. Augustine;Janarthanan Sarma;L. Pouchet;Gabriel Rodríguez
事实证明，用稀疏矩阵示例的不规则数据结构在现代计算中至关重要。已经研究了许多稀疏格式，以提高稀疏基质 - 矢量倍数（SPMV）的整体性能。但是在这项工作中，我们建议采用一种根本不同的方法：通过开采不规则数据结构中的常规子区域来自动构建常规子计算集。我们的方法导致了专门针对输入矩阵的稀疏结构的代码，但不再需要任何间接数组，从而改善了SIMD矢量化。我们特别关注小稀疏结构（低于1000万何零齐率），并且与经典的CSR实施和Intel MKL IE的SPMV实施相比，表现出了实质性的改进和压实功能，并评估了来自Suitesparse Reposority的200多个不同矩阵。
Irregular data structures, as exemplified with sparse matrices, have proved to be essential in modern computing. Numerous sparse formats have been investigated to improve the overall performance of Sparse Matrix-Vector multiply (SpMV). But in this work we propose instead to take a fundamentally different approach: to automatically build sets of regular sub-computations by mining for regular sub-regions in the irregular data structure. Our approach leads to code that is specialized to the sparsity structure of the input matrix, but which does not need anymore any indirection array, thereby improving SIMD vectorizability. We particularly focus on small sparse structures (below 10M nonzeros), and demonstrate substantial performance improvements and compaction capabilities compared to a classical CSR implementation and Intel MKL IE's SpMV implementation, evaluating on 200+ different matrices from the SuiteSparse repository.