Spiral Search Method to GPU Parallel Euclidean Minimum Spanning Tree Problem

摘要

We present both sequential and data parallel approaches to build hierarchical minimum spanning forest (MSF) or trees (MST) in Euclidean space (EMSF/EMST) for applications whose input N points are uniformly or boundedly distributed in the Euclidean space. The sequential approach takes O(N) time complexity through combining Boruvka's algorithm with an improved component-based neighborhood search algorithm, namely sliced spiral search, which is a newly proposed improvement of Bentley's spiral search for finding a component graph's closest outgoing point on 2D plane. We also propose a k-d search technique to extend this kind of search into 3D space. The data parallel approach includes a newly proposed two direction breadth-first search (BFS) implementation on graphics processing unit (GPU), which is aimed for selecting a spanning tree's shortest outgoing edge. The GPU parallel approaches assign N threads with one thread associated to one input point, one thread occupies 0(1) local memory and the whole algorithm occupies O(N) global memory. Experiments are conducted on point set of both uniformly distributed data sets and TSPLIB database. We evaluate computation time of the proposed approaches on more than 40 benchmarks with size N growing up to 10~5 points.