Anaheim: Architecture and Algorithms for Processing Fully Homomorphic Encryption in Memory

Fully homomorphic encryption (FHE) is a promising solution for privacy-preserving cloud computing as it enables computations on sensitive data without any risk of data leakage. Despite the significant attention FHE has received, substantial computation and memory demands make it hardly practical for real-world applications. We propose a readily available and practical hardware solution to tackle this problem by using GPUs. GPUs have adequate computational and memory resources to handle complex operations in FHE, including number-theoretic transform (NTT), on which most prior work has deeply focused. However, through detailed analyses, we discover that the performance bottleneck on GPUs is primarily due to simpler element-wise operations, which are limited by off-chip memory (DRAM) bandwidth. Motivated by these observations, we develop Anaheim, a processing-in-memory (PIM) architecture for FHE. We develop optimized FHE execution flows and an end-toend software framework for using PIM with GPUs. Also, we design a versatile PIM unit that handles various modular integer arithmetic PIM instructions, along with an efficient data mapping and associated PIM execution algorithms that minimize data access overhead by leveraging the internal structure of DRAM. Our concerted efforts substantially enhance the performance and energy efficiency of various FHE workloads on GPUs.