Microsoft Word - 5 王伟.doc

Size: px

Start display at page:

Download "Microsoft Word - 5 王伟.doc"

犹申
5 years ago
Views:

1 ISSN CODEN JKYTA8 Journal of Frontiers of Computer Science and Technology /2011/05(11) Tel: DOI: /j.issn N-body * 王伟 1,2,3+, 曾栩鸿 1,2,3, 王福焕 1,2,3, 傅丽丽 1,2,3, 曾国荪 1. 同济大学计算机科学与技术系, 上海国家高性能计算机工程技术中心同济分中心, 上海 ,2,3 3. 同济大学嵌入式系统与服务计算教育部重点实验室, 上海 Parallel Time-Space Processing Model Based Fast N-body Simulation * WANG Wei 1,2,3+, ZENG Xuhong 1,2,3, WANG Fuhuan 1,2,3, FU Lili 1,2,3, ZENG Guosun 1,2,3 1. Department of Computer Science and Engineering, Tongji University, Shanghai , China 2. Tongji Branch, National Engineering & Technology Center of High Performance, Shanghai , China 3. Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai , China + Corresponding author: willtongji@gmail.com WANG Wei, ZENG Xuhong, WANG Fuhuan, et al. Parallel time-space processing model based fast N-body simulation. Journal of Frontiers of Computer Science and Technology, 2011, 5(11): 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 *The National Natural Science Foundation of China under Grant No , ( ); the Joint Funds of NSFC and Microsoft Asia Research under Grant No (NSFC- ); the Doctoral Fund of Ministry of Education of China under Grant No ( ); the Program of Shanghai Subject Chief Scientist under Grant No. 10XD ( ); the Open Fund of State Key Laboratory of High- End Server & Storage Technology under Grant No. 2009HSSA06 (); the Program for Young Excellent Talents in Tongji University under Grant No , 2009KJ030 ( ). Received , Accepted

2 N-body 1007 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 图形处理器 (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); 时间空间模型 A TP301 1 N-body N, N-body PP(particle-particle), N 1 i,,,,, PP O(N 2 ), N,, N-body, BH (Barnes-Hut) [1] FMM(fast multiple method) [2] BH O(N lb N), FMM O(N) N-body,, GRAPE(gravity pipeline) GPU (graphic processing unit) GPU, GPU N-body PP BH, CPU, 400, GPU, N-body N-body N, [3], N-body,,, N-body,, 2.1 PP, PP N, x i v i, 1 i N, i j f ij f ij mm i j ij = G r r 2 r ij ij (1)

3 1008 Journal of Frontiers of Computer Science and Technology 2011, 5(11), m i m j i j ;, r ij =x j x i i j ; G,, i j i F i, N 1 m j r F = f = G m 1 1 r i ij i j N j N ij j i j i ij 3 (2) (2) PP, O(N 2 ) PP,,,,, [4] 2.2 BH PP, Treecode,,,,,, ( 4 );, Treecode BH [2] FMM [5] BH, N-body BH Barnes Hut 1986,, O(N lb N) 1%, BH (1) (2 ) ( ) (2) Box Box, Box, Box (3), Box, Box( ) l Box, D Box p 1 D < θ, θ, Box p p ;, 1 D θ, Box, force = G m mcm xcm x ycm y zcm z (3),, r r r, ( x, yz, ), m, ( xcm, ycm, zcm ) Box, m cm Box, r = cm + cm + cm ( x x) ( y y) ( z z), G 3 N-body, N-body,,,, (random access machine, RAM)

N-body 1009,,,,, SIMD(single instruction multiple data) PRAM(parallel random access machine) MIMD(multiple instruction multiple data) APRAM(asynchronize parallel random access machine)

1 GPU F i, f ij N N i j, i F i, Tile Tile p p, Tile 2p p 2 Tile p, p, Tile,, 1,, Tile Fig.

