Sample 3 - Thesis kickoff — heavy weight perfect matching on the GPU

The thesis is titled "Implementing the Heavy Weight Perfect Matching Algorithm for Bipartite Graphs on the GPU". This first entry sets the scope.

The problem

Given a bipartite graph G = (U ∪ V, E) with edge weights w(u, v), find a perfect matching that maximises total weight. The classical exact solutions — Hungarian / Kuhn–Munkres, and auction-based methods — are inherently sequential in their augmenting-path phase, which is exactly the part that dominates runtime on large sparse instances.

Why GPUs are awkward here

• Augmenting paths are irregular pointer chases: poor coalescing, heavy warp divergence.
• The active frontier shrinks over iterations, so occupancy collapses late in the run.
• Dual price updates are global reductions interleaved with sparse scatter writes.

Plan of attack

1. Build a correct CPU baseline (auction algorithm with ε-scaling) to validate against.
2. Port the bidding phase first — it is embarrassingly parallel over unmatched vertices.
3. Attack the assignment phase with atomics, then compare against a sort-based reduction.
4. Profile with Nsight Compute at each step; record occupancy, achieved bandwidth, and warp stall reasons.

Test instances

Instance family	|U|	Avg degree	Notes
Random sparse	1e5	16	Uniform weights
Power-law	1e5	12	Heavy hub vertices
SuiteSparse	varies	varies	Real-world matrices

Next entry: the CPU baseline and the first naive CUDA bidding kernel.