Presentation
SIGN IN TO VIEW THIS PRESENTATION Sign In
Efficient Tree-based Parallel Algorithms for N-Body Simulations Using C++ Standard Parallelism
DescriptionThe Barnes-Hut approximation for N-body simulations reduces the time complexity of the naive all-pairs approach from O(N^2) to O(N log N) by hierarchically aggregating nearby particles into single entities using a tree data structure.
This inherently irregular algorithm poses substantial challenges for performance portable implementations on multi-core CPUs and GPUs.
We introduce two portable fully-parallel Barnes-Hut implementation strategies that trade-off different levels of GPU support for performance: an unbalanced concurrent octree, and a balanced bounding volume hierarchy sorted by a Hilbert space-filling curve.
We implemente these algorithms in portable ISO C++ using parallel algorithms and concurrency primitives like atomics.
The results demonstrate competitive performance on a range of CPUs and GPUs.
Additionally, they highlight the effectiveness of the par execution policy for highly concurrent irregular algorithms, outperforming par_unseq on CPUs and GPUs with Independent Forward Progress.
This inherently irregular algorithm poses substantial challenges for performance portable implementations on multi-core CPUs and GPUs.
We introduce two portable fully-parallel Barnes-Hut implementation strategies that trade-off different levels of GPU support for performance: an unbalanced concurrent octree, and a balanced bounding volume hierarchy sorted by a Hilbert space-filling curve.
We implemente these algorithms in portable ISO C++ using parallel algorithms and concurrency primitives like atomics.
The results demonstrate competitive performance on a range of CPUs and GPUs.
Additionally, they highlight the effectiveness of the par execution policy for highly concurrent irregular algorithms, outperforming par_unseq on CPUs and GPUs with Independent Forward Progress.