4 N-body 1009,,,,, SIMD(single instruction multiple data) PRAM(parallel random access machine) MIMD(multiple instruction multiple data) APRAM(asynchronize parallel random access machine) MIMD BSP(bulk synchronous parallel) LogP(latency, overhead, gap, processor) [6] PP, N-body,,, GPU N-body, ;, ;,, GPU, GPU N-body 4 N-body GPU,, BH N-body 4.1 GPU F i, f ij N N i j, i F i, Tile Tile p p, Tile 2p p 2 Tile p, p, Tile,, 1,, Tile Fig.1 Tile presentation 1 Tile thread block (OpenCL (open computing language), thread OpenCL work-item, block work-group), block p thread Tile Tile,, GPU, Tile p p Tile, thread, block,, 2 walk, walk,, walk Fig.2 Block-thread presentation 2 Block-thread, GPU (parallel time-space processing model, PTPM), GPU, GPU

1010 Journal of Frontiers of Computer Science and Technology 2011, 5(11) 4.2 PTPM GPU BH 3 Nyland [4], i-parallel block 2 thread-block, i, j, N i, N j, thread i walk i, GPU, i, Fig.

5 1010 Journal of Frontiers of Computer Science and Technology 2011, 5(11) 4.2 PTPM GPU BH 3 Nyland [4], i-parallel block 2 thread-block, i, j, N i, N j, thread i walk i, GPU, i, Fig.3 Nyland s GPU execution plan (i-parallel) 3 Nyland GPU (i-parallel) Hamada [7] j-parallel N j N j /n block, block thread N j i, block, i GPU,,, block, GPU thread,,,, CPU, Hamada [8] w-parallel block walk i block 0, walk 0 i, block 0, j-parallel, 1/3 j i, block, 1/3, j-parallel block, 4.3,, jw-parallel j-parallel w-parallel w-parallel, block, block, block walk, block walk j-parallel, thread Tile, jw-parallel, thread Tile, GPU, GPU (jw-parallel), walk CPU, walk GPU GPU, GPU block, block walk block, block,, thread, block, GPU CPU, CPU (1),, 1 024, j-parallel (2) thread, thread Tile, (3), BH, walk 1, PP, PP (4) walk GPU, walk CPU, CPU GPU

N-body 1011 5 5.1 AMD Radeon HD 5850 GPU GPU, GPU 1 044 GFLOPS (1 440, 725 MHz, ), N-body, GFLOPS, PP, 9 9 1 1, 20, flop GFLOPS OpenCL 1.0, AMD ATI Stream SDK V2.2 ATI Stream SDK V2.

4 The performance of jw-parallel in different number of particles 4 jw-parallel, 1 024, 300, 408 (131 072 ), CPU GPU 100, 1 5.2.2 GPU jw-parallel i-parallel j-parallel w-parallel, 5, ( 4 096), GPU, Fig.

6 N-body AMD Radeon HD 5850 GPU GPU, GPU GFLOPS (1 440, 725 MHz, ), N-body, GFLOPS, PP, , 20, flop GFLOPS OpenCL 1.0, AMD ATI Stream SDK V2.2 ATI Stream SDK V2.2, ATI CatalystTM, OpenCL AMD GPU, Intel Pentium GHz, Microsoft Windows XP 5.2 N-body GPU CPU, i-parallel j- parallel PP, w-parallel jw-parallel BH CPU GPU i-parallel j-parallel w-parallel CPU jw-parallel CPU, AMD, GPU FLOPS jw-parallel 5850 GPU 4 4, ( 4 096), GPU 300 GFLOPS, 431 GFLOPS( ) CPU, Fig.4 The performance of jw-parallel in different number of particles 4 jw-parallel, 1 024, 300, 408 ( ), CPU GPU 100, GPU jw-parallel i-parallel j-parallel w-parallel, 5, ( 4 096), GPU, Fig.5 The performance of jw-parallel, i-parallel, j-parallel and w-parallel in different number of particles 5 jw-parallel i-parallel j-parallel w-parallel, jw-parallel GPU 100,

