<div align="center">

# HPCG SpMV Optimization

**A C++ kernel study with a side-by-side build, raw benchmark logs, and an independent correctness check.**

[![C++](https://img.shields.io/badge/C%2B%2B-17-2450a4?logo=cplusplus&logoColor=white&style=for-the-badge)](src/compute_spmv_unrolled.cpp)
[![HPCG](https://img.shields.io/badge/HPCG-3.1-405575?style=for-the-badge)](third_party/hpcg/UPSTREAM.md)
[![Input](https://img.shields.io/badge/Grid-104%20cubed-075E55?style=for-the-badge)](data/hpcg.dat)
[![Results](https://img.shields.io/badge/Results-CSV-2350a4?style=for-the-badge)](results/comparison.csv)
[![CTest](https://img.shields.io/badge/Checks-CTest-674B88?logo=cmake&logoColor=white&style=for-the-badge)](tests/spmv_test.cpp)
[![Gallery](https://img.shields.io/badge/Gallery-24%20figures-325567?style=for-the-badge)](#screenshots)

[![Interactive demo](https://img.shields.io/badge/Stencil-Interactive-195b49?logo=googlechrome&logoColor=white&style=for-the-badge)](#interactive-demo)
[![Report tool](https://img.shields.io/badge/Reports-Comparison-3b5667?logo=python&logoColor=white&style=for-the-badge)](tools/compare_runs.py)
[![Presentation](https://img.shields.io/badge/Project-Presentation-9d503b?logo=slides&logoColor=white&style=for-the-badge)](docs/presentation.pptx)
[![Verification](https://img.shields.io/badge/HPCG-Validation_logs-365539?logo=checkmarx&logoColor=white&style=for-the-badge)](results/local_checks/)

</div>

## Live Links

| What | Link |
| --- | --- |
| Repository | [https://github.com/rohaan2802/SPMV_Optimization](https://github.com/rohaan2802/SPMV_Optimization) |
| GitHub Pages | [https://rohaan2802.github.io/SPMV_Optimization/](https://rohaan2802.github.io/SPMV_Optimization/) |
| Benchmark comparison CSV | [https://rohaan2802.github.io/SPMV_Optimization/results/comparison.csv](https://rohaan2802.github.io/SPMV_Optimization/results/comparison.csv) |

## Contents

- [Overview](#overview)
- [Interactive Demo](#interactive-demo)
- [What’s Inside](#whats-inside)
- [Project Breakdown](#project-breakdown)
- [Folder Structure](#folder-structure)
- [Setup](#setup)
- [Results](#results)
- [Limitations](#limitations)
- [Screenshots](#screenshots)
- [About the Author](#about-the-author)

## Overview

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.

## Interactive Demo

Open [index.html](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](src/compute_spmv_unrolled.cpp) for the full implementation and [browser demo source](assets/js/stencil_demo.js) for the row model.

## What’s Inside

| File | Purpose |
| --- | --- |
| [index.html](index.html) | Project walkthrough, stencil demo, benchmark comparison, and gallery |
| [tools/compare_runs.py](tools/compare_runs.py) | Validates matching HPCG reports and gives medians, ranges, and percent changes |
| [src/compute_spmv_unrolled.cpp](src/compute_spmv_unrolled.cpp) | Maintained four-accumulator kernel |
| [third_party/hpcg/src/ComputeSPMV_ref.cpp](third_party/hpcg/src/ComputeSPMV_ref.cpp) | Independent upstream reference |
| [data/hpcg.dat](data/hpcg.dat) | Original 104 × 104 × 104 input and 60-second target |
| [results/comparison.csv](results/comparison.csv) | Five metrics extracted from the two original logs |
| [results/original/HPCG-Benchmark_3.1_2025-12-07_19-41-10.txt](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](results/original/HPCG-Benchmark_3.1_2025-12-07_20-49-54.txt) | Original unrolled run |
| [results/local_checks/baseline_16cube.txt](results/local_checks/baseline_16cube.txt) | Current baseline validity check |
| [results/local_checks/unrolled_16cube.txt](results/local_checks/unrolled_16cube.txt) | Current unrolled validity check |
| [tests/spmv_test.cpp](tests/spmv_test.cpp) | Row equivalence check across all HPCG row lengths |
| [docs/full_report.pdf](docs/full_report.pdf) | Project methodology and discussion |
| [docs/summary_report.pdf](docs/summary_report.pdf) | Short project report |
| [docs/presentation.pptx](docs/presentation.pptx) | Original presentation deck |
| [archive/README.md](archive/README.md) | Submitted patch, earlier runs, and audit notes |

## Project Breakdown

### Workload and memory access

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.

### Four-way unrolling and reduction

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.

### Integration and provenance

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](docs/full_report.pdf) gives the course paper discussion. The [upstream notes](third_party/hpcg/UPSTREAM.md) identify the source commit and license.

## Folder Structure

```text
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
```

## Setup

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.

```bash
cmake -S . -B build -G Ninja -DCMAKE_BUILD_TYPE=Release
cmake --build build
ctest --test-dir build --output-on-failure
```

### Smoke runs

```bash
# 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
# 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-Location
```

For 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.

### Rebuild the figures

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](index.html) in a browser to explore them.

## Results

### Original 104³ benchmark

| 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.

### Compare your own benchmark reports

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.

```bash
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.txt
```

Pass 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.

### Current local correctness checks

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.

## Limitations

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.

## Screenshots

[01](#1-a-27-point-stencil-in-three-slices) · [02](#2-the-original-benchmark-input) · [03](#3-a-million-equation-workload) · [04](#4-nonzeros-per-row-depend-on-location) · [05](#5-how-hpcg-stores-a-sparse-row) · [06](#6-the-scalar-reference-loop)

[07](#7-four-independent-accumulators) · [08](#8-the-scalar-remainder) · [09](#9-the-optimized-entry-point) · [10](#10-two-builds-from-one-source-tree)

[11](#11-spmv-time) · [12](#12-spmv-throughput) · [13](#13-total-runtime) · [14](#14-final-hpcg-rating) · [15](#15-multigrid-time) · [16](#16-both-runs-did-the-same-spmv-work)

[17](#17-baseline-log-validation) · [18](#18-unrolled-log-validation) · [19](#19-reference-and-optimized-iteration-counts) · [20](#20-spmv-departure-from-symmetry) · [21](#21-direct-numerical-equivalence-test) · [22](#22-the-recorded-benchmark-host)

[23](#23-build-and-verify-locally) · [24](#24-reading-the-timing-comparison)

### 1. A 27-point stencil in three slices

<p align="left"><a href="assets/screenshots/01_stencil.png"><img src="assets/thumbs/01_stencil.webp" alt="A 27-point stencil in three slices" width="900"></a></p>

The center coefficient is 26. Neighbor coefficients are −1. Grid boundaries trim the stencil.

### 2. The original benchmark input

<p align="left"><a href="assets/screenshots/02_input.png"><img src="assets/thumbs/02_input.webp" alt="The original benchmark input" width="900"></a></p>

HPCG generates the sparse system from these dimensions and the configured run duration.

### 3. A million-equation workload

<p align="left"><a href="assets/screenshots/03_dimensions.png"><img src="assets/thumbs/03_dimensions.webp" alt="A million-equation workload" width="900"></a></p>

The original baseline log records the expected grid size and number of nonzeros.

### 4. Nonzeros per row depend on location

<p align="left"><a href="assets/screenshots/04_boundary_rows.png"><img src="assets/thumbs/04_boundary_rows.webp" alt="Nonzeros per row depend on location" width="900"></a></p>

Counts are derived from the submitted 104³ grid. Interior rows dominate the workload.

### 5. How HPCG stores a sparse row

<p align="left"><a href="assets/screenshots/05_matrix_layout.png"><img src="assets/thumbs/05_matrix_layout.webp" alt="How HPCG stores a sparse row" width="900"></a></p>

The two pointer arrays locate coefficients and local column indices for each row.

### 6. The scalar reference loop

<p align="left"><a href="assets/screenshots/06_reference_loop.png"><img src="assets/thumbs/06_reference_loop.webp" alt="The scalar reference loop" width="900"></a></p>

The upstream kernel adds each product to a single running total.

### 7. Four independent accumulators

<p align="left"><a href="assets/screenshots/07_unroll.png"><img src="assets/thumbs/07_unroll.webp" alt="Four independent accumulators" width="900"></a></p>

Each iteration computes four products while retaining HPCG’s original matrix layout.

### 8. The scalar remainder

<p align="left"><a href="assets/screenshots/08_tail.png"><img src="assets/thumbs/08_tail.webp" alt="The scalar remainder" width="900"></a></p>

After reduction, the tail handles the entries left by the unrolled loop.

### 9. The optimized entry point

<p align="left"><a href="assets/screenshots/09_dispatch.png"><img src="assets/thumbs/09_dispatch.webp" alt="The optimized entry point" width="900"></a></p>

The maintained kernel is installed at ComputeSPMV, keeping ComputeSPMV_ref available for checks.

### 10. Two builds from one source tree

<p align="left"><a href="assets/screenshots/10_build_targets.png"><img src="assets/thumbs/10_build_targets.webp" alt="Two builds from one source tree" width="900"></a></p>

Both executables link the same core. The selected ComputeSPMV implementation differs.

### 11. SpMV time

<p align="left"><a href="assets/screenshots/11_spmv_time.png"><img src="assets/thumbs/11_spmv_time.webp" alt="SpMV time" width="900"></a></p>

The measured SpMV time fell 0.84% in the selected pair of original runs.

### 12. SpMV throughput

<p align="left"><a href="assets/screenshots/12_spmv_rate.png"><img src="assets/thumbs/12_spmv_rate.webp" alt="SpMV throughput" width="900"></a></p>

Raw SpMV throughput increased 0.85% in the selected pair.

### 13. Total runtime

<p align="left"><a href="assets/screenshots/13_total_time.png"><img src="assets/thumbs/13_total_time.webp" alt="Total runtime" width="900"></a></p>

The whole benchmark took 4.98% longer in the unrolled run.

### 14. Final HPCG rating

<p align="left"><a href="assets/screenshots/14_hpcg_rating.png"><img src="assets/thumbs/14_hpcg_rating.webp" alt="Final HPCG rating" width="900"></a></p>

The reported overall rating fell 4.79% even as raw SpMV throughput rose.

### 15. Multigrid time

<p align="left"><a href="assets/screenshots/15_multigrid.png"><img src="assets/thumbs/15_multigrid.webp" alt="Multigrid time" width="900"></a></p>

Multigrid time is a separate benchmark measure and dominates the runtime in these logs.

### 16. Both runs did the same SpMV work

<p align="left"><a href="assets/screenshots/16_same_work.png"><img src="assets/thumbs/16_same_work.webp" alt="Both runs did the same SpMV work" width="900"></a></p>

The same operation count lets the two raw SpMV rates be compared directly.

### 17. Baseline log validation

<p align="left"><a href="assets/screenshots/17_baseline_valid.png"><img src="assets/thumbs/17_baseline_valid.webp" alt="Baseline log validation" width="900"></a></p>

The baseline log reports a valid result for the original run.

### 18. Unrolled log validation

<p align="left"><a href="assets/screenshots/18_unrolled_valid.png"><img src="assets/thumbs/18_unrolled_valid.webp" alt="Unrolled log validation" width="900"></a></p>

The optimized log reports a valid result for the original run.

### 19. Reference and optimized iteration counts

<p align="left"><a href="assets/screenshots/19_iteration_counts.png"><img src="assets/thumbs/19_iteration_counts.webp" alt="Reference and optimized iteration counts" width="900"></a></p>

Both original logs report 50 reference and 50 optimized iterations.

### 20. SpMV departure from symmetry

<p align="left"><a href="assets/screenshots/20_symmetry.png"><img src="assets/thumbs/20_symmetry.webp" alt="SpMV departure from symmetry" width="900"></a></p>

Saved values from the benchmark’s scaled symmetry check.

### 21. Direct numerical equivalence test

<p align="left"><a href="assets/screenshots/21_test_rows.png"><img src="assets/thumbs/21_test_rows.webp" alt="Direct numerical equivalence test" width="900"></a></p>

The local CTest compares mixed-sign row products with zero to 27 entries, covering every tail length.

### 22. The recorded benchmark host

<p align="left"><a href="assets/screenshots/22_recorded_host.png"><img src="assets/thumbs/22_recorded_host.webp" alt="The recorded benchmark host" width="900"></a></p>

The original measurements were captured on this WSL host with one benchmark thread.

### 23. Build and verify locally

<p align="left"><a href="assets/screenshots/23_reproduce.png"><img src="assets/thumbs/23_reproduce.webp" alt="Build and verify locally" width="900"></a></p>

The baseline and unrolled binaries share the same Release build and run in separate working directories.

### 24. Reading the timing comparison

<p align="left"><a href="assets/screenshots/24_interpretation.png"><img src="assets/thumbs/24_interpretation.webp" alt="Reading the timing comparison" width="900"></a></p>

One measured pair shows a small kernel improvement alongside a lower overall HPCG rating.

## About the Author

Mohammad Rohaan and Ahmed Abdullah completed the original HPCG optimization study for CS-2008 Numerical Computing. Mohammad Rohaan maintains this repository. [GitHub profile](https://github.com/rohaan2802)
