TL;DR
This paper introduces CROSS, a compiler framework that enables Homomorphic Encryption (HE) workloads to run efficiently on AI accelerators like Google TPUs. By transforming HE algorithms to leverage the TPUs' specialized hardware, CROSS achieves state-of-the-art energy efficiency and throughput, bridging the gap between expensive dedicated HE ASICs and general-purpose hardware.
What Problem Does This Paper Address?
Homomorphic Encryption (HE) is a powerful cryptographic technique that allows computations on encrypted data, crucial for privacy-preserving cloud services. However, HE is notoriously computationally expensive, leading to massive performance overheads. While GPUs have been used to accelerate HE, they still lag significantly behind dedicated HE ASICs in energy efficiency. This paper tackles the challenge of achieving ASIC-level energy efficiency for HE without the prohibitive cost of custom hardware. The authors propose using existing, widely available AI accelerators, specifically Google's TPUs, which possess powerful matrix multiplication units (MXUs) and coarse-grained memory architectures. The core problem is that current HE algorithms, optimized for GPUs, are ill-suited for TPUs due to mismatches in precision requirements and data manipulation granularity, leading to underutilization and performance degradation.
Methods
The paper introduces CROSS, a compiler framework with two key novel techniques:
- Basis-Aligned Transformation (BAT): This technique refactors high-precision modular arithmetic (common in HE) into dense, low-precision (INT8) matrix multiplications. This allows HE workloads to fully utilize the high-throughput MXUs on TPUs, which are typically idle when running GPU-optimized HE algorithms. BAT achieves this by pre-computing known parameters offline and transforming them into a format suitable for efficient matrix operations.
- Memory-Aligned Transformation (MAT): This method addresses the inefficiency of fine-grained data reordering (like transposing and shuffling) on TPUs' coarse-grained memory. MAT embeds these reordering operations directly into the computation kernels by transforming parameters offline. This creates "layout-invariant" kernels, eliminating costly runtime data manipulation and improving memory efficiency.
Datasets
Not discussed in the paper. The evaluation uses HE workloads and benchmarks, not traditional machine learning datasets for training.
Key Insights and Ideas
- AI ASICs as a viable path to efficient HE: The paper demonstrates that existing AI accelerators, not just specialized HE ASICs, can achieve competitive energy efficiency for HE. This opens up a more accessible route to widespread adoption of privacy-preserving computation.
- Architectural mismatch is the key bottleneck: The core challenge isn't just raw compute power, but how HE algorithms' computational patterns (high precision, fine-grained data movement) clash with the architecture of AI accelerators (low precision, coarse-grained memory).
- Compiler-level transformations are crucial: Instead of hardware modifications, the authors show that intelligent compiler transformations (BAT and MAT) can effectively bridge the architectural gap, unlocking the potential of AI hardware for HE.
- Pre-computation is key to efficiency: Both BAT and MAT heavily rely on offline pre-computation of parameters to eliminate runtime overheads, a critical strategy for optimizing performance on hardware with different architectural strengths.
Key Results
- Record-breaking NTT throughput: CROSS on a Google TPU v6e achieved up to 1.43x higher throughput for the Number Theoretic Transform (NTT) compared to WarpDrive on an NVIDIA A100.
- Exceptional energy efficiency: CROSS achieved significant throughput-per-watt improvements over various HE libraries and platforms:
- 451x over OpenFHE
- 7.81x over WarpDrive
- 1.83x over FIDESlib
- 1.31x over FAB
- 1.86x over HEAP
- 1.15x over Cheddar
- Competitive with specialized ASICs: Even when compared to dedicated HE ASICs like CraterLake, CROSS on TPUs narrowed the performance gap, demonstrating its strong energy efficiency.
- Improved HE kernel performance: BAT and MAT individually showed significant speedups for key HE operations like modular multiplication and NTT.
Limitations and Future Work
- Inter-kernel optimization: The paper notes that CROSS doesn't explore pipelining and fusion between sequential vectorized operators and matrix multiplications in bootstrapping. This leads to intermediate results being written back to HBM, increasing memory access.
- Arbitrary permutation embedding: While MAT can embed many reordering operations, it cannot handle all arbitrary permutations in automorphism into computation. This remains an open question.
- Hardware-friendly moduli: Dedicated HE ASICs benefit from hardware-optimized moduli, which CROSS's more general approach doesn't leverage, potentially incurring a performance penalty.
- Future Work: The authors suggest exploring application-level optimizations and end-to-end benchmarks for HE workloads. They also highlight the need for better solutions for arbitrary permutation embedding and leveraging hardware-friendly moduli.
Summary updated