GPU Based Fast Minimum Spanning Tree

Usage

1. Random Connected Graph Generation

   $ g++ random_graph_generator.cpp -o graph
   $ ./graph > graph2p14
   16384
   

2. MST Serial

   $ g++ mst_serial.cpp -o serial
   $ ./serial < graph2p14
   

3. MST Serial BGL

   $ g++ mst_serial_bg;.cpp -o bgl
   $ ./bgl < graph2p14
   

4. Parallel CUDA code

   $ nvcc mst.cu -o mst
   $ ./mst < graph2p14
   

Results

Files

• mst.cu - CUDA code for parallel implementation of Prim's algorithm for MST
• mst_serial_bgl.cc - Serial code for Prim's MST using Boost Graph Library
• mst_serial.cc - Serial code for Prim's MST using Priority Queue
• random_graph_generator.cpp - Creation of random connected Graph

References

Papers

• GPU_based_mst.pdf
• GPU_based_prims.pdf