2011/06/30 by Jeroen Bédorf, Evghenii Gaburov, Simon Portegies Zwart · 2 citations
Computer Science · Physics and Astronomy · #Algorithm #CUDA #Central processing unit #Code (set theory) #Computational Physics and Python Applications #Computational science #Computer graphics (images) #Computer hardware #Computer science #General-purpose computing on graphics processing units #Graphics #Graphics processing unit #Multi-core processor #Octree #Operating system #Parallel Computing and Optimization Techniques #Parallel computing #Scientific Research and Discoveries #Software portability #Tree (set theory) #Tree traversal #astro-ph.IM #cs.DC
paper · pdf · doi:10.1016/j.jcp.2011.12.024
published as Journal of Computational Physics. Volume 231, Issue 7, 1 April 2012, Pages 2825-2839 · Accepted version. Published in Journal of Computational Physics. 35 pages, 12 figures, single column
openalex publication_date 2011/12/29 · arxiv created 2012/04/10 · arxiv updated 2012/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We present parallel algorithms for constructing and traversing sparse octrees on graphics processing units (GPUs). The algorithms are based on parallel-scan and sort methods. To test the performance and feasibility, we implemented them in CUDA in the form of a gravitational tree-code which completely runs on the GPU.(The code is publicly available at: http://castle.strw.leidenuniv.nl/software.html) The tree construction and traverse algorithms are portable to many-core devices which have support for CUDA or OpenCL programming languages. The gravitational tree-code outperforms tuned CPU code during the tree-construction and shows a performance improvement of more than a factor 20 overall, resulting in a processing rate of more than 2.8 million particles per second.