PHEM-MST

This is a code to obtain the MST of a graph using CPU and GPU. You can use only the GPU version or the CPU version or PHEM(both) or the unified memory version.

The cpu code is essentially the PBBS implementation.

The GPU code is completely written by me. It is a GPU version of CPU multi-threaded implementation discussed in thesis by W.Zhou.

The standalone gpu repo can be found here

I wanted to use the GPU version of this model which relies on atomics and it surprisingly performed well. I also could not find any implementation which takes in the input graph as a .mtx file and most methods usually use either binaries or CSR graphs.

The closest work i found was ECL-MST but they dont add the time to convert the graph to a .egr binary or the time to transfer the graph to the GPU.

This current work overlaps data transfer with compute kernels and more importantly can work with out of memory graphs (i.e. graphs that dont fit in the GPU memory 🤯). Well it is done because the MST/MSF can be found iteratively and generally the number of nodes (n) in a graph is much less than the number of edges (e) and we only need to transfer O(n) to compute the MST/MSF for the chunk.

Work is accepted and is set to be presented in ICPP-Grand 2025. Will update the manuscript here too.

Build Instructions:

nvcc -Xcompiler -fopenmp -std=c++17 -extended-lambda -lcudart main.cu -o mst

Usage:

./mst --filename <input_file> --result-file <output_file> [options]
Options:
  --debug                         Enable debug mode
  --generate-random-weights       Generate random weights for edges
  --use-malloc-managed           Use CUDA managed memory
  --use-streamline               Use streamline processing
  --use-cpu-only                 Use CPU-only processing
  --cpu-gpu-streamline           Use CPU-GPU streamline
  --save-weighted-graph          Save the weighted graph
  --chunk-size <size>            Chunk size (default: 100)
  --num-chunks-ideal <num>       Number of ideal chunks (default: 1)

Example Usage:

GPU Streams only run for 4 chunks:

CUDA_MODULE_LOADING=EAGER ./mst --filename /path/to/graph.mtx --result-file out.txt --generate-random-weights --use-streamline --num-chunks-ideal 4

PBBS impl only run:

./mst --filename /path/to/graph.mtx --result-file out.txt --generate-random-weights --use-cpu-only

Unified Memory run:

./mst --filename /path/to/graph.mtx --result-file out.txt --generate-random-weights --use-malloc-managed

PHEM Run for 4 chunks:

CUDA_MODULE_LOADING=EAGER ./mst --filename /path/to/graph.mtx --result-file out.txt --generate-random-weights --cpu-gpu-streamline --num-chunks-ideal 4

Get help:

./mst --help