多核平台稀疏矩阵计算研究及哈希表算法

对多核平台的研究主要集中在两个问题：内存管理和负载均衡。

1.基于CPU的优化

内存管理。为了利用数据局部性，Patwary等人通过使用中的稠密数组来优化传统的串行SpGEMM算法。为了减少SpGEMM中的重新分配内存的时间开销，Nagasaka等人计算了每个线程所需的内存量，并在Intel KNL处理器上独立地为每个线程分配了相应大小的私有内存。另外，他们还实现了一种基于哈希表的SpGEMM算法，该算法面向共享内存的多核处理器平台。对于具有适当的大内存和线程数的体系结构，Elliott等人在中提出了Gustavson’s SpGEMM算法的单路OpenMP变体。他们对右侧矩阵的行进行划分，然后在线程的局部值数组和列数组上执行Gustavson算法，同时在局部存储中完成行数组的构建。为了减少内存分配的开销，他们使用页面对齐的内存分配，同时分开监测已用大小和容量。为了实现适用于许多大规模应用的高效的SpGEMM，Chen等人在神威·太湖之光超级计算机上提出了基于COO、CSR、ELL和CSC格式的改进版SpGEMM内核。在该方案中，他们使用DMA（直接存储器访问）传输来访问主存储器中的数据，从而用于在CPE核心上的计算。毫无疑问，使用DMA连续传输数据的性能要远远优于离散存储器访问。为了研究不同层次的存储器架构与SpGEMM内核性能之间的关系，Deveci等人为Intel KNL设计了不同的基于分块的SpGEMM算法，其内存子系统具有相近的延迟。他们发现子系统的性能差异随着SpGEMM的时间和空间局部性的增加而减小。考虑到A矩阵的稀疏结构会造成对B矩阵访问的不规则性，他们在KNL上提出了一种存储矩阵B的数据放置方法。Deveci等人根据问题的特征，采用启发式的方法选择最佳内核参数，展示了通过权衡访存和计算成本之后，矩阵划分方案和数据结构的选择结果。为了满足大量线程的内核调用和服务请求，提前分配和初始化一个内存池。当一个线程发出请求时，便将一块内存分给该线程，直到该线程将该块内存放回内存池，它才会被释放。内存池的参数是随体系结构的不同而变化的，其分块的数量取决于目标设备的可用并发率。

负载均衡。在Patwary等人的实验中，矩阵被划分为较小的分块，然后对所有的分块采用动态的负载均衡。实验表明，减小每个分块的大小，能够在具有两个Intel Xeon E5−2697 V3处理器的系统上实现更好的负载平衡。他们发现当分块的总数是线程数的6～10倍时，SpGEMM的性能更优。为了减少动态调度的开销，他们在Intel KNL上的SpGEMM实现中使用了静态调度。为了实现负载均衡，Chen等人提出了一种基于神威架构的三层划分方案。对于C=A×B的形式，左侧的稀疏矩阵A在第一层划分中被划分为多个子矩阵sub−A。SW260 + 10处理器中的每个核组执行sub−A和B的乘法。在第二层划分，B被划分为多个sub−B。核组中的每个CPE核心完成sub−A和sub−B的相乘。在第三层划分，为了满足每个CPE核心不超过64 KB的局部存储，sub−A和sub−B进一步被划分为几组。(www.xing528.com)

2.基于GPU的优化

内存管理。高效并行的SpGEMM算法必须考虑到其不规则性，比如结果矩阵非零元的未知性，Liu等人使用混合的方法来指导结果矩阵的内存预分配，该方法可以减少大量的全局内存开销。此外，该方法有效利用了非常有限的片上缓冲存储器。为了充分利用GPU上的高速寄存器，Liu等人在中分别为不同的稀疏累加器设计了不同的寄存器感知的SpGEMM算法，这些稀疏累加器包括基于排序、基于归并和基于哈希的累加器。他们充分利用GPU寄存器来获取数据、完成计算和存储结果。Winter等人提出了一种基于块的自适应GPU SpGEMM方法（AC-pGEMM），以减少所有阶段的计算开销。他们执行基于块的ESC：显式扩展所有中间结果，对其进行排序并合并生成最终结果。通过局部任务分配，他们执行多次ESC迭代，充分利用局部内存资源，同时将临时结果保留在缓冲存储器中。为了实现大规模线程体系结构上的性能可移植性，Deveci等人引入了两个支持线程扩展的数据结构：一个多级哈希映射和一个内存池，设计了一种分层且内存高效的SpGEMM算法。考虑到NVIDIA GPU的内存子系统在带宽和延迟方面都存在显著差异，因此Deveci等人提出了两种不同的数据放置方法：一种是将A和C的划分保留在快速内存中，然后将B的划分流式传输到快速内存中；另一种是将B的划分保留在快速内存中，并将A和C的划分流式传输到快速内存中。选择哪种方法通常取决于输入矩阵的特征，为了在GPU上选择合适的内存池参数，Deveci等人适当高估并发性以高效地访问内存。如果GPU上的内存分配开销太大，他们会检查可用内存并减少分块的数量。

负载均衡。为了平衡SpGEMM在GPU上的工作负载，Liu等人提出了一种启发式方法，将结果矩阵的行分配给多个bins并使用不同系列的计算方法。他们首先申请了38个bins，并将它们分成5个bin组，然后根据非零元的数量将所有行分配给相应的bin，最后他们根据每个bin的大小为结果矩阵C中的非零项分配一个临时矩阵。由于前两个bin中的行仅需要少量计算，所以将其分配给CPU端完成。后续的bins需要更复杂的计算，所以交由GPU完成，从而实现更好的负载均衡。Winter等人均匀划分矩阵A的非零元，从而为每个线程块分配相同数量的非零元数。尽管来自A的访存需求是静态的，但是每个线程块的实际工作负载会根据生成的中间乘积而有所不同。尽管A矩阵非零元的静态划分不需要进行处理，但是第二阶段仍然需要将A中的每一个非零项与一行相关联。因此他们还采用并行的全局负载均衡：检查A的行指针并将所需的信息写入辅助数组。相比于枚举临时乘积，此步骤的成本可以忽略不计。