ArborX, a new open-source C++ search library developed as part of the Exascale Computing Project (ECP), has been shown to improve algorithm performance for proximity searches on collections of geometric objects as total object count and number of search queries scale up. ArborX will speed up exascale applications for computational cosmology, multiphysics data transfer, computational mechanics, wind farm simulations, and other research areas. The work was published in the December 2020 issue of ACM Transactions on Mathematical Software.
Applications running geometric searches require fast calculation of nearest neighbors of a point or finding all objects within a certain distance. This is especially true for exascale applications, which run multiple searches through millions of objects. ArborX improves performance and scalability with tree-based data structures, which offer a reduced logarithmic cost over brute force computations for large supercomputing problems. The library’s creators showed that it performs competitively with state-of-the-art serial libraries such as nanoFLANN and Boost.Geometry and effectively leverages multithreaded CPU and CPU compute power on leadership-class computers such as Summit. ArborX also provides performance portability, making it useful for today’s heterogeneous supercomputing hardware architectures.
The ArborX creators recently collaborated with the HACC (Hardware/Hybrid Accelerated Cosmology Code) team at Argonne National Laboratory to develop a new halo finding algorithm to accelerate the search of regions of high density of dark matter particles. The clustering algorithm developed in ArborX performed 15× better on a single GPU than the multithreaded CPU version used by the ExaSky team on a full Summit node. The HACC effort is part of ECP’s ExaSky project. ArborX has also become an important part of the workflow for numerous ECP applications and recently has become an integral part of xSDK, an extreme-scale scientific software development kit created by a consortium of US Department of Energy national laboratories, universities, and supercomputing facilities.
Future work includes addressing ArborX’s current limitations on scalability of the distributed search algorithms implementation using message passing interface (MPI) for exascale applications where objects indexed by the tree as well as query objects are distributed across many MPI ranks, developing algorithms for high-dimensional data and providing ray-tracing algorithms.
Lebrun-Grandie, D., A. Prokopenko, B. Turcksin, and S.R. Slattery. “ArborX: A performance portable geometric search library.” ACM Transactions on Mathematical Software (December 2020).
