Lecture 115: Proving Kernels Correct Instead of Testing Them
This lecture details the necessity and methodology of formally verifying GPU kernels, moving beyond traditional testing due to the massive input space and non-deterministic nature of GPU execution. The core approach involves reasoning about kernel correctness at the PTX level using Satisfiability Modulo Theories (SMT) solvers. The process requires modeling mathematical concepts (like floating-point operations and unbounded integers) as abstract 'reals' to prove equivalence between a candidate kernel and a reference implementation, thereby guaranteeing algorithmic correctness.
Key takeaways
-
Limitations of Testing GPU Kernels
1:30
Due to the vast input space and the non-deterministic scheduling inherent in GPU hardware (e.g., Nvidia), testing alone cannot guarantee correctness. Errors can occur across various boundaries (e.g., denormal boundaries, cancellation terms), and the execution order cannot be guaranteed at runtime. (0:01:30)
-
Formal Verification at the PTX Level
2:10
To prove correctness, the goal is to show that for every value X, the candidate kernel produces the same output as the reference kernel. This verification is performed at the PTX level because it provides relatively well-defined semantics, allowing the system to cover inputs from various sources (Triton, CUDA, inline PTX). (0:02:10)
-
SMT Solvers and Mathematical Abstraction
3:20
Formal verification uses SMT solvers to convert code into mathematical boolean abstractions. By modeling values as 'reals' (abstract values with infinite precision) and unbounded mathematical integers, the system can prove algorithmic equivalence without requiring bit-exact checks, which would lead to an unmanageable 'explosion' of clauses. (0:03:20)
-
Advanced Verification Boundaries
4:30
Future work focuses on formally verifying complex boundaries, including sandboxes (to prevent escape paths from LLM-generated code) and numerical stability (e.g., quantization stability), which are addressed separately from algorithmic correctness. (0:04:30)