A GPU-accelerated implementation of Minimum Spanning Tree/Forest using CUDA streams to overlap data transfer and execution, enabling computation on graphs that exceed GPU VRAM.
This implementation addresses GPU memory limitations by processing graphs in chunks using CUDA streams. When graphs exceed available GPU memory, the mst can be computed by splitting the graph into smaller chunks that fit within memory constraints. CUDA streams enable overlapping of data transfers (CPU ↔ GPU) with kernel execution, allowing computation on one chunk while simultaneously transferring data for subsequent chunks. This streaming approach maximizes GPU utilization and enables processing of arbitrarily large graphs without running out of memory. Standalone gpu version of PHEM work to be published in icpp grand. Work inspired by multicore version (Zhou) which I wrote in cuda. Wanted to check out the performance of cuda atomics in newer machines and was performing decently. Code can run for very large graphs too(assuming vertex set can fit onto device). Ran till Agatha and moliere graphs on DGX, work could be extended for multi-gpu scenarios too.
Work presented in ICPP - GRAND
nvcc main.cu -arch=sm_75 -Xcompiler -fopenmp -extended-lambda -lcudart -o mst
./mst --filename <input_file> --result-file <output_file> [options]NOTE: You may need to tweak the arch and ccbin flag (-ccbin /usr/bin/g++-15) for certain hardware like DGX/L4. Feel free to raise issue if you have trouble running the program.
-ccbin /usr/bin/g++-15 (or whichever g++ your CUDA release supports) is required on distros that ship a default gcc newer than your CUDA toolchain's supported host compiler (e.g. Fedora 44 ships gcc 16, but CUDA 13.3 only supports up to gcc 15) — nvcc will otherwise fail with a #error -- unsupported GNU version!. If your default gcc/g++ is already within range, you can drop that flag.
--filename <input_file>: Path to the input graph file--result-file <output_file>: Path to save the MST results
--gpu-only: GPU stream processing (the default mode; this flag is just an explicit, self-documenting alias for it)--gpu-monolithic: Transfer the entire graph to the device at once instead of chunking/streaming--cpu-only: Force CPU-only processing (for verification)--num-chunks-ideal <num>: Only relevant to the default (--gpu-only) streaming mode. The edge list is split into roughly this many chunks (default: 4), each transferred to the GPU and processed in turn, with the next chunk's transfer overlapping the current chunk's compute via CUDA streams. This is the right approach when a graph is too large to fit on the GPU at once: the resident GPU memory footprint scales as O(num_nodes) + O(chunk_size), not O(num_edges) — every per-vertex structure (representatives, MSF, outgoing-edge tracking) is sized to the node count only, which is fixed regardless of how many edges the graph has, and only one chunk's worth of edges is ever resident on the device at a time (the rest stay in host memory until their turn). Raising--num-chunks-idealshrinkschunk_sizeand lets you fit graphs whose full edge list would never fit in VRAM. Lower it (or use--gpu-monolithic, which needs the full O(num_edges) memory up front) only if the graph already fits comfortably and you want to minimize per-chunk overhead.--generate-random-weights: Generate random weights for edges--save-weighted-graph: Save the weighted graph toweighted.mtxand exit--use-malloc-managed: Use CUDA unified memory for the monolithic path instead of explicit transfers--cpu-gpu-streamline: Hybrid mode — runs CPU MST on the last chunk concurrently with GPU chunk streaming. Highest priority; overrides--cpu-only/--gpu-monolithic/--use-malloc-managed. (Benchmarked as consistently slower than plain--gpu-onlyon every graph size tried so far — kept as an available mode, not recommended by default.)--verbose: Print per-iteration/per-chunk progress (default: only the final summary is printed)
The program outputs:
- Processing configuration details
- Input/output file paths
- Number of chunks and processing mode
- Completion status message
- MST results written to the specified result file
To verify GPU results against CPU implementation:
-
Run GPU Streams version: Compute mst by calculating chunk by chunk and iteratively finding the final msf. Data transfer streams overlap with kernel execution streams.
./mst --filename input.mtx --result-file gpu_result.txt
-
Run GPU single chunk (monolithic) version: Compute mst by transferring entire edgelist to device and compute and transfer back
./mst --filename input.mtx --result-file gpu_monolithic_result.txt --gpu-monolithic
-
Run CPU verification: Run the PBBS suite mst implementation
./mst --filename input.mtx --result-file cpu_result.txt --cpu-only
-
Compare results:
sort gpu_result.txt > sorted_gpu.txt sort cpu_result.txt > sorted_cpu.txt diff sorted_cpu.txt sorted_gpu.txt
NB: This would only work if there is a unique MST/MSF. Otherwise, a weight comparison and node coverage method would be required.
The MST weights should be identical between GPU and CPU implementations.
The data required is in a .mtx format, no need for any binary conversion etc. For example to calculate for (cnr-2000). Download the .mtx file and run
./mst --filename cnr-2000.mtx --result-file gpu_result.txt --generate-random-weights #For streams approach
./mst --filename cnr-2000.mtx --result-file gpu_result_monolithic.txt --generate-random-weights --gpu-monolithic #For single chunk(monolithic) approach
./mst --filename cnr-2000.mtx --result-file cpu_result.txt --generate-random-weights --cpu-only #For pbbs cpu approach- Default configuration optimized for GPU streams processing
- Uses CUDA streams for overlapping computation and memory transfers
- Chunk-based processing for handling large graphs efficiently
CUDA_MODULE_LOADING=EAGERis set automatically; no need to export it yourself- Pass
--verboseif you want the detailed per-iteration/per-chunk progress log; by default only the final summary (execution time, total weight) is printed
Speedup of this approach (PHEM-MST) over ECL-MST and a CUDA Unified Memory (UVM) baseline. Note that ECL-MST does not fit onto the GPU for the ML and AG graphs, so no comparison point exists for those cases.
If you use this code, please cite:
@inproceedings{10.1145/3750720.3757291,
author = {Venkatachalam, Lokesh and Kothapalli, Kishore and Sahu, Abhijit and Ramakrishna, Gadhamsetty and Banerjee, Dip Sankar and Pedapudi, Balavarun and Harikrish, Aditya and Andaluri, Aditya S P Vm},
title = {PHEM: A Computational Model for Designing Parallel Algorithms for Very Large Graphs},
year = {2025},
isbn = {9798400721090},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3750720.3757291},
doi = {10.1145/3750720.3757291},
abstract = {Efficient algorithms for graph connected components and minimum spanning tree (mst) computations are vital in diverse domains, from medical diagnostics to chip design. Yet, as graph sizes grow to billions of edges, existing approaches often fail due to limited device memory. This challenge demands innovative rethinking of both algorithmic design and implementation strategies.We address this need by presenting a novel Parallel Heterogeneous External Memory (phem) framework, which harnesses both multicore cpu and gpu resources to tackle large-scale graph processing. Our method minimizes communication overhead while maximizing computational throughput through efficient copy- computation strategies. Experiments on a variety of real-world and synthetic benchmarks demonstrate that our algorithms for connected components and minimum spanning tree in the phem model outperform current state-of-the-art solutions, significantly advancing the capability to process massive graphs.},
booktitle = {Workshop Proceedings of the 54th International Conference on Parallel Processing},
pages = {95–103},
numpages = {9},
keywords = {Minimum Spanning Forest, Connected Components, GPU computation, Heterogeneous computation},
location = {
},
series = {ICPP Workshops '25}
}