Checkpoint Report:
Parallel Minimum Spanning Tree
Main Project Page

Current Progress

I'm approximately half a week behind, because of Carnival and because building a testing framework was far more work than I expected. I still want to write a GPU implementation, particularly because I think the types of algorithms that will work will change dramatically on the GPU, but I'm no longer sure I can get too it.

Preliminary Results

My preliminary results are about a 2-3x speedup for Kruskal's algorithm on 6 cores, with a max theoretical speedup of around 4-6x. This is because the initial sort of all edges by weight parallelizes well and is the majority of the runtime, but the rest of the algorithm is completely sequential.

Potential Roadblocks

There are no external roadblocks to my completing this project, but getting good speedup is going to be more challenging than I expected. Primarily, I'm fighting against two facts:
  1. Manipulating edge sets is hard to do efficiently.
  2. When you split a random graph into equal-size pieces, most of the edges go between two different pieces.
The first fact is a problem because the standard algorithms for MST (i.e. Prim's and Kruskal's) have found ways to avoid working with edge sets too much, so any algorithm I write has to avoid them too or it won't be work-efficient. The second fact makes partitioning graphs largely impractical, because every edge between partitions is a potential synchronization point. I have some ideas for combating these problems, but whether they'll be effective or not remains to be seen.