Implementation of a Parallel Tree Method on a GPU

Understand

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.