近年来,在世界超级计算机500强排行榜上,天河二号曾连续位居第一,去年神威太湖之光也夺得榜首!可以说我国在超级计算机硬件方面已经走到了世界的前列。要充分利用好如此巨大的计算能力,就要密切结合超级计算机的架构特征进行高效并行算法设计与评估。当前,超级计算机的一个显著特征是异构众核,在CPU的处理速度几乎达到物理极限的情况下,超级计算机需借助于GPU(或MIC)进行协同加速,即CPU+GPU已成为超级计算机的基本架构。另一方面,科学与工程计算的许多应用都归结为大型稀疏线性代数方程组的求解,其求解时间往往在整个数值模拟时间中占有非常大的比重(有的甚至超过80%,如辐射流体力学或辐射输运数值模拟)。因此,面向CPU+GPU架构研究线性代数方程组的高效并行求解与评估,成为在当前超级计算机上进行高效数值模拟的重中之重。本文以共轭梯度(CG)方法为例,对此进行了一些探索,主要进行了如下三个方面的工作:其一,针对四种常用的稀疏矩阵存储格式:CSR-V、CSR-S、ELL和JAD,分别建立了在GPU上高效实现稀疏矩阵向量乘积(SpMV)的两种新的性能预估模型:均匀分布模型和正态分布模型。这两种模型从矩阵结构的角度出发,基于统计学观点,通过线性拟合构造出含有两个参变量的性能预估函数。给定一个目标矩阵,需要根据矩阵结构和规模得到目标矩阵的两个参数,然后将这两个参数代入到性能预估函数中就能得到目标矩阵的SpMV的预测运行时间。这不仅克服了文献中SpMV在GPU上性能预估模型未考虑矩阵结构的缺陷,同时实验结果表明我们的两种模型的预估精确度平均比文献中的模型高1.69倍,且预估值与实测值的平均误差不超过3.5%。其二,构建了 CG方法在CPU+GPU架构上的性能预估模型。通过分析CPU与GPU之间的通讯原理和CG方法的计算内核,构造了 CPU与GPU之间通讯预估模型及其通讯与GPU内核计算重叠的性能预估函数,还建立了向量内积和向量校正在CPU上的性能预估模型。再结合已经构建的SpMV在GPU上预估模型,得到是CG方法在CPU+GPU架构上的性能预估模型。数值实验分别在PC机和中科院网络信息中心超级计算机“元”上来进行,结果表明:CG方法的预估值与实测值的平均误差不超过4.3%。这里构建的性能预估模型可容易地推广到其它Krylov子空间迭代方法(如GMRES、BiCGSTAB等)上。其三,通过计算的重叠,在CPU+GPU架构上更高效地实现了 CG方法。分析CG方法之后发现,在每一步迭代中,GPU上计算的矩阵向量乘积与CPU上计算的向量内积之间没有关联,因此可以同时计算,也即重叠计算,这样就降低了运算时间,使得CG方法整体性能得以提高。此外,我们还将重叠技巧应用于经过重排的MCG算法,由于MCG算法每一步迭代的矩阵向量乘积可以重叠掉一个向量内积和两个向量校正,因此重叠度更高,实验结果也表明重叠后性能提升得更明显。