Show all publications

Gpu Implementation of Borůvka'S Algorithm to Euclidean Minimum Spanning Tree Based on Elias Method

Open DOI PageDownload Bibliography in Open DocumentDownload Bibliography in HTMLDownload BibTeXDownload RISDownload Bibliographical Ontology (RDF)
Authors:
Details:
In Applied Soft Computing, vol. 76, pp. 105-120, 2019.
DOI: 10.1016/j.asoc.2018.10.046.
Abstract:
We present both sequential and data parallel approaches to build hierarchical minimum spanning forest (MSF) or tree (MST) in Euclidean space (EMSF/EMST) for applications whose input N points are uniformly or boundedly distributed in Euclidean space. Each iteration of the sequential approach takes O(N) time complexity through combining Borůvka's algorithm with an improved component-based neighborhood search algorithm, namely sliced spiral search, which is a newly proposed improvement to Bentley's spiral search for finding a component graph's closest outgoing point on the plane. It works based on the uniqueness property in Euclidean space, and allows O(1) time complexity for one search from a query point to find the component's closest outgoing point at different iterations of Borůvka's algorithm. The data parallel approach includes a newly proposed two-direction breadth- first search (BFS) implementation on graphics processing unit (GPU) platform, which is specialized for selecting a spanning tree's shortest ougoing edge. This GPU two-direction parallel BFS enables a tree traversal operation to start from any one of its vertex acting as root. These GPU parallel implementations work by assigning N threads with one thread associated to one input point, one thread occupies O(1) local memory and the whole algorithm occupies O(N) global memory. Experiments are conducted on both uniformly distributed data sets and TSPLIB database. We evaluate computation time of the proposed approaches on more than 80 benchmarks with size N growing up to 10^6 points on personal laptop.
Keywords:
Euclidean Minimum Spanning Tree EMST GPU Parallel EMST Breadth first search GPU parallel BFS decentralized control data parallel
Publication Category:
International journal with reading committee
Copyright 2010-2019 © Laboratoire Connaissance et Intelligence Artificielle Distribuées - Université Bourgogne Franche-Comté - Privacy policy