// High-Performance Computing · CUDA · 2024
Approximate nearest-neighbor search is the engine behind vector databases and recommendation systems. This project ports HNSW — the graph index most of them rely on — onto the GPU with hand-written CUDA C++, built for the OracleX × Politecnico di Milano high-performance computing challenge.
01 — The problem
HNSW (Hierarchical Navigable Small World) graphs answer "which vectors are closest to this query?" in near-logarithmic time by greedily hopping across a layered proximity graph. It is fast on CPU — but each query is a chain of dependent, pointer-chasing memory lookups, which is exactly the access pattern GPUs hate.
The challenge: get a GPU, which wins through massive parallelism over coalesced memory, to accelerate an algorithm whose single-query traversal is inherently sequential and scattered.
02 — Approach
The key move is changing what gets parallelized. Instead of trying to speed up one graph walk, the implementation runs thousands of independent queries concurrently, mapping warps to queries and threads to candidate-distance evaluations so the GPU stays busy even while any single traversal stalls on memory.
One warp drives each query's traversal while its lanes evaluate neighbor distances in parallel, hiding memory latency behind thousands of in-flight queries.
The adjacency lists and vectors are repacked so that threads in a warp read contiguous memory, turning scattered pointer chases into coalesced loads.
The visited set and candidate heap live in shared memory / registers where possible, cutting global-memory round-trips during the hot inner loop.
Nsight profiling guided block sizes and occupancy choices, trading off register pressure against the number of resident warps per SM.
03 — Takeaways
The headline lesson mirrors most real GPU work: the algorithm barely changed, but how data was laid out in memory decided everything. Reorganizing the graph for coalesced access and saturating the device with concurrent queries delivered large throughput gains over a naïve port — and made the difference between a GPU that idles on memory stalls and one that actually earns its parallelism.
It was also a hands-on counterpart to NVIDIA's Accelerated Computing in CUDA C/C++ certification — applying occupancy, coalescing and shared-memory ideas to a genuinely awkward, irregular workload rather than a textbook matrix multiply.
04 — Stack