● 摘要
科学工程计算的规模不断扩大导致对高性能计算机计算能力的需求不断提高，通过增加机群系统单个结点的计算量可以减少结点之间的通讯，从而达到提高整个高性能计算机实际性能的目的。受半导体技术的制约，单个结点实际性能的增加已经无法用提高处理器主频的办法来实现；在片上集成多个处理器核并在一个结点上集成多个处理器已经成为当前高性能计算机获得更高性能的重要途径。
在具有异构体系结构的系统中，现有的并行算法直接移植很难获得较好的性能，例如，已有稀疏矩阵存储格式和相关算法应用移植到多核或众核处理器上时，针对矩阵计算中与矩阵转置相关的算法存在的转置开销过大的问题，NVIDIA公司GTX 200系列GPU的浮点加法计算精度较低等问题，本论文在以下几个方面取得一些研究成果：
（1）针对多核CPU，提出一种基于压缩稀疏块存储格式优化转置稀疏矩阵与稀疏矩阵及稠密向量相乘算法的方法
对于稀疏矩阵A和稠密向量x及稠密向量y，计算y=y+ATAx，其中AT代表稀疏矩阵A的转置矩阵。由于矩阵转置在并行处理的情况下开销较大，如何在多核处理器上高效完成计算是一个很大的挑战。一种新的稀疏矩阵存储格式——压缩稀疏块（Compressed Sparse Blocks，CSB）可以在不转置的情况下高效计算Ax 和 ATx，本文提出一种基于存储格式优化计算y=y+ATAx的方法。实验结果表明：对于70%的测试矩阵，采用CSB存储格式的方法获得的性能超过POSKI并行库采用压缩稀疏行（Compressed Sparse Row,CSR）存储格式的性能，最多达到2.5倍。
（2）提出一种提高（众核）GPU的浮点加法计算精度的优化方法
针对GPU浮点加法计算精度较低的问题，本文提出采用部分和相加算法提高GPU的浮点数加法操作的计算精度，并用稠密矩阵相乘算法验证该方法。实验证明：当两个5120×5120矩阵相乘时，分别在CPU和GPU运行后计算结果相比，二者精度差>1E-6；采用部分和相加算法后，规模为8192×8192的矩阵相乘精度差<1E-6。针对求和浮点数总数相同但部分和粒度不同而产生的精度差别，建立相加浮点数总数与部分和计算粒度之间的数学模型，在此基础上，求出获得最高精度的部分和粒度值，由此提高NVIDIA公司200系列GPU的计算精度。
（3）提出一种在GPU上优化计算转置稀疏矩阵与向量相乘的方法
NVIDIA公司提供一个GPU上函数库CUSPARSE，为稀疏矩阵的相关计算提供接口。对于稀疏矩阵A和稠密向量x及稠密向量y，计算y=y+ATx，其中AT代表稀疏矩阵A的转置，实验证明稀疏矩阵转置操作部分是计算最大开销。本文提出一种基于GPU上原子加方法和采用压缩稀疏行（Compressed Sparse Row，CSR）存储格式的优化计算y=y+ATx的方法。实验结果表明：NVIDIA公司GPU上基于原子加方法的转置避免的算法y=y+ATx的性能与CUSPARSE库实现性能相比，最多提高405倍。
（4） 提出一种在GPU上同时高效计算稀疏矩阵与向量相乘及转置稀疏矩阵与向量相乘算法的优化方法
对于稀疏矩阵A和稠密向量x及稠密向量y，针对在GPU上常用的稀疏矩阵存储结构无法同时高效计算y=y+Ax和y=y+ATx的问题，其中AT代表稀疏矩阵A的转置。本文提出和设计一种适合在GPU上运行的扩展的压缩稀疏块（expanded Compressed Sparse Block,eCSB）的存储结构；针对稀疏矩阵的eCSB存储不同的块行非零元素个数可能差别较大的问题，将CUSP库的HYB存储格式思想用于eCSB存储格式，采用混合方式保存非零元素，从而缩小不同块行非零元素个数差别，在程序运行的过程中，根据矩阵的非零元素分布特点动态选择eCSB的不同存储方式。实验结果表明，在Kepler架构的GPU上计算y=y+Ax及y=y+ATx，均获得较高的性能，达到CPU上基于CSB格式计算性能的13倍。此外，本文设计的eCSB存储结构获得的性能是GPU上CUSP库中已有数据结构（HYB，CSR）实现y=y+Ax和y=y+ATx两种算法性能的1.88倍和9.14倍；从双共轭梯度算法的墙上时间看，eCSB存储结构分别比HYB和CSR快6%和25%。