A C++ kernel study with a side-by-side build, raw benchmark logs, and an independent correctness check.
| What | Link |
|---|---|
| Repository | https://github.com/rohaan2802/SPMV_Optimization |
| GitHub Pages | https://rohaan2802.github.io/SPMV_Optimization/ |
| Benchmark comparison CSV | https://rohaan2802.github.io/SPMV_Optimization/results/comparison.csv |
- Overview
- Interactive Demo
- What’s Inside
- Project Breakdown
- Folder Structure
- Setup
- Results
- Limitations
- Screenshots
- About the Author
This CS-2008 Numerical Computing project evaluates four-way loop unrolling in the sparse matrix–vector multiplication (SpMV) kernel of HPCG 3.1. Each row calculates one dot product y[i] from the stored coefficients and the corresponding entries of x. HPCG generates a sparse linear system from a three-dimensional 27-point stencil. The original input uses a 104 × 104 × 104 grid, producing 1,124,864 equations and 29,791,000 nonzeros. The input file defines the dataset, so no external matrix download is required.
Open index.html locally and select Demo in the navbar. The demo models the row for a grid point at the lower boundary for each constrained axis.
| Grid position | Active entries | Groups of four | Scalar tail |
|---|---|---|---|
| Interior | 27 | 6 | 3 |
| Face | 18 | 4 | 2 |
| Edge | 12 | 3 | 0 |
| Corner | 8 | 2 | 0 |
Choose All ones to see how the diagonal and neighbors cancel for an interior row. Choose Increasing values to inspect an input where individual products vary across the three slices. Both accumulation paths evaluate the same row. See the C++ kernel for the full implementation and browser demo source for the row model.
| File | Purpose |
|---|---|
| index.html | Project walkthrough, stencil demo, benchmark comparison, and gallery |
| tools/compare_runs.py | Validates matching HPCG reports and gives medians, ranges, and percent changes |
| src/compute_spmv_unrolled.cpp | Maintained four-accumulator kernel |
| third_party/hpcg/src/ComputeSPMV_ref.cpp | Independent upstream reference |
| data/hpcg.dat | Original 104 × 104 × 104 input and 60-second target |
| results/comparison.csv | Five metrics extracted from the two original logs |
| results/original/HPCG-Benchmark_3.1_2025-12-07_19-41-10.txt | Original baseline run |
| results/original/HPCG-Benchmark_3.1_2025-12-07_20-49-54.txt | Original unrolled run |
| results/local_checks/baseline_16cube.txt | Current baseline validity check |
| results/local_checks/unrolled_16cube.txt | Current unrolled validity check |
| tests/spmv_test.cpp | Row equivalence check across all HPCG row lengths |
| docs/full_report.pdf | Project methodology and discussion |
| docs/summary_report.pdf | Short project report |
| docs/presentation.pptx | Original presentation deck |
| archive/README.md | Submitted patch, earlier runs, and audit notes |
HPCG stores a pointer to each row’s coefficients, a pointer to its local column indices, and a count of the active entries. Boundary rows have 8, 12, or 18 entries. Interior rows have 27. The inner loop performs indirect reads from x, and work is proportional to the number of nonzeros.
The scalar loop accumulates into one running total. The optimized loop processes four entries per iteration with four separate partial sums. It then combines those sums and handles the last zero to three entries with a scalar loop. The matrix layout and the number of products remain the same. The changed addition order can introduce small floating-point differences.
The maintained build selects the implementation at ComputeSPMV and keeps the upstream ComputeSPMV_ref intact. This preserves an independent scalar reference for HPCG's internal checks. The original submission changed ComputeSPMV_ref itself, and that version is archived. The technique was inspired by research on vectorizing SpMV. It uses scalar source operations and makes no assumption about which SIMD instructions a compiler emits. The full report gives the course paper discussion. The upstream notes identify the source commit and license.
SPMV_Optimization/
├── CMakeLists.txt Baseline, unrolled, and CTest targets
├── src/ Maintained kernel and portable timer
├── third_party/hpcg/ Pinned reference benchmark and notices
├── tests/ Direct kernel comparison
├── data/ Original workload specification
├── results/ Original logs, comparison, local checks
├── docs/ Reports, assignment, and slides
├── archive/ Submitted source and earlier experiments
├── tools/ Figure and results extraction
├── assets/ Site code and screenshot gallery
└── index.html GitHub Pages entry point
Use CMake 3.16 or newer, Ninja and a C++17 compiler. The commands build single-rank, single-thread Release executables. On Windows use a configured C++ toolchain, such as MSYS2 UCRT64 GCC with its bin directory on PATH. On Linux or WSL use GCC or Clang.
cmake -S . -B build -G Ninja -DCMAKE_BUILD_TYPE=Release
cmake --build build
ctest --test-dir build --output-on-failure# Linux or WSL, from the repository root
mkdir -p run/baseline run/unrolled
(cd run/baseline && ../../build/xhpcg_baseline --nx=16 --ny=16 --nz=16 --rt=1)
(cd run/unrolled && ../../build/xhpcg_unrolled --nx=16 --ny=16 --nz=16 --rt=1)# PowerShell, from the repository root
New-Item -ItemType Directory -Force run/baseline,run/unrolled | Out-Null
Push-Location run/baseline
& ../../build/xhpcg_baseline.exe --nx=16 --ny=16 --nz=16 --rt=1
Pop-Location
Push-Location run/unrolled
& ../../build/xhpcg_unrolled.exe --nx=16 --ny=16 --nz=16 --rt=1
Pop-LocationFor the original workload, copy data/hpcg.dat into each run directory and invoke the same executable there without flags. Keep runs in separate directories to retain both logs. Use the 16³ case first for a quick check. The report is written in the working directory. Look for Final Summary::HPCG result is VALID and inspect the convergence, symmetry, iteration-count and reproducibility fields.
Install matplotlib, numpy and pillow in a Python environment and run python tools/build_figures.py. The generator reads the two original reports, writes the comparison CSV, and regenerates the 24 named figures. Open index.html in a browser to explore them.
| Metric | Baseline | Unrolled | Change |
|---|---|---|---|
| SpMV time | 24.6904 s | 24.4821 s | −0.84% |
| Raw SpMV rate | 0.123072 GFLOP/s | 0.124118 GFLOP/s | +0.85% |
| Total runtime | 157.837 s | 165.699 s | +4.98% |
| Final HPCG rating | 0.130700 GFLOP/s | 0.124442 GFLOP/s | −4.79% |
| Multigrid time | 128.491 s | 136.293 s | +6.07% |
The original December 2025 logs used one rank and one thread on Ubuntu under WSL on an Intel Core i5-5300U. Both logs show VALID and the same raw SpMV operation count. The selected pair shows a small improvement in the kernel and a lower overall score. Multigrid is the largest component in both logs and took longer in the unrolled run.
The comparison tool takes an equal number of complete, valid HPCG reports for each build. It checks grid dimensions, rank and thread counts, nonzero count, and raw SpMV operation count before computing medians and observed ranges. Use matching compiler flags, duration, machine, and process affinity. Alternate run order when collecting repeats. One pair gives no estimate of timing spread.
python tools/compare_runs.py \
--baseline results/original/HPCG-Benchmark_3.1_2025-12-07_19-41-10.txt \
--candidate results/original/HPCG-Benchmark_3.1_2025-12-07_20-49-54.txtPass additional filenames after each option for repeated runs. Output is CSV and can be redirected to a file. A negative change in seconds means a shorter runtime, while a positive change in GFLOP/s means higher throughput.
The current Windows Release build was checked independently. CTest compared mixed-sign row products over 0–27 entries with the upstream reference and measured a maximum absolute difference of 3.10862e−15. Both current binaries reported VALID on 16³, passing convergence, symmetry, iteration-count, and reproducibility checks. Those short runs verify execution and correctness.
The archived performance comparison consists of one selected pair on one machine. It has no repeated-run variance estimate, and the short duration does not qualify for an official HPCG submission. The current Windows checks use a smaller problem, a different timer and toolchain, and a corrected entry point. MPI, OpenMP, and 104³ performance of the maintained build were outside those checks.
The center coefficient is 26. Neighbor coefficients are −1. Grid boundaries trim the stencil.
HPCG generates the sparse system from these dimensions and the configured run duration.
The original baseline log records the expected grid size and number of nonzeros.
Counts are derived from the submitted 104³ grid. Interior rows dominate the workload.
The two pointer arrays locate coefficients and local column indices for each row.
The upstream kernel adds each product to a single running total.
Each iteration computes four products while retaining HPCG’s original matrix layout.
After reduction, the tail handles the entries left by the unrolled loop.
The maintained kernel is installed at ComputeSPMV, keeping ComputeSPMV_ref available for checks.
Both executables link the same core. The selected ComputeSPMV implementation differs.
The measured SpMV time fell 0.84% in the selected pair of original runs.
Raw SpMV throughput increased 0.85% in the selected pair.
The whole benchmark took 4.98% longer in the unrolled run.
The reported overall rating fell 4.79% even as raw SpMV throughput rose.
Multigrid time is a separate benchmark measure and dominates the runtime in these logs.
The same operation count lets the two raw SpMV rates be compared directly.
The baseline log reports a valid result for the original run.
The optimized log reports a valid result for the original run.
Both original logs report 50 reference and 50 optimized iterations.
Saved values from the benchmark’s scaled symmetry check.
The local CTest compares mixed-sign row products with zero to 27 entries, covering every tail length.
The original measurements were captured on this WSL host with one benchmark thread.
The baseline and unrolled binaries share the same Release build and run in separate working directories.
One measured pair shows a small kernel improvement alongside a lower overall HPCG rating.
Mohammad Rohaan and Ahmed Abdullah completed the original HPCG optimization study for CS-2008 Numerical Computing. Mohammad Rohaan maintains this repository. GitHub profile