Research on algorithm of fast Fourier transform in exascale system

点击翻译按钮获取中文摘要

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