Implementation of a Parallel Tree Method on a GPU
Department of Computer Science and Engineering, University of Aizu, Aizu-Wakamatsu, Fukushima 965-8580, Japan
arXiv:1112.4539v1 [astro-ph.IM] (20 Dec 2011)
@article{2011arXiv1112.4539N,
author={Nakasato}, N.},
title={"{Implementation of a Parallel Tree Method on a GPU}"},
journal={ArXiv e-prints},
archivePrefix={"arXiv"},
eprint={1112.4539},
primaryClass={"astro-ph.IM"},
keywords={Astrophysics – Instrumentation and Methods for Astrophysics, Astrophysics – Galaxy Astrophysics, Computer Science – Performance},
year={2011},
month={dec},
adsurl={http://adsabs.harvard.edu/abs/2011arXiv1112.4539N},
adsnote={Provided by the SAO/NASA Astrophysics Data System}
}
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.
December 21, 2011 by hgpu
