papers/lux-lightspeed-dex/sections/07-gpu-matching.tex

\section{GPU CLOB Matching}
\label{sec:gpu-matching}

This section reports the measured throughput of the matching engine, the algorithmic lever
that produced it, the parity discipline that makes the numbers trustworthy, and an honest
treatment of the question ``can it do more than $10^{9}$ matches per second?''

All figures are measured on stated hardware and gated by byte-exact parity against a CPU
reference oracle. We do not report any throughput from a simulation, and we do not multiply
a measured number by a fudge factor. The retraction of prior fabricated figures is stated
explicitly in Section~\ref{subsec:retraction}.

\subsection{Representation and parity gate}

Prices are fixed-point \texttt{Q64.64}; quantities and notionals are computed in
\texttt{uint256} (big-endian limbs) so that matching is integer-exact and identical across
CPU architectures. The CPU reference oracle and the GPU kernels share this representation
exactly. The parity gate is the contract that makes every GPU number in this section
meaningful:

\begin{quote}
\emph{The GPU matcher must be byte-identical to the CPU reference oracle---on both the
emitted fills and the post-match arena state---across millions of fuzz cases and a
known-answer test suite, with zero failures, or it does not ship.}
\end{quote}

The gate was exercised with over two million direct division-pair comparisons and two
hundred thousand book-fuzz cases (checking output \emph{and} arena post-state), plus a
known-answer sequence, with zero failures, for the CUDA path and the Metal port. Where the
oracle's bit-serial division would overflow its remainder register---reachable only for an
average price at or above $2^{255}$, which does not occur in real matching---the fast path
falls back to the bit-serial routine to remain byte-exact even on that adversarial input.

\subsection{The algorithmic lever: limb-wise division}

The per-match critical path is dominated by a \texttt{uint256} volume-weighted-average-price
(VWAP) division. The original kernel computed it with a 512-iteration bit-serial long
division, one data-dependent subtraction per bit. Replacing this with \textbf{Knuth
Algorithm~D}---base-$2^{32}$ limb division with a quotient-digit estimate and correction
step---collapses the per-match cost:

\begin{table}[H]
\centering
\renewcommand{\arraystretch}{1.2}
\begin{tabular}{l r r}
\toprule
\textbf{Division routine} & \textbf{GB10 ns/match} & \textbf{M4 Max ns/match} \\
\midrule
512-iteration bit-serial (baseline) & 50--61 & 51 \\
Knuth Algorithm~D (limb-wise)       & \textbf{6.9} & \textbf{4.15} \\
\midrule
Speedup & $\sim$8$\times$ & $\sim$12$\times$ \\
\bottomrule
\end{tabular}
\caption{The dominant lever is the division, not the parallelism strategy. Replacing the
512-iteration bit-serial \texttt{uint256} VWAP division with Knuth Algorithm~D
(base-$2^{32}$ limbs) shrinks the per-match critical path by roughly an order of magnitude.
Both rows are byte-identical to the CPU oracle.}
\label{tab:division}
\end{table}

\subsection{Measured throughput}

\begin{table}[H]
\centering
\renewcommand{\arraystretch}{1.25}
\begin{tabular}{l l r r}
\toprule
\textbf{Platform} & \textbf{Kernel} & \textbf{Fills/s} & \textbf{ns/match} \\
\midrule
NVIDIA GB10 (Grace-Blackwell) & limb (Knuth-D)        & 104--126\,M & 6.9 \\
NVIDIA GB10                   & warp-cooperative      & $\sim$99\,M (sustained) & 10.2 \\
NVIDIA GB10                   & bit-serial (baseline) & 16.5--18.5\,M & 50--61 \\
Apple M4 Max (128\,GB UMA)    & limb (Knuth-D)        & $\sim$250\,M (sustained) & 4.15 \\
\bottomrule
\end{tabular}
\caption{Measured CLOB matching throughput, byte-parity-gated, single-fill depth-64
markets. The limb (Knuth-D) kernel is the production path (one match per book per
dispatch); the warp-cooperative kernel is an optional sustained-compute path that runs the
GPU harder but adds gather overhead for the rare multiply/divide. The Apple M4 Max's
unified memory and wide ALUs lead on this workload.}
\label{tab:gpu-throughput}
\end{table}

