A single-tree algorithm to compute the Euclidean minimum spanning tree on GPUs

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

Computing the Euclidean minimum spanning tree (Emst) is a computationally demanding step of many algorithms. While work-efficient serial and multithreaded algorithms for computing Emst are known, designing an efficient GPU algorithm is challenging due to a complex branching structure, data dependencies, and load imbalances. In this paper, we propose a single-tree Borůvka-based algorithm for computing Emst on GPUs. We use an efficient nearest neighbor algorithm and reduce the number of the required distance calculations by avoiding traversing subtrees with leaf nodes in the same component. The developed algorithms are implemented in a performance portable way using ArborX, an open-source geometric search library based on the Kokkos framework. We evaluate the proposed algorithm on various 2D and 3D datasets, show and compare it with the current state-of-the-art open-source CPU implementations. We demonstrate 4-24 × speedup over the fastest multi-threaded implementation. We prove the portability of our implementation by providing results on a variety of hardware: AMD EPYC 7763, Nvidia A100 and AMD MI250X. We show scalability of the implementation, computing Emst for 37 million 3D cosmological dataset in under a 0.5 second on a single A100 Nvidia GPU.

Original languageEnglish
Title of host publication51st International Conference on Parallel Processing, ICPP 2022 - Main Conference Proceedings
PublisherAssociation for Computing Machinery
ISBN (Electronic)9781450397339
DOIs
StatePublished - Aug 29 2022
Event51st International Conference on Parallel Processing, ICPP 2022 - Virtual, Online, France
Duration: Aug 29 2022Sep 1 2022

Publication series

NameACM International Conference Proceeding Series

Conference

Conference51st International Conference on Parallel Processing, ICPP 2022
Country/TerritoryFrance
CityVirtual, Online
Period08/29/2209/1/22

Funding

This manuscript has been authored by UT-Battelle, LLC, under contract DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a nonexclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. This research used resources of the Oak Ridge Leadership Computing Facility at the Oak Ridge National Laboratory, which is supported by the Office of Science of the U.S. Department of Energy under Contract No. DE-AC05-00OR22725. This research was supported by the Exascale Computing Project (17-SC-20-SC), a collaborative effort of the U.S. Department of Energy Office of Science and the National Nuclear Security Administration.

FundersFunder number
U.S. Department of EnergyDE-AC05-00OR22725
Office of Science
National Nuclear Security Administration

    Keywords

    • Euclidean minimum spanning tree
    • GPU
    • parallel algorithm

    Fingerprint

    Dive into the research topics of 'A single-tree algorithm to compute the Euclidean minimum spanning tree on GPUs'. Together they form a unique fingerprint.

    Cite this