ECL-MST v1.0

ECL-MST is a fast CUDA implementation for computing a minimum spanning tree (MST) or a minimum spanning forest (MSF) of an undirected graph. It operates on graphs stored in binary CSR format. Converters to this format and several pre-converted graphs can be found here.

Click on ECL-MST_10.cu and ECLgraph.h to download the CUDA code. Alternatively, the code is also available on github. See the paper listed below for a description of ECL-MST. Note that ECL-MST is protected by the 3-Clause BSD license.

The code can be compiled as follows:

To compute the MST of the file graph.egr, enter:

Publication

Alex Fallin, Andres Gonzalez, Jarim Seo, and Martin Burtscher. "A High-Performance MST Implementation for GPUs." Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. Article 77, pp. 1-13. November 2023. [doi] [pdf] [pptx] [talk]

Summary: ECL-MST is an efficient parallel Minimum Spanning Tree code for GPUs. Its edge-centric, data-driven implementation avoids the sorting of edges based on the observation that the minimum element of a list is the same regardless of whether the list is sorted or not. Our implementation demonstrates how a massive parallelization of Kruskal's algorithm converges to that of Boruvka's algorithm, which allows multiple edges to be concurrently included in the MST. The judicious use of atomic operations makes ECL-MST lock-free and fast. Among other optimizations, implicit path compression in the union-find data structure, primarily edge-based processing, and a hybrid parallelization between thread and warp computation allow ECL-MST to achieve large performance gains over state-of-the-art MST codes for GPUs.

This work has been supported in part by the National Science Foundation under Award Number 1955367 and by an equipment donation from NVIDIA Corporation.