论文部分内容阅读
N点相关函数在星系分布的研究上有重要的意义，是宇宙学模拟中的基本问题。但是朴素解法的计算复杂度却随着点集的扩大而呈点相关数的次方增长，虽然有基于KDTree等的相关优化算法，但是其复杂度也与点集中的点数相关，处理大规模点集时性能也难以满足要求。一种基于递归卷积的优化算法，可以求得近似解，而为了取得较高的计算精度，则要扩大计算矩阵的规模，这同样需要解决相应的性能问题。本文对解决递归卷积算法在解三点相关函数所存在的性能问题、计算精度问题、以及二者之间的折衷问题进行研究和分析。本文首先使用宇宙学模拟中的真实数据分析原始算法在不同的矩阵规模下的计算性能问题和计算精度问题。以此入手，提出相应的解决方案，即通过扩大矩阵规模提升相应的计算精度，而另一方面利用多GPU解决随之带来的性能问题。对于算法并行优化，首先将算法简单迁移到单颗GPU上运行，分析对比不同参数下的性能变化。其次，分析改进后的GPU算法的程序结构，对GPU下的快速傅立叶变换的特性进行分析，调整快速傅立叶的变换维度和变换尺寸，以此获得进一步性能优化。最后分析多GPU程序运行特点，将优化过的单GPU算法进行调整，设计并实现出多GPU环境下的算法，使算法在多GPU环境下相对单GPU的加速比能够接近GPU数，以充分发挥各个GPU的计算效率。本文使用Tesla C2050GPU相关环境进行相关实验，实验结果显示多GPU环境下的递归卷积算法较原始算法在较高计算精度下，性能提升近七百倍。