Theodosian: A Deep Dive into Memory-Hierarchy-Centric FHE Acceleration

Wonseok Choi, Hyunah Yu, Jongmin Kim, Hyesung Ji, Jaiyoung Park, Jung Ho Ahn

TL;DR

This paper introduces "Theodosian," a novel set of memory-hierarchy-aware optimizations for Fully Homomorphic Encryption (FHE) on GPUs. By deeply analyzing the GPU's memory hierarchy, Theodosian significantly boosts FHE performance by improving effective memory throughput and hardware utilization, achieving up to 1.83x speedup over existing state-of-the-art.

What Problem Does This Paper Address?

Fully Homomorphic Encryption (FHE) is a revolutionary cryptographic technique that allows computations on encrypted data, promising enhanced privacy in cloud and edge computing. However, FHE schemes, particularly the popular CKKS scheme, are computationally intensive and demand substantial memory resources. This has led to extensive research in accelerating FHE, with GPUs emerging as a promising platform due to their massive parallelism and high memory bandwidth.

Despite significant progress, existing FHE acceleration efforts on GPUs often focus narrowly on DRAM bandwidth or compute-centric optimizations. This paper argues that such approaches are insufficient for modern GPUs. The authors identify a critical bottleneck within the GPU's entire memory hierarchy, specifically the L2 cache, which, despite its increased capacity and bandwidth, still limits performance due to insufficient intra-kernel parallelism and memory access patterns. This creates a "memory wall" that current optimizations struggle to overcome. The paper aims to provide a comprehensive microarchitectural analysis of CKKS on GPUs and introduce optimizations that address this deeper memory hierarchy bottleneck.

Methods

Theodosian is built upon a detailed microarchitectural analysis of CKKS kernels on modern GPUs, particularly focusing on the memory hierarchy. The authors employ NVIDIA's Nsight Compute to analyze GPU performance counters, examining compute pipeline utilization and L2 cache behavior.

Their proposed optimizations are:

  • L2-aware Multi-Polynomial Caching: This strategy batches operation sequences to keep their working sets resident in the L2 cache, enhancing hardware utilization without increasing DRAM traffic. It's designed to leverage the larger L2 cache of modern GPUs more effectively than previous methods.
  • Complementary Pipelining: This technique pipelines DRAM-bound and L2-bound kernels together. By interleaving operations with different memory access patterns, it aims to balance the utilization of both DRAM and L2 cache, thereby improving aggregate memory throughput.
  • CUDA Graphs: To address the overhead of numerous fine-grained kernel launches in FHE bootstrapping, Theodosian utilizes CUDA Graphs. This allows submitting the entire computation graph to the GPU in a single CPU launch, significantly reducing kernel launch latency.

Additionally, the paper incorporates algorithmic optimizations, such as an improved BConv kernel that eliminates intermediate modular reductions by carefully selecting moduli, and explores the impact of advanced techniques like OverModRaise.

Datasets

The paper does not explicitly mention training datasets. Evaluation is performed on representative FHE workloads, including:

  • Bootstrapping: A fundamental operation for refreshing ciphertexts and reducing noise.
  • Key-switching: A frequent operation sequence in FHE.
  • HELR (Logistic Regression): Evaluated on MNIST images.
  • ResNet20: A convolutional neural network for image inference.

The authors use parameter sets common in the FHE community, aiming for 128-bit security. They compare their approach against existing FHE libraries and implementations like Cheddar, HEaaN-GPU, WarpDrive, FIDESlib, and HEAAN2.

Key Insights and Ideas

  • The "Memory Wall" is Deeper: The dominant bottleneck in GPU-based FHE is not just DRAM bandwidth, but a more nuanced limitation within the entire memory hierarchy, including the L2 cache.
  • L2 Cache is Underutilized: Modern GPUs have large L2 caches, but existing FHE optimizations don't fully exploit their capacity and bandwidth due to insufficient intra-kernel parallelism.
  • Kernel Fusion Has Limits: While kernel fusion is beneficial, its effectiveness is constrained by shared memory capacity and the differing parallelism models of FHE kernels (e.g., NTT vs. BConv).
  • Batching is Key, But Needs Hierarchy Awareness: Batching operations can improve hardware utilization, but it must be done with an awareness of the L2 cache's capacity to avoid overwhelming it and increasing DRAM traffic.
  • Complementary Bottlenecks Offer Synergy: Pipelining kernels with different memory access patterns (DRAM-bound vs. L2-bound) can lead to better overall memory system utilization.
  • CUDA Graphs are Crucial for Fine-Grained Workloads: For FHE operations involving many small kernels, like bootstrapping, the overhead of kernel launches can be significant, making CUDA Graphs a vital optimization.

Key Results

  • Significant Speedups: Theodosian achieves 1.45-1.83× performance improvements over the highly optimized Cheddar baseline on an RTX 5090.
  • Reduced Bootstrapping Latency: Bootstrapping latency for 32,768 complex numbers is reduced from 22.1ms to 15.2ms. With additional algorithmic optimizations, this further drops to 12.8ms, setting a new state-of-the-art for GPU FHE performance.
  • Broad GPU Compatibility: Theodosian demonstrates consistent improvements (1.26-1.54×) over Cheddar on A100 and H100 GPUs.
  • Outperforming Existing Libraries: Theodosian achieves 9.7-12.5× lower bootstrapping latency compared to FIDESlib for the same security level.
  • Algorithmic Gains: Incorporating advanced algorithmic optimizations (like OverModRaise) provides an additional 1.27× speedup for bootstrapping, even outperforming the proprietary HEAAN2.

Limitations and Future Work

  • Remaining Headroom: Despite significant gains, Theodosian still achieves a bootstrapping latency that is 1.73× higher than the theoretical bound imposed by global memory accesses. This suggests that further improvements are limited by the fundamental memory wall.
  • Algorithmic and Hardware Co-design: The authors suggest that future work should focus on shifting the memory wall itself. This could involve developing memory-aware cryptographic algorithms or hardware designs with even higher on-chip memory bandwidth.
  • Exploration of Other FHE Schemes: While this work focuses on CKKS, the insights into GPU memory hierarchy bottlenecks could be valuable for optimizing other FHE schemes like TFHE, which have different arithmetic structures.
  • Multi-GPU Scaling: The current work focuses on single-GPU optimization. Future research could explore how these optimizations translate to multi-GPU environments.

Summary updated

BibTeX
@inproceedings{choi2026theodosian,
  author = {Wonseok Choi and Hyunah Yu and Jongmin Kim and Hyesung Ji and Jaiyoung Park and Jung Ho Ahn},
  title = {{Theodosian: A Deep Dive into Memory-Hierarchy-Centric FHE Acceleration}},
  booktitle = {ISPASS},
  year = {2026},
  doi = {10.1109/ispass69572.2026.00037},
}
Figure