论文部分内容阅读
随着计算机硬件的快速发展，体系结构变得越来越复杂。根据体系结构特点开发高性能数学库可以对应用开发人员屏蔽具体硬件细节。系统结构的多样性和更新速度无疑增加了数学库开发人员的工作量和难度。自适应性能优化技术可以根据具体硬件结构的特征，自适应地变换执行路径以选择最优实现。保证运行效率的同时，提高程序的移植性，因此被广泛应用到数学库开发中。
稀疏矩阵向量乘(SpMV，y=A×x)是科学计算中常用到的计算内核之一。传统基于CSR(Compressed Storage Row)存储的稀疏矩阵向量乘实现，其运行效率通常低于硬件浮点运算峰值的10％。首先，我们分析影响稀疏矩阵向量乘的因素，并通过实验进行验证。然后，根据不同矩阵非零元的分布特点，进行相应的优化：
●针对稀疏矩阵向量乘过程中x元素被频繁换入换出，提出cache分块算法以及分块大小确定方案，实现x元素被换出前尽可能被重用；
●针对对角线稀疏矩阵，提出了CRSD(Compressed Row Segment withDiagonal-pattern)存储结构，借助“应用特定对角线格式”对稀疏矩阵相乘进行应用特定的优化。
●针对矩阵中非零元分布主要集中在稠密子块的特点，提出了CSRC(Compressed Sparse Row format with Column-unit)存储结构，通过压缩算法减少索引值容量，并借助列单元重用x元素;
在具体稀疏矩阵向量乘实现过程中，采用自适应性能优化策略，提高程序移植性及运行速率。尤其CRSD存储格式根据应用矩阵特点自动生成相应的稀疏矩阵向量乘实现。测试结果表明，与现有优化策略相比，我们所提出的方法有很大的性能提升。采用cache分块优化策略后，其运行速率加速比达到1.92。采用CSRC存储格式后的性能加速比可以达到1.78。根据应用特点自适应性能调优后的CRSD实现，与Intel MKL中DIA(DIAgonal format)实现相比，其运行速率加速比可以达到2.37;相对于CSR实现，加速比可以达到4.61。
目前，多核处理器以及GPGPU(General-Purpose Graphics Processing Unit)计算加速部件在高性能计算机中被广泛应用。国产天河-1A，星云等大型机多采用结点间高速网络连接，结点内多核处理器配有加速部件的混合层次结构。OpenCL(Open Computing Language)使GPGPU被广泛应用到科学计算过程中。首先，在GPU上使用OpenCL实现了基于CRSD存储格式的稀疏矩阵向量乘。该实现借助代码生成器在运行时动态生成稀疏矩阵向量乘Kernel代码。然后，在CRSD多核优化的基础上，实现了CPU/GPU混合编程。并提出了CPU/GPU混合实现时的任务划分策略，实现负载均衡。该划分策略还能有效判断CPU/GPU混合并行编程是否能够提高运行速率。与现有优化(Bell and Garland，SC2009)中四种存储格式的最优实现相比，基于CRSD的GPGPU Kernel实现，对双精度和单精度处理的加速比分别达到1.52和1.94。CPU/GPU混合优化后的性能实现相对于CRSD多核实现的性能加速比可以达到1.56。