Kd-tree Based N-Body Simulations with Volume-Mass Heuristic on the GPU

Klaus Kofler, Dominik Steinhauser, Biagio Cosenza, Ivan Grasso, Sabine Schindler, Thomas Fahringer
Institute of Computer Science, DPS, University of Innsbruck, Austria
Workshop on Parallel and Distributed Scientific and Engineering Computing (PDSEC), 2014


   author={Kofler, Klaus and Steinhauser, Dominik and Cosenza, Biagio and Grasso, Ivan and Schindler, Sabine and Fahringer, Thomas},

   title={Kd-tree Based N-Body Simulations with Volume-Mass Heuristic on the GPU},

   booktitle={Workshop on Parallel and Distributed Scientific and Engineering Computing (PDSEC)},


   keywords={n-body, gpgpu, kd-tree}


Download Download (PDF)   View View   Source Source   



N-body simulations represent an important class of numerical simulations in order to study a wide range of physical phenomena for which researchers demand fast and accurate implementations. Due to the computational complexity, simple brute-force methods to solve the long-distance interaction between bodies can only be used for small-scale simulations. Smarter approaches utilize neighbor lists, tree methods or other hierarchical data structures to reduce the complexity of the force calculations. However, such data structures have complex building algorithms which hamper their parallelization for GPUs. In this paper, we introduce a novel method to effectively parallelize N-body simulations for GPU architectures. Our method is based on an efficient, three-phase, parallel Kd-tree building algorithm and a novel volume-mass heuristic to reduce the simulation time and increase accuracy. Experiments demonstrate that our approach is the fastest monopole implementation with an accuracy that is comparable with state of the art implementations (GADGET-2). In particular, we are able to reach a simulation speed of up to 3 Mparticles/s on a single GPU for the force calculation, while still having a relative force error below 0.4% for 99% of the particles. We also show competitive performance with existing GPU implementations, while our competitor shows worse accuracy behavior as well as a higher energy error during time integration.
Rating: 2.5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: