并行时空处理模型下的快速N-body算法

计算机科学与探索 ›› 2011, Vol. 5 ›› Issue (11): 1006-1013.

并行时空处理模型下的快速N-body算法

王伟, 曾栩鸿, 王福焕, 傅丽丽, 曾国荪

1. 同济大学计算机科学与技术系, 上海 200092
2. 国家高性能计算机工程技术中心同济分中心, 上海 200092
3. 同济大学嵌入式系统与服务计算教育部重点实验室, 上海 200092

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-11-01 发布日期:2011-11-01

Parallel Time-Space Processing Model Based Fast N-body Simulation

WANG Wei, ZENG Xuhong, WANG Fuhuan, FU Lili, ZENG Guosun

1. Department of Computer Science and Engineering, Tongji University, Shanghai 200092, China 2. Tongji Branch, National Engineering & Technology Center of High Performance, Shanghai 200092, China 3. Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai 200092, China

Received:1900-01-01 Revised:1900-01-01 Online:2011-11-01 Published:2011-11-01

摘要/Abstract

摘要： 图形处理器(graphic processing unit, GPU)的最新发展已经能够以低廉的成本提供高性能的通用计算。基于GPU的CUDA (compute unified device architecture)和OpenCL (open computing language)编程模型为程序员提供了充足的类似于C语言的应用程序接口(application programming interface, API), 便于程序员发挥GPU的并行计算能力。采用图形硬件进行加速计算, 通过一种新的GPU处理模型——并行时间空间模型, 对现有GPU上的N-body实现进行了分析, 从而提出了一种新的GPU上快速仿真N-body问题的算法, 并在AMD的HD Radeon 5850上进行了实现。实验结果表明, 相对于CPU上的实现, 获得了400倍左右的加速; 相对于已有GPU上的实现, 也获得了2至5倍的加速。

关键词: N-body, 并行计算, 通用图形处理器(GPGPU), 时间空间模型

Abstract: With the development of graphic processing unit (GPU), the general processing with high performance can be achieved with low cost. The GPU based compute unified device architecture (CUDA) and open computing language (OpenCL) programming model provide adequate application programming interfaces (APIs) similar to C language, which can be utilized by programmer with the power of GPU parallel processing. This paper presents a novel parallel implementation algorithm of N-body gravitational simulation on GPU. The algorithm uses graphics hardware to accelerate computation, and is optimized to N-body computation based on parallel time-space processing model (PTPM) on GPUs. The paper also analyzes the current implementations of GPU, and gives a new method on implementing N-body algorithm on HD Radeon 5850 GPU of AMD. Experimental results show that this method achieves an acceleration of 400 times compared with CPU, and an acceleration up to 2-5 times compared with GPU.

Key words: N-body, parallel computing, general purpose graphic processing unit (GPGPU), time-space model

王伟, 曾栩鸿, 王福焕, 傅丽丽, 曾国荪. 并行时空处理模型下的快速N-body算法[J]. 计算机科学与探索, 2011, 5(11): 1006-1013.

WANG Wei, ZENG Xuhong, WANG Fuhuan, FU Lili, ZENG Guosun

. Parallel Time-Space Processing Model Based Fast N-body Simulation[J]. Journal of Frontiers of Computer Science and Technology, 2011, 5(11): 1006-1013.

[1]	李秉政，黄高阳，许瑾晨. 面向申威众核处理器的LZMA并行算法设计与优化[J]. 计算机科学与探索, 2020, 14(9): 1501-1509.
[2]	刘徐，肖志勇，甘霖，徐敬蘅，陈宏博. 神威国产处理器应用程序的并行参数自动寻优[J]. 计算机科学与探索, 2020, 14(11): 1838-1848.
[3]	李勇，滕飞，黄齐川，李天瑞. 基于Spark的时间序列并行分解模型[J]. 计算机科学与探索, 2018, 12(7): 1055-1063.
[4]	景翠萍，廖丽，王伟. 面向非结构网格应用并行程序的编程工具[J]. 计算机科学与探索, 2018, 12(2): 252-262.
[5]	韩超，段磊，邓松，王慧锋，唐常杰. 基于Spark的序列数据质量评价[J]. 计算机科学与探索, 2017, 11(6): 897-907.
[6]	王涛，胡双林. 材料科学中的高性能计算[J]. 计算机科学与探索, 2017, 11(2): 185-193.
[7]	郝赫，司雨蒙，韦建文，文敏华，林新华. 天体物理成团研究中的非规则访存优化[J]. 计算机科学与探索, 2017, 11(1): 80-90.
[8]	揭月馨，刘浩. 融合有向图集与并行架构的HEVC去块滤波[J]. 计算机科学与探索, 2016, 10(9): 1221-1228.
[9]	詹杭龙，曹东刚，谢冰. 分布共享环境下支持弹性伸缩的图处理框架[J]. 计算机科学与探索, 2016, 10(7): 901-914.
[10]	赵莲，赵永华，陈尧，赵慰. GPU集群加速近似逆预条件CG并行求解器[J]. 计算机科学与探索, 2015, 9(9): 1084-1092.
[11]	林娟，杜庆良，杨辉，钟一文. 基于粒子群优化算法的并行模拟退火算法[J]. 计算机科学与探索, 2014, 8(7): 886-896.
[12]	韦向远，杨辉华，谢谱模. 基于CUDA的并行布谷鸟搜索算法设计与实现[J]. 计算机科学与探索, 2014, 8(6): 665-673.
[13]	师金钢，郑艳，孙焕良，栾方军. 云环境中海量数据的并行分组密码体制研究[J]. 计算机科学与探索, 2014, 8(2): 161-170.
[14]	吴再龙，张云泉，徐建良，贾海鹏，颜深根，解庆春. 基于OpenCL的Kmeans算法的优化研究[J]. 计算机科学与探索, 2014, 8(10): 1162-1176.
[15]	叶炜晨，陈克非. 快速寻找非线性反馈移位寄存器的编程算法[J]. 计算机科学与探索, 2014, 8(1): 28-39.