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 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:

nvcc -O3 -arch=sm_70 -o ecl-mst

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

./ecl-mst graph.egr


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.

Official Texas State University Disclaimer