Research on algorithm of fast Fourier transform in exascale system

百亿亿级系统快速傅里叶变换算法研究

• 批准号: 19K11989
• 负责人: 高橋 大介
• 金额: $ 2.25万
• 依托单位: University of Tsukuba
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K11989/
• 关键词: エクサスケールシステム; 高速フーリエ変換; 数論変換; メニーコアプロセッサ; SIMD化; 並列化; GPU; 最適化

2022年度は複素数上の離散フーリエ変換（Discrete Fourier Transform）を環や体上に一般化した数論変換（Number-Theoretic Transform、以下NTT）の実装および性能評価を行った。NTTは準同型暗号、多項式の乗算および多倍長数の乗算に用いられている。NTTのカーネルには剰余乗算が含まれているが、Montgomery乗算やShoup乗算を用いることで時間の掛かる除算を実質的に行うことなく、乗算、加減算およびシフト演算のみで剰余乗算を行えることが知られている。NTTのカーネルにおける演算回数を検討したところ、Shoup乗算を用いた方がMontgomery乗算よりも少ないことが明らかになった。そこで、複数のShoup乗算をSIMD命令であるIntel Advanced Vector Extensions 512 (AVX-512）命令を用いて高速化した。さらに、高速フーリエ変換（Fast Fourier Transform，以下FFT）の並列化に適しているsix-step FFTアルゴリズムをNTTに適用し、six-step NTTアルゴリズムを構築するとともに、OpenMPを用いて並列化を行った。メニーコアプロセッサにおける性能評価の結果、提案するNTTの実装は並列化が行われていないIntel Homomorphic Encryption（HE）Acceleration Libraryに含まれているNTTの実装よりも高速であることを示した。また、2022年度に行った研究成果を国際会議で発表した。

In 2022, the implementation of Discrete Fourier Transform on complex prime numbers and Number-Theoretic Transform on ring bodies was evaluated. NTT is a quasi-isotypic code, a polynomial, and a multiple. NTT's calculation of the sum of the The NTT's algorithm is based on the Montgomery algorithm. The Intel Advanced Vector Extensions 512 (AVX-512) command is used to speed up the computation of complex numbers. Fast Fourier Transform (FFT) parallelization is applied to NTT, six-step NTT parallelization is applied to OpenMP parallelization. Intel Homomorphic Encryption (HE) Acceleration Library contains the results of performance evaluation and proposal for NTT implementation. The 2022 annual research results were presented at the International Conference.

项目成果

二次元分割を用いた並列三次元FFTにおける計算と通信のオーバーラップの自動チューニング

使用 2D 分区自动调整并行 3D FFT 中的计算和通信重叠

• 发表时间: 2021
• 作者: Shunta Ishihara;Chiemi Watanabe;Toshiyuki Amagasa;高橋大介
• 通讯作者: 高橋大介

Implementation of Parallel 3-D Real FFT with 2-D Decomposition on Intel Xeon Phi Clusters

在英特尔至强融核集群上实现并行 3-D Real FFT 和 2-D 分解

• DOI: 10.1007/978-3-030-43229-4_14
• 发表时间: 2020
• 期刊: Proc. 13th International Conference on Parallel Processing and Applied Mathematics (PPAM 2019), Part I, Lecture Notes in Computer Science
• 作者: 齋藤光貴;渡辺知恵美;Daisuke Takahashi
• 通讯作者: Daisuke Takahashi

Fast Multiple Montgomery Multiplications Using Intel AVX-512IFMA Instructions

使用 Intel AVX-512IFMA 指令进行快速多重蒙哥马利乘法

• DOI: 10.1007/978-3-030-58814-4_52
• 发表时间: 2020
• 期刊: Proc. 20th International Conference on Computational Science and Its Applications (ICCSA 2020), Part V, Lecture Notes in Computer Science
• 作者: 齋藤光貴;渡辺知恵美;Daisuke Takahashi
• 通讯作者: Daisuke Takahashi

Xeon Phiクラスタにおける二次元分割を用いた並列三次元実数FFTの実現と評価

Xeon Phi 集群中使用 2D 分区的并行 3D 实数 FFT 的实现和评估

• 发表时间: 2019
• 作者: 石原詢大;天笠俊之;渡辺知恵美;高橋大介
• 通讯作者: 高橋大介

Parallel Implementation of FFT in a Finite Field

有限域中 FFT 的并行实现

• 发表时间: 2022
• 作者: Shunta Ishihara;Chiemi Watanabe;Toshiyuki Amagasa;Daisuke Takahashi
• 通讯作者: Daisuke Takahashi