多GPU异构平台的SpMV技巧

SpMV内核因为在内存访问和控制流方面的不规则性导致其优化是一项非常具有挑战性的任务。随着多核CPU和GPU的出现，已有较多针对这些挑战的研究工作和技术，如第2章中提到的不同稀疏格式（COO、CSR、ELL、HYB、块划分的格式等）。但是，大多数现有的研究仅针对一种类型的处理器，主要是多核CPU或GPU，尚未探索将多个处理单元组成的计算平台混合使用的潜力。在异构平台上，只有少数研究工作针对不同处理单元上稀疏矩阵划分的问题给出了解决方案，从而提高其SpMV内核的性能。目前存在多种稀疏格式，而且其性能既取决于矩阵的稀疏特性，又与不同的硬件特性相关，从而使得这个问题更具挑战性。因此，在异构平台上，最佳性能的实现不仅取决于如何在不同处理器之间对输入稀疏矩阵进行划分，也取决于在每个划分上使用哪种稀疏格式。对于大的稀疏矩阵，解空间（所有可能的划分方案的空间）非常大，因此寻找最佳划分方案是一个巨大的挑战。Yang等人研究了稀疏矩阵的几种划分方案（基于行的数量、基于非零元的数量以及基于子矩阵的块）。Yang等人提出的解决方案是基于混合稀疏格式HYB（ELL/COO），其中稀疏矩阵分为两部分，相对“稠密”的部分将在GPU上使用ELL（或DIA）格式计算，相对“稀疏”的部分使用COO格式在CPU上计算。将输入的稀疏矩阵划分为两个子矩阵，但此策略仅探索了所有可能划分方案中的一小部分。而且，它主要是为具有一个CPU和一个GPU的系统而开发的，不易扩展以处理两个以上不同处理器（例如一个CPU和两个或多个GPU）的情况。

本节对CPU-GPU异构平台上的稀疏矩阵划分问题进行了精细的分析，同时提出了一种新的基于异构平台的SpMV的计算方法。在本节的解决方案中，对稀疏矩阵按行进行划分，并使用基于机器学习的性能模型来预测每个处理器（系统中可用的CPU和GPU）上每个子矩阵使用不同稀疏格式编码时的SpMV内核的性能。然后，通过应用min-min策略（一种广泛应用于不同处理单元上不相关任务调度的策略）找到子矩阵在可用CPU和GPU上的最佳映射。本节考虑了四种常用的稀疏格式：COO、CSR、ELL和HYB。在GPU上，使用了基于CUDA的开源CUSP库中的实现。在CPU上，使用了英特尔MKL库中基于COO和CSR格式的SpMV内核的实现。鉴于多核CPU和GPU硬件的日益复杂，本节使用了基于机器学习的SpMV内核在不同稀疏格式下的性能模型。这些模型仅基于输入稀疏矩阵的易于计算的稀疏特征，使用支持向量回归算法在SuiteSparse矩阵集中的大量真实稀疏矩阵上进行了训练。为了同时在不同的CPU和GPU上进行计算，本节使用了基于OpenMP的编程模型，其中许多CPU线程专用于控制GPU，其他线程则参与计算工作。本节在两台不同的机器上，使用大量真实非结构化稀疏矩阵所得到的实验结果表明，与仅使用单个CPU或仅使用单个GPU相比，本节的解决方案实现了显著的加速，且获得了比Yang等人提出的基于HYB的解决方案更好的性能。(www.xing528.com)