Reproduce “Theodosian: A Deep Dive into Memory-Hierarchy-Centric FHE Acceleration” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Wonseok Choi, Hyunah Yu, Jongmin Kim, Hyesung Ji, Jaiyoung Park, Jung Ho Ahn
Researchers from Seoul National University developed Theodosian, a set of memory-hierarchy-centric optimizations for Fully Homomorphic Encryption (FHE) on modern GPUs. It reduces CKKS bootstrapping latency for 32,768 complex numbers to 15.2ms on an RTX 5090 by addressing L2 cache bandwidth limitations and improving hardware utilization, achieving up to 1.83x speedup over prior state-of-the-art methods.
Key insights
- Key FHE polynomial kernels (NTT and BConv) are fundamentally bottlenecked by L2 cache write bandwidth (SM-to-L2 NoC) on modern GPUs, rather than solely by DRAM or compute throughput.
- Removing 'core' computational operations from NTT and BConv kernels resulted in only marginal performance improvements (7% to 20%), confirming memory access as the primary constraint.
- For configurations with low limb counts, FHE kernels exhibit severe hardware underutilization due to insufficient intra-kernel parallelism, leading to inefficient GPU resource use.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.