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/div} & \textbf{M4 Max ns/div} \\
\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 Knuth-D division is one of two compounding levers; the other is the coalesced
structure-of-arrays memory layout (below). Replacing the 512-iteration bit-serial
\texttt{uint256} VWAP division with Knuth Algorithm~D (base-$2^{32}$ limbs) shrinks the
\emph{per-lane} division cost by roughly an order of magnitude. Both rows are byte-identical
to the CPU oracle. These are per-division-op latencies, not matcher throughput: the tuned
matcher runs thousands of such divisions in parallel across coalesced lanes
(Table~\ref{tab:gpu-throughput}).}
\label{tab:division}
\end{table}

\subsection{Measured throughput}

\begin{table}[H]
\centering
\renewcommand{\arraystretch}{1.25}
\begin{tabular}{l l r}
\toprule
\textbf{Platform} & \textbf{Kernel} & \textbf{Orders/s} \\
\midrule
AMD Radeon 8060S              & coalesced SoA (Knuth-D)   & \textbf{12.76\,B} \\
NVIDIA GB10 (Grace-Blackwell) & coalesced SoA (Knuth-D)   & 9.13\,B \\
NVIDIA GB10                   & un-coalesced (baseline)   & 1.54\,B \\
Apple M4 Max (128\,GB UMA)    & coalesced SoA (Knuth-D)   & 5.60\,B \\
Apple M1 Max                  & coalesced SoA (Knuth-D)   & 2.80\,B \\
\bottomrule
\end{tabular}
\caption{Measured CLOB matching throughput, byte-parity-gated, single-fill depth-64
markets. The tuned production path lays each book's arena out as a coalesced
structure-of-arrays (SoA) so neighboring lanes touch neighboring addresses; on the GB10
this lifts throughput from a 1.54\,B un-coalesced baseline to 9.13\,B orders/sec, and the
same SoA preload yields $6.6\times$ over baseline on the AMD Radeon 8060S (the fastest
device measured). Every row is byte-identical to the CPU oracle. A two-node fabric
aggregates linearly to 21.9\,B orders/sec.}
\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}

An earlier, un-coalesced kernel behaved as if the wall were dependency latency---the
data-dependent loop inside the division and the serial walk of price levels---because
forcing higher occupancy (a register cap, or raising occupancy from 16.7\% to 25\%) did not
move throughput and the GB10 drew only a fraction of its power envelope while reporting the
GPU fully busy. The lever that broke this apparent wall was \emph{memory layout}, not
occupancy: laying each book's arena out as a coalesced structure-of-arrays (SoA), so that
neighboring lanes touch neighboring addresses on every match, turns the matcher
throughput-bound. On the GB10 this lifts sustained throughput from the 1.54\,B un-coalesced
baseline to 9.13\,B orders/sec; on the AMD Radeon 8060S the same SoA preload yields
12.76\,B orders/sec, $6.6\times$ over its un-coalesced baseline. The Apple M4 Max and M1 Max
reach 5.60\,B and 2.80\,B orders/sec respectively. What looked like a latency ceiling was an
un-coalesced memory-access pattern.

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. 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{Yes---a single device already clears it, per venue.} The tuned coalesced-SoA matcher
sustains 9.13\,B orders/sec on a GB10, 12.76\,B on an AMD Radeon 8060S, 5.60\,B on an M4 Max,
and 2.80\,B on an M1 Max---each an order of magnitude past $10^{9}$/s on one device,
byte-exact against the CPU oracle. An earlier draft, benchmarking an un-coalesced kernel,
concluded that $10^{9}$/s required an $8$--$10$-node fleet; that conclusion was an artifact
of the un-tuned memory layout and is withdrawn. Fleet and fabric scaling then compose
\emph{on top of} the single-device rate, following Equation~\eqref{eq:aggregate}:

\begin{description}
  \item[$N$-node / fabric aggregation.] Per-book arenas are independent, so sharding markets
  across nodes and summing scales linearly on top of the single-device rate. A two-node
  fabric measures 21.9\,B orders/sec; larger fleets extend this proportionally.
  \item[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, further shortening the critical
  path and shrinking the working set (10\,k markets in $\sim$41\,MB versus $\sim$1.3\,GB). It
  trades precision and ABI width and is \emph{not yet built}; we state it as an 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; the remaining constraints are 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,'' and a ``billion orders/sec'' headline derived from 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. \textbf{Those figures are fabricated and are retracted}; they measured nothing
on a GPU. They must not be conflated with the billions-of-orders-per-second rates reported
in this section, which are independently measured on the stated hardware under the parity
gate and gated byte-for-byte against the CPU oracle. The numbers in
Tables~\ref{tab:division} and~\ref{tab:gpu-throughput} supersede every prior claim.