We implement a parallel graph processing library in C++ for computing minimum spanning trees on large static graphs, with OpenMP and CUDA backends. We benchmark edge-parallel Borůvka's algorithm across a diverse suite of graph types and sizes, and explore graph decomposition strategies to optimally assign subgraphs to the appropriate compute backend.
| Date | Task |
|---|---|
| Mar 29 | Project structure + build system |
| Apr 1 | Templated graph primitives with C++20 concepts |
| Apr 5 | Benchmark graph generator with visualization |
| Apr 8 | Baseline Kruskal + OpenMP Borůvka |
| Apr 8 | Batch benchmark, CSR graph variant |
| Apr 9 | Batch benchmark, atomic union-find |
| Apr 10 | VTune benchmark, reduced contention through path halving |
| Apr 12 | Research on reducing contraction contention |
| Apr 16 | Sparse + dense CUDA implementation |
| Apr 20 | Finalize all strategies + start on varying weights test |
| Apr 22 | Graph decomposition based on subgraph density |
| Apr 24 | Subgraph scheduling |
| Apr 28 | Finish all benchmarks + final report progress check |
| Apr 30 | Finish final report |
✓ Completed ◯ Upcoming