Implementation of a Parallel Tree Method on a GPU

Abstract

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.

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

References in corpus (5)

• High Performance Direct Gravitational N-body Simulations on Graphics Processing Units -- II: An implementation in CUDA
• High Performance Direct Gravitational N-body Simulations on Graphics Processing Unit I: An implementation in Cg
• Gravitational tree-code on graphics processing units: implementation in CUDA
• The Chamomile Scheme: An Optimized Algorithm for N-body simulations on Programmable Graphics Processing Units
• Fast Simulations of Gravitational Many-body Problem on RV770 GPU

Cited by in corpus (13)

• The Core-Cusp Problem in Cold Dark Matter Halos and Supernova Feedback: Effects of Oscillation
• What sets the central structure of dark matter haloes?
• Dynamical Evolution of Primordial Dark Matter Haloes through Mergers
• GOTHIC: Gravitational oct-tree code accelerated by hierarchical time step controlling
• Dynamical friction and scratches of orbiting satellite galaxies on host systems
• Sacrificing information for the greater good: how to select photometric bands for optimal accuracy
• Astrophysical data mining with GPU. A case study: genetic classification of globular clusters
• Astrophysical Particle Simulations on Heterogeneous CPU-GPU Systems
• GTS: GPU-based Tree Index for Fast Similarity Search
• Manycore processing of repeated k-NN queries over massive moving objects observations
• GPU accelerated Hybrid Tree Algorithm for Collision-less N-body Simulations
• Manycore processing of repeated range queries over massive moving objects observations
• Gravitational octree code performance evaluation on Volta GPU