Implementation of a Parallel Tree Method on a GPU

Naohito Nakasato
Department of Computer Science and Engineering, University of Aizu, Aizu-Wakamatsu, Fukushima 965-8580, Japan
arXiv:1112.4539v1 [astro-ph.IM] (20 Dec 2011)


   author={Nakasato}, N.},

   title={"{Implementation of a Parallel Tree Method on a GPU}"},

   journal={ArXiv e-prints},




   keywords={Astrophysics – Instrumentation and Methods for Astrophysics, Astrophysics – Galaxy Astrophysics, Computer Science – Performance},




   adsnote={Provided by the SAO/NASA Astrophysics Data System}


Download Download (PDF)   View View   Source Source   



The kd-tree is a fundamental tool in computer science. Among other applications, the application of kd-tree search (by the tree method) to the fast evaluation of particle interactions and neighbor search is highly important, since the computational complexity of these problems is reduced from O(N^2) for a brute force method to O(N log N) for the tree method, where N is the number of particles. In this paper, we present a parallel implementation of the tree method running on a graphics processing unit (GPU). We present a detailed description of how we have implemented the tree method on a Cypress GPU. An optimization that we found important is localized particle ordering to effectively utilize cache memory. We present a number of test results and performance measurements. Our results show that the execution of the tree traversal in a force calculation on a GPU is practical and efficient.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: