Checkpoint Report:

Parallel Minimum Spanning Tree

## Current Progress

- Wrote graph I/O functions for two formats (binary and text)
- Wrote random graph generators for several types of graphs:
- Uniform random graphs
- Sparse (but connected) random graphs
- Random planar triangulations
- Random regular graphs
- Hypercubes

- Wrote a sequential implementation of Kruskal's algorithm (along with
union-find)
- Wrote two parallel sorts using pthreads (mergesort and samplesort)
- Trivially parallelized Kruskal's algorithm by parallelizing the
sorting phase

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:

- Manipulating edge sets is hard to do efficiently.
- 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.