7 1012 Journal of Frontiers of Computer Science and Technology 2011, 5(11) Table 1 Comparison of running time of CPU and GPU (jw-parallel) in different number of particles 1 CPU jw-parallel (100 )/s CPU > > GPU Table 2 Comparison of total time of various GPU plans in different number of particles 2 GPU (100 )/s i-parallel j-parallel w-parallel jw-parallel Table 3 Comparison of running time of various GPU plans in different number of particles 3 GPU (100 )/s i-parallel j-parallel w-parallel jw-parallel ,, jw-parallel, 3, jw-parallel 6 N-body AMD Radeon HD 5850 N-body (PP BH ) N-body, GPU PTPM, GPU N-body, GPU N-body, AMD HD Radeon 5850, CPU, 400 ; GPU, 2 5 References: [1] Barnes J, Hut P. A hierarchical O(nlogn) force-calculation algorithm[j]. Nature, 1986, 324: [2] Greengard L, Rokhlin V. A fast algorithm for particle simulations[j]. Journal of Computational Physics, 1987, 73(2): [3] Hagihara Y. Celestial mechanics[m]. Cambridge: MIT Press, [4] Nyland L, Harris M, Prins J. Fast N-body simulation with CUDA[J]. GPU Germs, 2007, 3: [5] Hamada T, Nitadori K, Benkrid K, et al. A novel multiple walk parallel algorithm for the Barnes-Hut treecode on GPUs towards cost effective, high performance N-body

N-body 1013 simulation[j]. Computer Science: Research and Development, 2009, 24(1/2): 21 31. [6] Chen Guoliang. Parallel computing-structure, algorithm and programming[m].

(2007-03)[2011-04]. http://arxiv.org/abs/astro-ph/0703100. [8] Hamada T, Yokota R, Nitadori K, et al.

Storage and Analysis (SC 09). New York, NY, USA: ACM, 2009: 14 20. 附中文参考文献 : [6]. [M]. :, 2003. WANG Wei was born in 1979. He received his Ph.D. degree from Tongji University.

His research interests include parallel distributed computing, trustworthy computing and cloud computing, etc. (1979 ),,,,,, ZENG Xuhng was born in 1987.

She is a master candidate at Tongji University. Her research interests include parallel computing and reconfigurable computing, etc. (1986 ),,,,, FU Lili was born in 1986.

8 N-body 1013 simulation[j]. Computer Science: Research and Development, 2009, 24(1/2): [6] Chen Guoliang. Parallel computing-structure, algorithm and programming[m]. Beijing: Higher Education Press, [7] Hamada T, Titaka I. The chamomile scheme: an optimized algorithm for N-body simulations on programmable graphics processing units[eb/ol]. ( )[ ]. [8] Hamada T, Yokota R, Nitadori K, et al. 42 TFLOPS hier- archical N-body simulations on GPUs with applications in both astrophysics and turbulence[c]//proceedings of the Conference on High Performance Computing Networking, Storage and Analysis (SC 09). New York, NY, USA: ACM, 2009: 附中文参考文献 : [6]. [M]. :, WANG Wei was born in He received his Ph.D. degree from Tongji University. Now he is a lecturer at Department of Computer Science and Technology, Tongji University. His research interests include parallel distributed computing, trustworthy computing and cloud computing, etc. (1979 ),,,,,, ZENG Xuhng was born in He is a master candidate at Tongji University. His research interests include parallel computing and cloud computing, etc. (1987 ),,,,, WANG Fuhuan was born in She is a master candidate at Tongji University. Her research interests include parallel computing and reconfigurable computing, etc. (1986 ),,,,, FU Lili was born in She is a master candidate at Tongji University. Her research interests include parallel computing and GPU programming, etc. (1986 ),,,,, GPU ZENG Guosun was born in He received his Ph.D. degree from Shanghai Jiaotong University. Now he is a professor and doctoral supervisor at Tongji University, and the senior member of IEEE and CCF. His research interests include parallel computing, trustworthy computing and cloud computing, etc. (1964 ),,,, IEEE CCF,, 863,,,

Microsoft Word - 3 王伟.doc

Microsoft Word - 3 王伟.doc ISSN 1673-9418 CODEN JKYTA8 E-mail: fcst@vip.163.com Journal of Frontiers of Computer Science and Technology http://www.ceaj.org 1673-9418/2012/06(02)-0118-07 Tel: +86-10-51616056 DOI: 10.3778/j.issn.1673-9418.2012.02.003