% Created 2025-09-30 Tue 15:07
% Intended LaTeX compiler: pdflatex
\documentclass[usenames,dvipsnames,colorlinks,aspectratio=169]{beamer}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\usepackage{color}
\usepackage{listings}
\usepackage{pdfpages}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{xspace}
\usepackage{siunitx}
\usepackage{libertine}
\usepackage{fontawesome}
\mode<beamer>{\usetheme{Boadilla}}
\setbeamertemplate{navigation symbols}{}
\setbeamerfont{alerted text}{series=\bfseries}
\setbeamercolor{alerted text}{fg=blue}
\usecolortheme{default}
\usefonttheme{serif}
\usefonttheme{professionalfonts}
\lstloadlanguages{[ISO]C++}
\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.50,0,0.82}
\definecolor{codeorange}{rgb}{0.95,0.3,0.1}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
\lstdefinestyle{mystyle}{
commentstyle=\color{codegreen},
keywordstyle=\color{codeorange},
numberstyle=\tiny\color{codegray},
stringstyle=\color{codepurple},
basicstyle=\footnotesize,
breakatwhitespace=false,
breaklines=true,
captionpos=b,
keepspaces=true,
numbers=left,
numbersep=5pt,
showspaces=false,
showstringspaces=false,
showtabs=false,
tabsize=2
}
\lstset{style=mystyle}
\usetheme{default}
\author{Brett Viren}
\date{\today}
\title{Discrete Fourier Transform Speed in SPNG}
\hypersetup{
 pdfauthor={Brett Viren},
 pdftitle={Discrete Fourier Transform Speed in SPNG},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 28.2 (Org mode 9.5.5)}, 
 pdflang={English}}
\begin{document}

\maketitle

\begin{frame}[label={sec:org47f2833}]{Topics}
\begin{itemize}
\item Discrete Fourier Transform (DFT) speed vs size.
\item Code to select a ``faster'' size.
\end{itemize}
\end{frame}

\begin{frame}[label={sec:orgb17c8f7},shrink=10]{Intro to DFT speed theory}
\begin{block}{Original FFT (radix-2 Cooley-Tukey) algorithm}
\begin{itemize}
\item Only supports array sizes that are powers of 2.

\item FFT complexity scales with \(\mathcal{O}(N \log N)\).
\end{itemize}
\end{block}

\begin{block}{Mixed-radix algorithms extend FFT to sizes with other prime factors.}
\begin{itemize}
\item Special, compile-time support optimizes for small prime factors (3, 5, 7).

\item Special, run-time (slower) algorithms handle sizes with larger prime factors.
\end{itemize}
\end{block}

\begin{block}{Need luck to hit a fast size but luck is fairly uniform}
\begin{itemize}
\item Huge speed ups often possible with small increase in size.

\item A simple heuristic can find good candidates for ``special''.

\begin{itemize}
\item First larger size with prime factors less than some value (eg 7).

\item But sometimes next or next-next with small primes is faster.
\end{itemize}

\item Measurements needed to find the truly faster but problematic.

\begin{itemize}
\item Very dependent on the device (CPU/GPU), amount of and makeup memory (L1/L2/L3 cache) and parallelism.

\item Measuring produces a large table that needs significant time for lookup.
\end{itemize}
\end{itemize}
\end{block}
\end{frame}

\begin{frame}[label={sec:org642c0b7},fragile]{Measurements}
 \begin{block}{Test environment and plots}
\begin{itemize}
\item Using wcgpu0 Ryzen 7970X, RTX 4090
\item Look duration at \texttt{torch::fft::fft()} on all sizes of 1D tensor
\begin{itemize}
\item Given a focus and color to just small-prime factor sizes.
\end{itemize}
\item Look with and without CPU multi-threading.
\end{itemize}
\end{block}

\begin{block}{Testing procedure:}
\begin{itemize}
\item Duration is measured with \texttt{<chrono>}
\item Each test point repeats to get around 10ms total duration.
\item A GPU test point loop is async followed by a sync to assure completion.
\end{itemize}

Code to reproduce is in \texttt{spng/test/check\_dft\_measure.\{cxx,py\}}.
\begin{itemize}
\item (written in ``collaboration'' with Gemini)
\end{itemize}
\end{block}
\end{frame}


\begin{frame}[label={sec:org020e2a6}]{Measurements - all sizes, single-core CPU}
\includegraphics[height=0.9\textheight, page=1]{benchmark-10k.pdf}
\end{frame}

\begin{frame}[label={sec:org6a6e690}]{Measurements - small-prime factor sizes, single-core CPU}
\includegraphics[height=0.9\textheight, page=1]{benchmark-st.pdf}
\end{frame}

