A unified sparse matrix data format for modern processors with wide SIMD units
A unified sparse matrix data format for modern processors with wide SIMD units
复制标题
适用于具有宽 SIMD 单元的现代处理器的统一稀疏矩阵数据格式
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
A. Bishop
中科院分区：
文献类型：
--
作者：
Moritz Kreutzer;G. Hager;G. Wellein;H. Fehske;A. Bishop
稀疏矩阵向量乘法（spMVM）是许多数值算法中最耗时的核心，在所有现代处理器和加速器架构上都得到了广泛的研究。然而，最佳稀疏矩阵数据存储格式是高度硬件特定的，这可能成为使用异构系统时的障碍。此外，目前还不清楚如何在当前多核和众核处理器中最有效地使用宽单指令多数据（SIMD）单元，如果矩阵的稀疏模式中没有结构。我们建议SELL-C-σ，切片ELLPACK的变体，作为一种SIMD友好的数据格式，它结合了通用图形处理单元（GPGPU）和矢量计算机编程的长期思想。我们讨论了SELL-C-σ与压缩行存储（CRS）和ELLPACK等已建立的格式相比的优势，并展示了其在各种硬件平台（英特尔桑迪桥、英特尔至强融核和Nvidia Tesla K20）上的适用性，用于不同应用领域的各种测试矩阵。使用适当的性能模型，我们深入了解SELL-C-σ spMVM内核的数据传输特性。SELL-C-σ有两个调优参数，研究了它们在测试矩阵范围内的性能影响，并提出了合理的选择。这导致了一种独立于硬件的（“全捕获”）稀疏矩阵格式，其对于跨所有硬件平台的所有测试矩阵实现了非常高的效率。
Sparse matrix-vector multiplication (spMVM) is the most time-consuming kernel in many numerical algorithms and has been studied extensively on all modern processor and accelerator architectures. However, the optimal sparse matrix data storage format is highly hardware-specific, which could become an obstacle when using heterogeneous systems. Also, it is as yet unclear how the wide single instruction multiple data (SIMD) units in current multiand many-core processors should be used most efficiently if there is no structure in the sparsity pattern of the matrix. We suggest SELL-C-σ, a variant of Sliced ELLPACK, as a SIMD-friendly data format which combines long-standing ideas from General Purpose Graphics Processing Units (GPGPUs) and vector computer programming. We discuss the advantages of SELL-C-σ compared to established formats like Compressed Row Storage (CRS) and ELLPACK and show its suitability on a variety of hardware platforms (Intel Sandy Bridge, Intel Xeon Phi and Nvidia Tesla K20) for a wide range of test matrices from different application areas. Using appropriate performance models we develop deep insight into the data transfer properties of the SELL-C-σ spMVM kernel. SELL-C-σ comes with two tuning parameters whose performance impact across the range of test matrices is studied and for which reasonable choices are proposed. This leads to a hardware-independent (“catch-all”) sparse matrix format, which achieves very high efficiency for all test matrices across all hardware platforms.