\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{booktabs}
\usepackage{hyperref}

\title{Computational Analysis of Elman RNN on enwik9\\
Baseline Performance and Optimization Targets}
\author{Claude}
\date{2026-02-06}

\begin{document}
\maketitle

\begin{abstract}
We analyze the computational requirements for running an Elman RNN on the full
enwik9 dataset (1 billion bytes). The current single-threaded C implementation
achieves approximately 2,800 bytes/second, requiring $\sim$100 hours for a single
forward pass. We characterize the bottlenecks and establish optimization targets
for practical tick-tock iteration.
\end{abstract}

\section{Introduction}

The tick-tock methodology alternates between training (tick) and interpretation (tock).
Each tick requires multiple passes over enwik9---at minimum one forward pass for
evaluation, and many more for gradient-based training. At 100 hours per pass,
a single training epoch takes 4 days, making rapid iteration impossible.

This paper establishes the baseline computational profile and identifies
optimization opportunities.

\section{Model Architecture}

The Elman RNN has architecture $256 \to 128 \to 256$:
\begin{align}
h_t &= \tanh(W_{ih} x_t + W_{hh} h_{t-1} + b_h) \\
y_t &= \text{softmax}(W_{ho} h_t + b_o)
\end{align}

Parameters:
\begin{center}
\begin{tabular}{lrr}
\toprule
Matrix & Dimensions & Parameters \\
\midrule
$W_{ih}$ & $128 \times 256$ & 32,768 \\
$W_{hh}$ & $128 \times 128$ & 16,384 \\
$b_h$ & $128$ & 128 \\
$W_{ho}$ & $256 \times 128$ & 32,768 \\
$b_o$ & $256$ & 256 \\
\midrule
Total & & 82,304 \\
\bottomrule
\end{tabular}
\end{center}

Model size: 329 KB (float32).

\section{Operations per Timestep}

For each of the 1 billion input bytes:

\begin{center}
\begin{tabular}{lrr}
\toprule
Operation & Computation & FLOPs \\
\midrule
$W_{ih} x_t$ (sparse) & column lookup & 256 \\
$W_{hh} h_{t-1}$ & $128 \times 128$ matmul & 32,768 \\
$+ b_h$ & vector add & 128 \\
$\tanh$ & 128 nonlinearities & $\sim$1,280 \\
$W_{ho} h_t$ & $256 \times 128$ matmul & 65,536 \\
$+ b_o$ & vector add & 256 \\
softmax & exp, sum, div & $\sim$2,560 \\
cross-entropy & log lookup & $\sim$257 \\
\midrule
\textbf{Total} & & $\sim$\textbf{103,000} \\
\bottomrule
\end{tabular}
\end{center}

Note: The input $x_t$ is one-hot, so $W_{ih} x_t$ reduces to a single column lookup
rather than a full matrix-vector multiply.

\section{Total Computation for enwik9}

\begin{center}
\begin{tabular}{lr}
\toprule
Metric & Value \\
\midrule
Dataset size & 1,000,000,000 bytes \\
FLOPs per byte & 103,000 \\
Total FLOPs & 103 TFLOPs \\
\bottomrule
\end{tabular}
\end{center}

\section{Memory Analysis}

\subsection{Weight Matrices}

All weights fit comfortably in L2/L3 cache:
\begin{center}
\begin{tabular}{lr}
\toprule
Component & Size \\
\midrule
$W_{ih}$ & 128 KB \\
$W_{hh}$ & 64 KB \\
$W_{ho}$ & 128 KB \\
Biases & 1.5 KB \\
\midrule
Total & 321.5 KB \\
\bottomrule
\end{tabular}
\end{center}

\subsection{Per-Timestep Memory Traffic}

With weights cached:
\begin{itemize}
\item Read: $h_{t-1}$ (512 bytes), input byte (1 byte)
\item Write: $h_t$ (512 bytes), output logits (1 KB)
\item Total: $\sim$1.5 KB per timestep
\item Full dataset: $\sim$1.5 TB memory traffic
\end{itemize}

\section{Baseline Performance}

\subsection{C Implementation (hutter.c)}

Benchmarked on server CPU (single-threaded):

\begin{center}
\begin{tabular}{rrr}
\toprule
Sample Size & Time & Throughput \\
\midrule
1,000 bytes & 0.39 s & 2,551 bytes/s \\
10,000 bytes & 3.85 s & 2,597 bytes/s \\
100,000 bytes & 30.6 s & 3,263 bytes/s \\
\bottomrule
\end{tabular}
\end{center}

