Logo image
Back
Generating High-Performance Number Theoretic Transform Implementations for Vector Architectures
Conference proceeding

Generating High-Performance Number Theoretic Transform Implementations for Vector Architectures

Naifeng Zhang, Austin Ebel, Negar Neda, Patrick Brinich, Benedict Reynwar, Andrew G. Schmidt, Mike Franusich, Jeremy Johnson, Brandon Reagen and Franz Franchetti
2023 IEEE High Performance Extreme Computing Conference (HPEC), pp 1-7
25 Sep 2023
DOI: https://doi.org/10.1109/HPEC58863.2023.10363559

Abstract

code generation Computer architecture Encoding Fully homomorphic encryption Generators Libraries number theoretic transform Rendering (computer graphics) SPIRAL Spirals Transforms vectorization
Fully homomorphic encryption (FHE) offers the ability to perform computations directly on encrypted data by encoding numerical vectors onto mathematical structures. However, the adoption of FHE is hindered by substantial overheads that make it impractical for many applications. Number theoretic transforms (NTTs) are a key optimization technique for FHE by accelerating vector convolutions. Towards practical usage of FHE, we propose to use SPIRAL, a code generator renowned for generating efficient linear transform implementations, to generate high-performance NTT on vector architectures. We identify suitable NTT algorithms and translate the dataflow graphs of those algorithms into SPIRAL's internal mathematical representations. We then implement the entire workflow required for generating efficient vectorized NTT code. In this work, we target the Ring Processing Unit (RPU), a multitile long vector accelerator designed for FHE computations. On average, the SPIRAL-generated NTT kernel achieves a 1.7x speedup over naive implementations on RPU, showcasing the effectiveness of our approach towards maximizing performance for NTT computations on vector architectures.

Metrics

7 Record Views
2 citations in Scopus

Details

Logo image