Distributed PageRank in C++ over a 916K-node, 5.1M-edge web graph, scaled to 256 processes on an HPC cluster. Profiling showed that 89% of the runtime was communication. We restructured the distributed sparse matrix–vector multiply (SpMV) to move the costly setup exchanges out of the iteration loop, then added an MPI + OpenMP hybrid on top.
Results:
- Up to 20× faster than the baseline MPI implementation at the same process count. It is still 4× faster at 256 processes.
- Wall-clock time falls from about 2 minutes (baseline, 1 process) to under 0.4 s (optimized, 64 processes).
- A persistent OpenMP thread team gives a further 15–20% on long runs.
By Alekh Pandey and Brodie Witkowski, Parallel Processing course, University of New Mexico, Fall 2025.
PageRank is the stationary distribution of a random surfer on a directed graph. It is computed by power iteration:
where
Dataset: SNAP/web-Google, the 2002 Google web graph (916,428 nodes, 5,105,039 edges). All ranks read it in parallel from a PETSc binary file into a row-distributed CSR matrix.
In the baseline, every iteration of the distributed SpMV performed three all-to-all exchanges:
MPI_Alltoallto exchange counts (how many vector entries each rank needs from each other rank)MPI_Alltoallto exchange indices (which entries)MPI_Alltoallvto exchange the values themselves
The sparsity pattern never changes between iterations, so steps 1 and 2 give the same answer every time.
We moved the count and index exchanges out of the loop and computed the communication plan once. Each iteration now performs only the value exchange plus two scalar MPI_Allreduces, one for the dangling-node sum and one for the convergence check.
flowchart LR
subgraph Baseline["Baseline: every iteration"]
direction TB
A1[Alltoall: counts] --> A2[Alltoall: indices] --> A3[Alltoallv: values] --> A4[Local SpMV] --> A5[Allreduce: dangling sum + convergence]
end
subgraph Optimized["Optimized"]
direction TB
B0["Once: Alltoall counts + indices<br/>(build comm plan)"] --> B3
subgraph Loop["every iteration"]
B3[Alltoallv: values] --> B4[Local SpMV] --> B5[Allreduce: dangling sum + convergence]
end
end
The optimized version is up to 20× faster at low process counts and still 4× faster at 256. It scales well up to 64 processes. Beyond that, the per-process work becomes so small that the remaining collective communication dominates, and runtime starts to rise again.
We compared two OpenMP strategies for the local SpMV and vector updates:
| Strategy | Approach |
|---|---|
| Inner parallel-for | #pragma omp parallel for inside each iteration, which forks and joins a thread team every time |
| Persistent team | A single #pragma omp parallel region outside the iteration loop; the threads are reused across iterations and synchronized with barriers, with MPI_THREAD_FUNNELED |
We then swept hybrid layouts at a fixed 256 execution units, from 2 processes × 32 threads up to 32 processes × 2 threads per node.
| ~70 iterations (normal convergence) | 1000 iterations (forced) |
|---|---|
 |
 |
Findings:
- The persistent team wins: 1–5% faster at about 70 iterations, and 15–20% faster at 1000 iterations once the fork/join overhead adds up.
- More MPI processes beat more threads. Trading processes for threads raises the communication volume per process, and since PageRank is communication-bound, that outweighs the faster computation.
- The best configuration was 32 processes per node × 2 threads, with a persistent team.
Restructuring the communication gives most of the speedup. The hybrid version improves on it a little further, which fits with PageRank on this graph converging in few iterations with little computation per iteration.
.
├── CMakeLists.txt
├── c/
│ ├── libs/
│ │ ├── reader.cpp # Parallel PETSc-binary reader → distributed CSR
│ │ ├── mat_op.cpp # Distributed SpMV, baseline + optimized PageRank
│ │ ├── openmp_mat_op.cpp # Hybrid kernels: parallel-for + persistent-team
│ │ └── my_time.cpp # Timer
│ └── src/
│ ├── page_rank.cpp # → page_rank (baseline MPI)
│ ├── page_rank_mod.cpp # → mod_page_rank (optimized MPI)
│ ├── openmp_page_rank.cpp # → openmp_page_rank (hybrid, parallel-for)
│ ├── openmp_page_rank_mod.cpp # → enhanced_openmp_page_rank (hybrid, persistent team)
│ └── spmv_example.cpp
├── python/
│ ├── convert_mtx_fast.py # Matrix Market → PETSc binary (.pm), transposed for PageRank
│ └── grapher.py # Plots scaling results
├── data/small.{mtx,pm} # Small test graph
├── pagerank1.sh, thread_page_rank.sh # Sample Slurm job scripts
└── docs/images/ # Result figures
Requirements: a C++11 compiler, CMake ≥ 3.12, an MPI implementation (OpenMPI tested), and OpenMP.
mkdir -p build && cd build
cmake .. && make -jPrepare a graph. Download web-Google.mtx from SuiteSparse into data/, then convert it to PETSc binary. Edit the paths at the bottom of the script first.
pip install -r requirements.txt
cd python && python convert_mtx_fast.pyRun. Executables look up the file name under data/. Usage: <exe> <file.pm> [tolerance=1e-4] [max_iters=100].
mpirun -n 4 ./build/page_rank small.pm # baseline
mpirun -n 4 ./build/mod_page_rank small.pm # optimized MPI
OMP_NUM_THREADS=2 mpirun -n 4 ./build/enhanced_openmp_page_rank small.pm 1e-4 100 # hybridOn a Slurm cluster, see thread_page_rank.sh for the hybrid job setup (--ntasks-per-node=32 --cpus-per-task=2, OMP_PROC_BIND=close). Experiments were run on UNM CARC's Easley cluster.
- Store the matrix in CSC, which fits the column-oriented (source → destination) structure of PageRank
- One-sided MPI (RMA) communication to overlap or remove the per-iteration
Alltoallv - Larger graphs, where the computation share is bigger and the OpenMP gains should be larger