\textbf{Extrapolated time for full enwik9: 99 hours (4.1 days)}

\subsection{Python/NumPy Implementation}

Single-threaded with BLAS:

\begin{center}
\begin{tabular}{lr}
\toprule
Metric & Value \\
\midrule
Throughput & $\sim$10,000 bytes/s \\
Extrapolated enwik9 time & $\sim$28 hours \\
\bottomrule
\end{tabular}
\end{center}

NumPy outperforms the C implementation because it uses optimized BLAS routines
for the matrix-vector multiplications.

\subsection{Analysis}

The C implementation achieves only:
\[
\frac{103,000 \text{ FLOPs}}{1/2800 \text{ s}} = 288 \text{ MFLOPs/s}
\]

This is $\sim$3\% of single-core capability ($\sim$10 GFLOPs/s for modern x86).
The bottleneck is not raw compute but rather:
\begin{enumerate}
\item Lack of SIMD vectorization
\item Sequential loop structure
\item Possible cache inefficiency in memory layout
\end{enumerate}

\section{Theoretical Limits}

\subsection{CPU (Single Core)}

Modern x86 with AVX2: $\sim$100 GFLOPs/s peak, $\sim$10-30 GFLOPs/s sustained.

\begin{center}
\begin{tabular}{lr}
\toprule
Sustained GFLOPs/s & enwik9 Time \\
\midrule
10 & 2.9 hours \\
30 & 57 minutes \\
\bottomrule
\end{tabular}
\end{center}

\subsection{GPU}

RNNs are memory-bound on GPU due to sequential dependency. Effective throughput
is typically 1-5\% of peak FLOPs.

\begin{center}
\begin{tabular}{llr}
\toprule
GPU & Effective TFLOPs & enwik9 Time \\
\midrule
RTX 3090 (35 TF peak) & 0.5--1.0 & 2--3 minutes \\
A100 (312 TF peak) & 3--5 & 20--30 seconds \\
\bottomrule
\end{tabular}
\end{center}

\subsection{Batched Processing}

Processing $B$ independent sequences in parallel:
\begin{itemize}
\item Matrix-vector $\to$ matrix-matrix multiplication
\item Better cache utilization and SIMD efficiency
\item Requires $B \times$ memory for hidden states
\end{itemize}

For batch size $B = 64$:
\begin{itemize}
\item Each sequence: 15.6M bytes (enwik9 / 64)
\item Hidden state memory: 64 $\times$ 512 bytes = 32 KB
\item Potential speedup: 10--50$\times$ on CPU, 100--1000$\times$ on GPU
\end{itemize}

\section{Optimization Targets}

\begin{center}
\begin{tabular}{llr}
\toprule
Optimization & Expected Speedup & Target Time \\
\midrule
Baseline (current) & 1$\times$ & 99 hours \\
SIMD vectorization & 5--10$\times$ & 10--20 hours \\
+ Batched (B=64) & 20--50$\times$ & 2--5 hours \\
GPU (cuDNN RNN) & 100--500$\times$ & 10--60 minutes \\
\bottomrule
\end{tabular}
\end{center}

\section{Optimization Roadmap}

\subsection{Phase 1: SIMD Vectorization}

\begin{enumerate}
\item Replace scalar loops with AVX2 intrinsics
\item Ensure 32-byte aligned memory layout
\item Use \texttt{-O3 -march=native -ffast-math}
\item Target: 10$\times$ speedup (10 hours per pass)
\end{enumerate}

\subsection{Phase 2: Batched Processing}

\begin{enumerate}
\item Split enwik9 into $B$ chunks
\item Process chunks in parallel with BLAS \texttt{sgemm}
\item Hidden states: $B \times 128$ matrix
\item Target: 50$\times$ speedup (2 hours per pass)
\end{enumerate}

\subsection{Phase 3: GPU Acceleration}

\begin{enumerate}
\item Port to PyTorch or cuDNN
\item Use fused RNN kernels
\item Target: 500$\times$ speedup (10 minutes per pass)
\end{enumerate}

\section{Results After Optimization}

\subsection{Phase 1 Results: SIMD Vectorization}

Implemented AVX2 SIMD with 8-way loop unrolling and FMA instructions.

\textbf{Compiler flags}: \texttt{-O3 -march=native -mavx2 -mfma -ffast-math}

