mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
abf99d05fc
Restructured from flat .tex/.pdf files into per-paper subdirectories. Added Antje Worring as co-author on all papers. Synced PDFs to pdfs/ for download site.
29 lines
1.2 KiB
TeX
29 lines
1.2 KiB
TeX
\section{NTT SIMD Performance}
|
|
|
|
|
|
The NTT engine is the innermost loop of all FHE operations. Performance here determines the floor for everything above it.
|
|
|
|
\begin{table}[h]
|
|
\centering
|
|
\begin{tabular}{@{}lrrr@{}}
|
|
\toprule
|
|
\textbf{Operation} & \textbf{$N$} & \textbf{EPYC (AVX-512)} & \textbf{M2 (NEON)} \\
|
|
\midrule
|
|
Forward NTT & 1024 & 4.2 $\mu$s & 5.8 $\mu$s \\
|
|
Forward NTT & 2048 & 9.1 $\mu$s & 12.4 $\mu$s \\
|
|
Inverse NTT & 1024 & 4.5 $\mu$s & 6.1 $\mu$s \\
|
|
Inverse NTT & 2048 & 9.8 $\mu$s & 13.2 $\mu$s \\
|
|
Polynomial Mul (NTT) & 1024 & 13.5 $\mu$s & 18.1 $\mu$s \\
|
|
Polynomial Mul (NTT) & 2048 & 29.0 $\mu$s & 39.2 $\mu$s \\
|
|
\midrule
|
|
\textbf{Throughput} (poly mul/s) & 1024 & 74.1M & 55.2M \\
|
|
\textbf{Throughput} (poly mul/s) & 2048 & 34.5M & 25.5M \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\caption{NTT performance. Polynomial multiplication includes forward NTT, pointwise multiply, inverse NTT. Barrett reduction throughout.}
|
|
\label{tab:ntt}
|
|
\end{table}
|
|
|
|
The NTT engine uses precomputed twiddle factors in bit-reversed order for in-place Cooley-Tukey butterflies. Barrett reduction ($\mu = \lfloor 2^{64}/Q \rfloor$) avoids division in the inner loop. Montgomery form is used for coefficient storage to avoid reduction after every multiply.
|
|
|