1112.4539 (Naohito Nakasato)
Naohito Nakasato
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.
View original:
http://arxiv.org/abs/1112.4539
No comments:
Post a Comment