收藏切换
NTT Butterfly Arithmetic Acceleration Based on Dataflow Architecture
收藏切换
Hongbo Shi1, 2, Zhihua Fan1, *, Wenming Li1, 2, Zhiyuan Zhang1, 2, Yudong Mu1, 2, Xiaochun Ye1, 2, Xuejun An1, 2
Journal of Computer Research and Development | 2025, 62(6) : 1547 - 1561
Less
收藏切换
Journal of Computer Research and Development | 2025, 62(6): 1547-1561
• Chip Architecture Design •
NTT Butterfly Arithmetic Acceleration Based on Dataflow Architecture
Full
Hongbo Shi1, 2, Zhihua Fan1, *, Wenming Li1, 2, Zhiyuan Zhang1, 2, Yudong Mu1, 2, Xiaochun Ye1, 2, Xuejun An1, 2
Affiliations
  • 1State Key Lab of Processors (Institute of Computing, Chinese Academy of Sciences), Beijing 100190
  • 2School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing 100049
  • born in 2002. Bachelor. His main research interests include dataflow architecture and high-performance computing

    born in 1996. PhD, assistant professor. His main research interests include dataflow architecture, programming model, and reconfigurable architecture

    born in 1988. PhD, associate professor. His main research interests include high-throughput processor architecture, dataflow architecture, and software simulation

    born in 2000. PhD candidate. His main research interests include high-performance computing, dataflow, and reconfigurable architecture

    born in 2001. PhD candidate. His main research interests include dataflow architecture, dataflow graph mapping, and reconfigurable architecture

    born in 1983. PhD,professor. His main research interests include high-performance computer architecture and software simulation

    born in 1966. PhD,professor. His main research interests include programming model and processor architecture

About Author:

born in 2002. Bachelor. His main research interests include dataflow architecture and high-performance computing

born in 1996. PhD, assistant professor. His main research interests include dataflow architecture, programming model, and reconfigurable architecture

born in 1988. PhD, associate professor. His main research interests include high-throughput processor architecture, dataflow architecture, and software simulation

born in 2000. PhD candidate. His main research interests include high-performance computing, dataflow, and reconfigurable architecture

born in 2001. PhD candidate. His main research interests include dataflow architecture, dataflow graph mapping, and reconfigurable architecture

born in 1983. PhD,professor. His main research interests include high-performance computer architecture and software simulation

born in 1966. PhD,professor. His main research interests include programming model and processor architecture

Published: 2025-06-02 doi: 10.7544/issn1000-1239.202550160
Outline
收藏切换

Fully homomorphic encryption (FHE), which enables computation on encrypted data without decryption throughout the entire processing flow, offers a promising solution for privacy preservation in cloud computing and other distributed environments. However, the practical deployment of FHE remains significantly constrained by its high computational complexity, poor data locality, and limited parallelism. Among the core operations in FHE, the number theoretic transform (NTT) plays a pivotal role in determining overall system performance. We target the butterfly computation pattern, which is central to the NTT algorithm, and propose a high-efficiency NTT accelerator architecture based on a dataflow computing model. First, we design an RVFHE extension instruction set tailored for NTT butterfly operations, incorporating custom modular multiplication and modular addition/subtraction units to enhance the efficiency of modular arithmetic. Second, we introduce a novel NTT data reordering scheme, combined with a structured butterfly address generation strategy, to reduce the control complexity and access conflicts associated with cross-row and cross-column data exchanges. Finally, we develop a dataflow-driven NTT accelerator architecture that leverages data dependency-triggered execution to enable efficient on-chip scheduling and data reuse, thereby exploiting instruction-level parallelism to the fullest extent. Experimental results demonstrate that, compared with NVIDIA GPU, the proposed architecture achieves up to 8.96 times speedup and 8.53 times improvement in energy efficiency. Furthermore, compared with state-of-the-art dedicated NTT accelerators, our design delivers a 1.37 times performance gain.

dataflow  /  full homomorphic encryption (FHE)  /  NTT algorithm  /  butterfly computation  /  RISC-V instruction set
石泓博, 范志华, 李文明, 张志远, 穆宇栋, 叶笑春, 安学军. 基于数据流架构的NTT蝶式计算加速. 计算机研究与发展, 2025 , 62 (6) : 1547 -1561 . DOI: 10.7544/issn1000-1239.202550160
Hongbo Shi, Zhihua Fan, Wenming Li, Zhiyuan Zhang, Yudong Mu, Xiaochun Ye, Xuejun An. NTT Butterfly Arithmetic Acceleration Based on Dataflow Architecture[J]. Journal of Computer Research and Development, 2025 , 62 (6) : 1547 -1561 . DOI: 10.7544/issn1000-1239.202550160
Year 2025 volume 62 Issue 6
99
44
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202550160
  • Receive Date:2025-03-01
  • Online Date:2026-11-10
  • Published:2025-06-02
Article Data
Affiliations
History
  • Received:2025-03-01
  • Revised:2025-04-08
Affiliations
    1State Key Lab of Processors (Institute of Computing, Chinese Academy of Sciences), Beijing 100190
    2School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing 100049
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202550160
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT