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年度に行った研究成果を国際会議で発表した。

在 2022 财年，我们实施并评估了数论变换 (NTT) 的性能，它是复数到环和域的离散傅里叶变换的推广。 NTT 用于同态加密、多项式乘法和多精度数乘法。虽然NTT的内核包括模乘法，但众所周知，通过使用蒙哥马利乘法和Shoup乘法，可以仅使用乘法、加法、减法和移位运算来执行模乘法，实际上消除了耗时的除法。当我们调查 NTT 内核中的运算数量时，很明显使用 Shoup 乘法比使用 Montgomery 乘法要少。因此，我们使用英特尔高级矢量扩展 512 (AVX-512) SIMD 指令加速多个 Shoup 乘法。此外，我们将适合并行化快速傅立叶变换（FFT）的六步FFT算法应用于NTT，构建了六步NTT算法，并使用OpenMP对其进行了并行化。多核处理器上的性能评估结果表明，所提出的 NTT 实现比英特尔同态加密 (HE) 加速库中包含的非并行化 NTT 实现更快。此外，2022年进行的研究成果还在国际会议上公布。

项目成果

二次元分割を用いた並列三次元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