基于异构计算的MOND数值模拟加速技术研究

发布时间：2018-09-14 17:22

【摘要】：现代宇宙学中,科学家们提出了许多新理论来解释种种天文现象。他们需要基于观测现象进行精确的数值模拟,依据模拟结果验证新理论的正确性。而天文观测结果表明,基于牛顿力学所建立的宇宙学模型无法解释观测获得的星系旋转曲线等现象。为了解决这些问题,理论物理学家指出牛顿力学在星系大尺度空间下可能不准确,发展出不同于暗物质理论的修正牛顿动力学理论(Modified Newtonian Dynamics,MOND)。但是由于MOND理论的数值模拟包含具有高计算复杂度的N体模拟,受计算能力的制约,MOND数值模拟的规模一直不大。N体模拟是天体动力学模拟中重要的基础运算之一。它不仅在天体物理学中被用来模拟星系的演变、验证新的宇宙学理论,还在等离子体物理、分子动力学、流体动力学等科学、工程领域都有着重要的地位。随着近年来计算机技术的发展带来的计算能力骤增,N体模拟的规模越来越大,在各个领域也发挥着越来越重要的作用。目前对于N体模拟的计算能力需求依旧在不断增大。为了简化计算,研究人员做出了许多假设,提出了多种近似算法,比如粒子网格算法(Particle Mesh,PM),树形算法(Tree),树-粒子网格混合(TreePM)算法以及粒子-粒子网格混合算法(P3M)。其中,TreePM算法,由于可以较好地平衡计算精度和速度的需求,在天文学数值模拟领域获得了广泛的应用。为了进一步提高计算速度,多种计算加速技术也被应用到N体模拟中。利用新的计算加速技术来加速N体模拟也一直是学术界和工业界的研究热点。可编程逻辑门阵列(FPGA)和通用图形处理单元(GPGPU)由于各自的特点,经常被用到N体模拟加速中。本学位论文主要围绕加速MOND数值模拟展开,基于应用的需求选择了合适的TreePMN体模拟算法,剖析了算法的计算瓶颈,依据运算特点将计算任务分配给GPU、FPGA;接着利用包含CPU、GPU、FPGA的异构加速平台实现了对MOND数值模拟的加速。借助FPGA动态可重构的功能,当PM模块空闲时,将其逻辑资源配置成Tree模块,从而提高了资源利用率。实验结果表明,动态可重构功能的加入使得系统性能提升了 24%。本文的异构平台较传统的高性能CPU服务器有更好的计算性能和更低的功耗。当粒子数为3x106、网格大小为1283、Tree算法中计算的张角为0.5时,异构平台相比于CPU服务器的加速比为9.37,能耗比为24.42。本文最后探讨将异构加速平台扩展至多个计算节点的方式,分析了设计的可扩展性。本论文主要研究工作包括:(1)基于MOND数值模拟的特点,对比研究了各种N体模拟算法,针对MOND数值模拟中数据模拟规模大、计算复杂度高、模拟时间长、具有强成团性的特点,选用了经典的TreePM算法,并且对其进行更为深入的研究。首先,以CPU串行实现为基础,分析算法各部分的占用时间,剖析算法的性能瓶颈。针对Tree部分中耗时最多的建立树型数据结构、粒子相互作用势能计算以及多维快速傅里叶变换计算部分在不同平台上的加速,分析加速效果,比较优劣。同时,分析TreePM算法的访存模式,对Tree部分粒子进行预先排序,加速了粒子的势能计算。(2)实现了基于TreePM算法的MOND数值模拟异构加速。主要采用FPGA进行核心计算,利用FPGA动态可重构的特点,为多维快速傅里叶变换计算和粒子间相互作用势能计算合理分配逻辑资源。同时,由GPU完成树型数据结构建立这种具有较高并行度的递归算法。余下的任务调配、粒子位置和速度的更新、以及数据的输入输出等工作则交由CPU完成。该设计充分利用了各平台的特点,提高了 TreePM算法实现的性能及功耗比,首次完成了 TreePM算法在FPGA、CPU和GPU异构平台上的加速,为N体模拟加速提供新的实现方案。(3)进一步地探讨设计的合理性,提出上述算法实现的扩展方案。采用皮亚诺-希尔伯特曲线来划分各节点Tree计算的区域范围,并结合FPGA的动态可重构的特性,更细粒度地分配资源,减小负载不均衡带来的影响,实现良好的可扩展性。
[Abstract]:......
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：P159

【参考文献】