\textbf{Key optimizations}:
\begin{enumerate}
\item 8-way unrolled dot products using \texttt{\_mm256\_fmadd\_ps}
\item Fast tanh approximation using Pad\'{e} polynomial
\item Horizontal sum via \texttt{\_mm256\_extractf128\_ps} shuffle
\item Aligned memory access for weight matrices
\end{enumerate}

\textbf{Results}:
\begin{center}
\begin{tabular}{lrrr}
\toprule
Version & Throughput & enwik9 Time & Speedup \\
\midrule
Original hutter.c & 2,800 steps/s & 99 hours & 1.0$\times$ \\
Scalar (-O3 -march=native) & 11,800 steps/s & 23.5 hours & 4.2$\times$ \\
SIMD V3 (8x unroll + FMA) & 37,400 steps/s & 7.4 hours & 13.3$\times$ \\
\bottomrule
\end{tabular}
\end{center}

\textbf{Analysis}: The original hutter.c was compiled without optimization flags,
explaining the 4.2$\times$ improvement from just \texttt{-O3 -march=native}.
The SIMD implementation adds another 3.2$\times$ on top, for a total of 13.3$\times$.

\textbf{Conclusion}: Phase 1 exceeded the 10$\times$ target. Single forward pass
over enwik9 now takes 7.4 hours instead of 99 hours.

\subsection{Phase 2 Results: OpenMP Parallelization}

Implemented parallel processing of independent sequences using OpenMP.
Each thread processes its own segment of enwik9 with the Phase 1 SIMD kernel.

\textbf{System}: AMD EPYC 7571 with 2 vCPUs (1 core, 2 threads via SMT).

\textbf{Results}:
\begin{center}
\begin{tabular}{lrrr}
\toprule
Threads & Throughput & enwik9 Time & Total Speedup \\
\midrule
1 (Phase 1 only) & 34,000 bytes/s & 8.2 hours & 12.2$\times$ \\
2 & 42,700 bytes/s & 6.5 hours & 15.2$\times$ \\
4 (hyperthreading) & 43,100 bytes/s & 6.4 hours & 15.4$\times$ \\
\bottomrule
\end{tabular}
\end{center}

\textbf{Analysis}: SMT provides $\sim$1.3$\times$ speedup over single-threaded.
With more physical cores, near-linear scaling is expected up to memory bandwidth limits.

\textbf{Conclusion}: Phase 2 achieves 15.4$\times$ total speedup on this 2-vCPU system.
On a machine with 8+ cores, we expect 50+$\times$ speedup (target: 2 hours).

\subsection{Phase 3: GPU Acceleration}

\textit{Skipped---no GPU available on target system.}

\section{Conclusion}

\subsection{Summary of Optimizations}

\begin{center}
\begin{tabular}{llrr}
\toprule
Phase & Optimization & Throughput & Speedup \\
\midrule
0 & Original hutter.c & 2,800 bytes/s & 1.0$\times$ \\
1 & SIMD (AVX2 + FMA) & 37,400 bytes/s & 13.3$\times$ \\
2 & + OpenMP (2 threads) & 42,700 bytes/s & 15.2$\times$ \\
\bottomrule
\end{tabular}
\end{center}

\subsection{Time for enwik9 Forward Pass}

\begin{center}
\begin{tabular}{lr}
\toprule
Version & Time \\
\midrule
Original & 99 hours (4.1 days) \\
Phase 1 (SIMD) & 7.4 hours \\
Phase 2 (+ OpenMP) & 6.5 hours \\
\bottomrule
\end{tabular}
\end{center}

\subsection{Key Techniques}

\begin{enumerate}
\item \textbf{Compiler flags}: \texttt{-O3 -march=native -ffast-math} provides 4$\times$ baseline improvement
\item \textbf{8-way loop unrolling}: Maximizes instruction-level parallelism
\item \textbf{FMA instructions}: Fused multiply-add in single cycle
\item \textbf{Fast tanh}: Pad\'{e} polynomial approximation avoids expensive \texttt{tanhf}
\item \textbf{OpenMP parallelization}: Scales with available cores
\end{enumerate}

\subsection{Files}

\begin{itemize}
\item \texttt{rnn\_fast.h}: Drop-in SIMD replacement for \texttt{rnn\_step()}
\item \texttt{parallel\_batch.c}: OpenMP parallel benchmark
\end{itemize}

\subsection{Impact on Tick-Tock Cycle}

With 15$\times$ speedup, a single forward pass takes 6.5 hours instead of 99 hours.
Training epochs (multiple forward + backward passes) are now feasible in a day
rather than a week. This enables practical iteration on the tick-tock methodology.

\end{document}
