Since proposal approval, we have built out the foundational components of the project. We selected the human PPI network from BioGRID as our primary dataset and built a graph loading pipeline that parses the raw interaction data into a clean, deduplicated edge list. We represent the graph in CSR (compressed sparse row) format, chosen because it provides good cache locality for neighbor iteration during BFS and is the standard choice for sparse graph workloads.
We have completed a serial implementation of Brandes' algorithm and verified its correctness by comparing its output against a NetworkX reference on small test graphs — centrality scores match within floating-point tolerance. Alongside the implementation, we built a benchmarking framework that handles warm-up runs, multiple trials, and consistent output formatting, which will let us collect reliable timing data across all configurations we plan to compare. We have also begun initial profiling of the serial baseline to understand the distribution of BFS costs across source vertices, which will inform our load balancing work in the next phase.
We are on track with the schedule outlined in our proposal and believe we will be able to produce all of our core deliverables. The MVP — serial Brandes', static source-parallel, dynamically-scheduled source-parallel, and a hybrid version that parallelizes within BFS for high-degree sources — remains fully achievable. The source-parallel variants are natural extensions of the serial code we have now finished, and the main intellectual work (analyzing load imbalance and designing the hybrid) falls directly out of the experiments we plan to run in the coming weeks.
For the stretch goals, we are being realistic about what is reachable. Fine-grained BFS parallelism and lock-free accumulation remain plausible since they build directly on the MVP code. A CUDA implementation and graph reordering experiments are more ambitious, and we are treating them as aspirational rather than planned.
Correct serial Brandes', static source-parallel OpenMP, dynamically-scheduled source-parallel, and a hybrid version that switches to intra-BFS parallelism for high-degree sources. Speedup and runtime graphs across thread counts and at least two graph sizes. An analysis of how power-law degree distributions in PPI networks create load imbalance, and how our scheduling strategies address it.
Lock-free or atomic-based accumulation of dependency scores as an alternative to per-thread accumulators, with a comparison of their overhead. Results on multiple PPI datasets (BioGRID human, STRING, yeast) to show how graph density affects scaling.
We plan to present speedup graphs showing how each of our parallel implementations scales with thread count on different PPI datasets, along with a breakdown of execution time showing how much is spent in BFS traversal versus dependency accumulation. We will also include visualizations of load imbalance — per-thread work distribution — to motivate our hybrid approach.
We have initial serial timing measurements on the BioGRID human PPI network and have started collecting per-source BFS cost data. Early profiling confirms what we expected from the graph's degree distribution: a small number of hub vertices contribute disproportionately to total BFS runtime, which will make load balancing a meaningful problem to solve.
Our main open question is how large the gap will be between static and dynamic scheduling on real PPI data. If the imbalance from hub vertices is smaller than expected on our chosen datasets, the hybrid approach may not yield a dramatic improvement, which would make the analysis less interesting. To hedge against this, we plan to test on multiple datasets with varying density. Beyond this, we do not see any blockers we cannot work through, and most of what remains is focused implementation and experimentation work.
| Window | Goals |
|---|---|
| Apr 15 – Apr 17 | Finalize profiling of the serial baseline and lock in the BFS cost distribution data (Vera). Begin static source-parallel OpenMP implementation (Tanishqa). |
| Apr 18 – Apr 21 | Finish static source-parallel version and measure initial speedup (Tanishqa). Begin dynamically-scheduled source-parallel version and compare against static (Vera). |
| Apr 22 – Apr 25 | Finish dynamic scheduling variant and begin hybrid version that parallelizes within BFS for high-degree source vertices (paired). Begin structured data collection across thread counts and graph sizes. |
| Apr 26 – Apr 28 | Run full experiments varying graph size, thread count, and dataset (Vera). Generate speedup graphs and analyze bottlenecks (Tanishqa). Begin drafting the final report. |
| Apr 29 – Apr 30 | Attempt stretch goals if time allows (lock-free accumulation or fine-grained BFS parallelism). Finalize analysis, complete report, and prepare poster materials (paired). |