The matcher is embarrassingly parallel across markets because each book occupies an
independent arena and books never share state on the hot path. Throughput is therefore
governed by the exact relation
\begin{equation}
  \text{aggregate fills/s} \;=\; N_{\text{nodes}} \times B_{\text{books/node}}
    \times f_{\text{fills/book/s}}.
  \label{eq:aggregate}
\end{equation}

\subsection{What actually limits a single GPU}

The limit is \emph{not} occupancy, PCIe bandwidth, dispatch overhead, or ALU throughput;
it is dependency latency---the data-dependent loop inside the division and the serial walk
of price levels on the critical path. We established this on the GB10 four ways:

\begin{enumerate}
  \item Forcing higher occupancy via a register cap \emph{lowered} throughput (register
  spills).
  \item Reducing threads-per-block to raise occupancy from 16.7\% to 25\% did not move
  throughput.
  \item At peak limb-kernel throughput the GB10 drew $\sim$25\,W of a 100\,W-plus envelope
  with the SM clock below its maximum, yet reported the GPU fully busy---characteristic of a
  latency-bound, not throughput-bound, kernel.
  \item The warp-cooperative kernel, which shortens the per-match critical path by spreading
  one \texttt{uint256} across lanes, raises sustained throughput by $\sim$22\% and runs the
  GPU at $\sim$62\,W---moving the latency wall, not an occupancy wall.
\end{enumerate}

A second, separate wall appears at high market counts. The per-book arena is large (mostly
empty depth), so beyond roughly 50--75\,k markets the working set overflows cache and
throughput falls off a cliff (on the GB10: 126\,M fills/s at 50\,k markets, 48\,M at 75\,k,
31\,M at 100\,k). A compact arena is the lever for very high market counts and is not yet
built.

\subsection{Can it exceed $10^{9}$ matches per second?}
\label{subsec:billion-matching}

\textbf{Honestly: not on one GPU for byte-exact \texttt{uint256} matching.} The measured,
latency-bound ceiling is $\sim$100--130\,M fills/s on a GB10 and $\sim$250\,M on an M4 Max.
A prior internal projection of $\sim$$10^{9}$/s on a single GPU was optimistic and is not
supported by measurement. There are two honest routes past $10^{9}$/s, both following
directly from Equation~\eqref{eq:aggregate}:

\begin{description}
  \item[(a) $N$-node aggregation.] Per-book arenas are independent, so sharding markets
  across nodes and summing yields linear scaling. With $f \approx 100\text{--}130$\,M
  fills/s per node, $8$--$10$ GB10-class or M4-Max-class nodes clear $10^{9}$ fills/s. This
  is aggregation of measured single-node rates, not a new measurement.
  \item[(b) A cheaper representation.] A \texttt{Q64.64} fixed-point path uses 4\,KB arenas
  and a $64/64$ division instead of full $512$-bit arithmetic. This trades precision and ABI
  width for a far shorter critical path and a far smaller working set (10\,k markets in
  $\sim$41\,MB versus $\sim$1.3\,GB). It is a precision/ABI tradeoff and is \emph{not yet
  built}; we state it as the obvious lever, not as a result.
\end{description}

We are careful to aggregate correctly: the aggregate rate shards distinct books across
nodes and sums, never the same books counted on multiple nodes. Per-book compute is never
the constraint---each book needs only on the order of $10^{4}$ fills/s to reach $10^{9}$/s
across a fleet, hundreds of times below the single-lane rate---so the constraint is host
dispatch and, on discrete GPUs, the resident-arena data path, both addressed by batched,
persistent-arena kernels rather than per-call allocation.

\subsection{Retraction of prior figures}
\label{subsec:retraction}

Earlier drafts of this work claimed ``581\,M orders/sec at 597\,ns,'' ``100\,M+/s,''
``434\,M GPU orders/sec,'' ``billion orders/sec,'' and ``planet-scale.'' \textbf{Those
figures are fabricated and are retracted.} Their lineage is a \texttt{time.Sleep}-based
simulation with a hardcoded $597$\,ns/order, followed by a post-processing step that
multiplied a CPU run's throughput by $40$ and divided its latency by the same. They measured
nothing on a GPU. The numbers in Tables~\ref{tab:division} and~\ref{tab:gpu-throughput} are
measured on the stated hardware under the parity gate of this section and supersede every
prior claim.