Implementation of a Parallel Tree Method on a GPU

Details Implementation of a Parallel Tree Method on a GPU Implementation of a Parallel Tree Method on a GPU

2011-12-20

arxiv.org/abs/1112.4539v1

Astronomy and Astrophysics

Astrophysics

Instrumentation and Methods for Astrophysics

Journal of Computational Science, 2011; See our recent update at http://galaxy.u-aizu.ac.jp/trac/note/wiki/Octree_On_GPU

Scientific paper

10.1016/j.jocs.2011.01.006

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.

Affiliated with

Also associated with

No associations

Rating

Implementation of a Parallel Tree Method on a GPU does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Implementation of a Parallel Tree Method on a GPU, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implementation of a Parallel Tree Method on a GPU will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-54388