TY - GEN
T1 - CiFlow
T2 - 2024 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2024
AU - Neda, Negar
AU - Ebel, Austin
AU - Reynwar, Benedict
AU - Reagen, Brandon
N1 - Publisher Copyright:
© 2024 IEEE.
PY - 2024
Y1 - 2024
N2 - Homomorphic encryption (HE) is a privacy-preserving computation technique that enables computation on encrypted data. Today, the potential of HE remains largely unrealized as it is impractically slow, preventing it from being used in real applications. A major computational bottleneck in HE is the key-switching operation, accounting for approximately 70 % of the overall HE execution time and involving a large amount of data for inputs, intermediates, and keys. Prior research has focused on hardware accelerators to improve HE performance, typically featuring large on-chip SRAMs and high off-chip bandwidth to deal with large scale data. In this paper, we present a novel approach to improve key-switching performance by rigorously analyzing its dataflow. Our primary goal is to optimize data reuse with limited on-chip memory to minimize off-chip data movement. We introduce three distinct dataflows: Max-Parallel (MP), Digit-Centric (DC), and Output-Centric (OC), each with unique scheduling approaches for key-switching computations. Through our analysis, we show how our proposed Output-Centric technique can effectively reuse data by significantly lowering the intermediate key-switching working set and alleviating the need for massive off-chip band-width. We thoroughly evaluate the three dataflows using the RPU, a recently published vector processor tailored for ring processing algorithms, which includes HE. This evaluation considers sweeps of bandwidth and computational throughput, and whether keys are buffered on-chip or streamed. With OC, we demonstrate up to 4.16 x speedup over the MP dataflow and show how OC can save 12.25 x on-chip SRAM by streaming keys for minimal performance penalty.
AB - Homomorphic encryption (HE) is a privacy-preserving computation technique that enables computation on encrypted data. Today, the potential of HE remains largely unrealized as it is impractically slow, preventing it from being used in real applications. A major computational bottleneck in HE is the key-switching operation, accounting for approximately 70 % of the overall HE execution time and involving a large amount of data for inputs, intermediates, and keys. Prior research has focused on hardware accelerators to improve HE performance, typically featuring large on-chip SRAMs and high off-chip bandwidth to deal with large scale data. In this paper, we present a novel approach to improve key-switching performance by rigorously analyzing its dataflow. Our primary goal is to optimize data reuse with limited on-chip memory to minimize off-chip data movement. We introduce three distinct dataflows: Max-Parallel (MP), Digit-Centric (DC), and Output-Centric (OC), each with unique scheduling approaches for key-switching computations. Through our analysis, we show how our proposed Output-Centric technique can effectively reuse data by significantly lowering the intermediate key-switching working set and alleviating the need for massive off-chip band-width. We thoroughly evaluate the three dataflows using the RPU, a recently published vector processor tailored for ring processing algorithms, which includes HE. This evaluation considers sweeps of bandwidth and computational throughput, and whether keys are buffered on-chip or streamed. With OC, we demonstrate up to 4.16 x speedup over the MP dataflow and show how OC can save 12.25 x on-chip SRAM by streaming keys for minimal performance penalty.
KW - Accelerator
KW - Fully Homomorphic Encryption
KW - Key-switching
UR - http://www.scopus.com/inward/record.url?scp=85199881424&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85199881424&partnerID=8YFLogxK
U2 - 10.1109/ISPASS61541.2024.00016
DO - 10.1109/ISPASS61541.2024.00016
M3 - Conference contribution
AN - SCOPUS:85199881424
T3 - Proceedings - 2024 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2024
SP - 61
EP - 72
BT - Proceedings - 2024 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2024
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 5 May 2024 through 7 May 2024
ER -