\begin{frame}[label={sec:org40f56a3}]{Measurements - small-prime factor sizes, multi-core CPU}
\includegraphics[height=0.9\textheight, page=1]{benchmark-mt.pdf}
\end{frame}

\begin{frame}[label={sec:org72dd67c},fragile]{Some observations}
 \begin{itemize}
\item Powers of 2 win \alert{but only up to 1024}.

\begin{itemize}
\item 2048 and above is slower, maybe because of Ln CPU cache misses.
\end{itemize}

\item Most points have a \alert{nearby faster point} that has small-prime factors.

\begin{itemize}
\item There is a spread in small-prime factor speeds.
\item Spread is in bands, actually, and I don't understand their origin.
\end{itemize}

\item \texttt{libtorch} kicks in CPU-parallelism after 4096.
\begin{itemize}
\item Increases throughput \(\approx 2 \times\) but uses \(\approx 20\) cores, a \alert{high cost}!
\end{itemize}

\item \alert{CPU beats GPU for small sizes} below about 512!

\begin{itemize}
\item Almost certainly due to GPU transfer overheads compared to fast CPU memory access.
\end{itemize}

\item \alert{GPU time largely constant} as function of size for moderate sizes.

\begin{itemize}
\item I expect this is due to massive parallelization and fixed overheads.
\end{itemize}

\item Results are very \alert{device dependent}.
\begin{itemize}
\item Testing other CPUs/GPUs is needed.
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}[label={sec:orgf700b31},fragile]{Reproducing}
 \begin{block}{Environment for single-threaded tests:}
\scriptsize
\begin{verbatim}
$ export OMP_NUM_THREADS=1
$ export MKL_NUM_THREADS=1
\end{verbatim}
\end{block}

\begin{block}{Measure}
\scriptsize
\begin{verbatim}
$ ./build/spng/check_dft_measure -s range -m 16 -M 10000 benchmark-10k.csv 
$ ./build/spng/check_dft_measure benchmark-st.csv
\end{verbatim}
Unset the \texttt{*\_NUM\_THREADS} and repeat to get a MT data.
\end{block}

\begin{block}{Plot}
\scriptsize
\begin{verbatim}
$ ./spng/test/check_dft_measure.py benchmark-10k.csv benchmark-10k.pdf
\end{verbatim}
Etc for the others.
\end{block}
\end{frame}



\begin{frame}[label={sec:org9f29ac9},fragile,shrink=10]{Picking the best size}
 \begin{block}{WCT mainline already has an \texttt{fft\_best\_length()}, why not just use that?}
Hard-coded lookup based on some undocumented measurement procedure on an unknown device using unknown software done at least seven years ago.  SPNG can do better!
\end{block}

\begin{block}{High-level API}
\scriptsize
\begin{verbatim}
#include "WireCellSpng/DFT.h"

// Init in single-thread context with default policy.
FasterDftSize fds;

// Optional customized policy. 
fds.reset(make_faster_dft_size_measured(...));

// Use in MT context okay
int64_t new_size = fds(old_size);
\end{verbatim}
\end{block}

\begin{block}{Design}
This design is driven by the need to be thread-safe inside \texttt{INode::operator()} while also handling file loading, caching, etc.
\end{block}
\end{frame}

\begin{frame}[label={sec:org4ff80ea},fragile,shrink=10]{More API}
 \begin{block}{Mid-level - construct with some available knobs}
\scriptsize
\begin{verbatim}
inline const std::string faster_dft_size_default_measurement_file =
    "torch_dft_measured.json";

FasterDftSizeBase::pointer make_faster_dft_size_measured(
    torch::Device device = torch::kCPU,
    const std::string& filename = faster_dft_size_default_measurement_file);

FasterDftSizeBase::pointer make_faster_dft_size_primes(int64_t max_prime=7);
\end{verbatim}
\end{block}

\begin{block}{Low-level - actual measure lookup or heuristic calculation}
\scriptsize
\begin{verbatim}
int64_t faster_dft_size(const std::vector<int64_t>& sizes,
                        const std::vector<float>& durations,
                        int64_t orig_size);

int64_t faster_dft_size(int64_t orig_size, int64_t max_prime=7);
\end{verbatim}
\end{block}
\end{frame}

\begin{frame}[label={sec:org81573b8},fragile]{Open questions:}
 \begin{itemize}
\item Is there significant variation across different devices?

\item Is there significant variation across different DFT functions?  
\begin{itemize}
\item How does 2D play a role?  Does \texttt{rfft()} have speeds from \texttt{fft()}?
\end{itemize}

\item Can/should we exploit caching and reusing DFT plans?

\item Does any of this matter compared to other operations?
\end{itemize}
\end{frame}
\end{document}