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.
22 lines
917 B
TeX
22 lines
917 B
TeX
\section{Memory Layout and Cache Effects}
|
|
|
|
|
|
\subsection{Data Layout}
|
|
|
|
Coefficients are stored as contiguous arrays of \texttt{int16} (for ML-KEM, $q < 2^{16}$)
|
|
or \texttt{int32} (for ML-DSA, $q < 2^{24}$). This ensures that AVX2 loads (\texttt{VMOVDQU})
|
|
fetch 16 or 8 coefficients in a single cache line access.
|
|
|
|
\subsection{Cache Friendliness}
|
|
|
|
The iterative NTT with bit-reversed twiddle factors accesses memory in stride-1 order
|
|
within each butterfly layer. Layer 1 processes adjacent pairs; layer 2 processes pairs
|
|
separated by 2; layer $k$ processes pairs separated by $2^{k-1}$.
|
|
|
|
For NTT-256, the entire polynomial (512 bytes at 16-bit) fits in L1 cache (32--64~KB).
|
|
For NTT-4096 (FHE), the polynomial (16~KB at 32-bit) still fits in L1. Cache effects
|
|
become significant only for very large degrees ($n \geq 2^{16}$), which are rare in
|
|
practice.
|
|
|
|
%% ============================================================
|