Parallel Prefix Sum (Scan) for NVIDIA T4 (sm_75)

A production‑ready, hierarchical parallel prefix sum (scan) kernel optimised for NVIDIA T4 GPUs. Supports both inclusive and exclusive scans for arbitrary large arrays, with full boundary handling and zero register spills.

---

Repository Structure

cuda-parallel-prefix-scan/
├── README.md
├── scan.cu              # Complete kernel + benchmark + CPU reference
├── LICENSE
└── docs/
└── case-study.md    # Detailed optimisation journey

---

Key Features

• Hierarchical recursion – handles any array size N (tested up to 100M elements).
• Bank‑conflict‑free shared memory – padding formula phys_idx = logical_idx + (logical_idx >> 5) eliminates 32‑bank conflicts.
• Warp‑shuffle reductions – __shfl_up_sync for fast intra‑warp prefix.
• Parallel prefix tree in registers – removes serial dependency chains.
• Workspace caching – reuses device allocations across calls, avoiding repeated cudaMalloc overhead.
• Full error checking – every CUDA API call validated.
• Both inclusive and exclusive scans – configurable via template parameter.
• Zero register spills – 44 registers/thread, 0 stack, 0 spills.

---

Performance

Hardware: NVIDIA T4 (sm_75) on Google Colab
Tested sizes: 1M, 10M, 100M elements (FP32)

Array Size	GPU Time	Throughput	Rate
1M	0.066 ms	116.7 GB/s	14.6 G‑elem/s
10M	0.684 ms	116.9 GB/s	14.7 G‑elem/s
100M	6.7 ms	119.3 GB/s	14.9 G‑elem/s

Compiler output (nvcc -O3 -arch=sm_75):

0 bytes stack frame
0 bytes spill stores
0 bytes spill loads
Used 44 registers, 8480 bytes smem

---

Compilation & Usage

Prerequisites

• CUDA Toolkit 11.8 or later
• NVIDIA driver supporting sm_75 (T4)

Build

nvcc -O3 -arch=sm_75 -lineinfo --ptxas-options=-v -o scan scan.cu

Run

./scan

The benchmark runs scans for 1M, 10M, and 100M elements, compares against a CPU reference, and reports execution time and throughput.

---

How It Works

1. Tiling – each block processes 2048 elements (256 threads × 8 elements/thread).
2. Load – coalesced global reads into padded shared memory with bank‑conflict‑free mapping.
3. Register scan – parallel prefix tree on 8‑element chunks.
4. Warp scan – __shfl_up_sync computes prefix across warp lanes.
5. Block‑level scan – warp sums are scanned by warp 0 using shuffle.
6. Writeback – scanned values written to global memory with optional exclusivity.
7. Recursion – if multiple blocks, block sums are scanned recursively (or in a single block if ≤ 2048).
8. Uniform add – block offsets are added back to all elements.

---

Correctness Validation

The kernel is validated against a naive CPU implementation using random floating‑point inputs. Due to floating‑point non‑associativity, small relative errors (≤ 1e-2) are tolerated. The benchmark reports PASSED when all elements match within tolerance.

---

Optimisation Journey

Key fixes applied after rigorous auditing:

· Removed restrict – to avoid aliasing violation during in‑place recursive calls. · 64‑bit indexing – changed all indices to size_t to support arrays > 2^31 elements. · Added CUDA error handling – every API call and kernel launch is checked. · Workspace caching – avoids repeated cudaMalloc overhead. · Parallel prefix tree – replaced sequential 8‑addition loop with parallel tree to improve ILP. · Bank‑conflict padding – ensures 100% conflict‑free shared memory accesses.

---

License

MIT License – see LICENSE file.

---

Author

Mustafa-cuda-dev GitHub: https://github.com/Mustafa-cuda-dev

---

Acknowledgements

· NVIDIA CUDA Toolkit and WMMA documentation · Google Colab for providing free T4 GPU access · The open‑source CUDA community

---