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
项目状态：
已结题

项目摘要

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用于同态密码学，多项式的乘法和多个长度的乘法。尽管NTT内核包含剩余的乘法，但已知通过使用蒙哥马利或shoup乘法，只能通过乘法，加法和减法和移位操作执行剩余乘法，而无需实质性地执行时间耗时的划分。在检查NTT内核中的操作数量时，发现Shoup乘法小于蒙哥马利乘法。因此，使用SIMD指令，Intel Advanced Vector Extensions 512（AVX-512）指令加速了多个SHOUP乘法。此外，将适用于快速傅立叶变换（FFT）并行的六步FFT算法应用于NTT，以构建六步NTT算法，并使用OpenMP进行并行化。多核处理器的性能评估表明，NTT的拟议实现比Intel同构加密（HE）加速库中包含的NTT的实现更快，该加速库尚未并行化。此外，在国际会议上提出了2022年进行的研究结果。

项目成果

期刊论文数量（10）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

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

DOI：
发表时间：
2021
期刊：
影响因子：
0
作者：
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
影响因子：
0
作者：
齋藤光貴;渡辺知恵美;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
影响因子：
0
作者：
齋藤光貴;渡辺知恵美;Daisuke Takahashi
通讯作者：
Daisuke Takahashi

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

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

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
石原詢大;天笠俊之;渡辺知恵美;高橋大介
通讯作者：
高橋大介

Parallel Implementation of FFT in a Finite Field

有限域中 FFT 的并行实现

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
Shunta Ishihara;Chiemi Watanabe;Toshiyuki Amagasa;Daisuke Takahashi
通讯作者：
Daisuke Takahashi

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

高橋大介其他文献

アントラキノン-ヒドラジドハイブリッドによる還元糖の選択的光分解とAGEs 生成阻害への応用

使用蒽醌-酰肼杂化物选择性光解还原糖及其在抑制 AGEs 产生中的应用

DOI：
发表时间：
2016
期刊：
影响因子：
0
作者：
高城美智;高橋大介;戸嶋一敦
通讯作者：
戸嶋一敦

非負値テンソル因子分解を用いたR3 冬の札幌圏大雪における断面交通量分析

基于非负张量分解的札幌地区冬季大雪R3断面交通分析

DOI：
发表时间：
2023
期刊：
影响因子：
0
作者：
森雅弘;植原量行;高橋大介;小林憲一;佐藤嘉洋，円山琢也;橋本晟矢，杉浦聡志
通讯作者：
橋本晟矢，杉浦聡志

沿岸潮位から見た駿河湾の海洋構造の季節変動

从沿岸潮位观察骏河湾海洋结构的季节变化

DOI：
发表时间：
2023
期刊：
影响因子：
0
作者：
高橋大介;植原量行
通讯作者：
植原量行

インドールプレニル基転移酵素の動的立体構造基盤の確立と酵素触媒機能の拡張

吲哚异戊二烯基转移酶动态构象基础的建立及酶催化功能的扩展

DOI：
发表时间：
2014
期刊：
影响因子：
0
作者：
外川翔太;高橋大介;戸嶋一敦;植村　朋弘;森田洋行
通讯作者：
森田洋行

ミヤコバンカーのナシにおける設置方法と土着カブリダニの発生消長から見たハダニ防除効果

从梨宫古沙坑的安装方法看红蜘蛛的防治效果及本土红蜘蛛的发生与减少

DOI：
发表时间：
2023
期刊：
影响因子：
0
作者：
城下沙織;高橋大介;戸嶋一敦;Noureldin Ghazy・Naoki Takeda・Masanobu Yamamoto・Yasser Mohammad・Kotaro Mori・Takeshi Suzuki;小川　展弘;山口晃一・吉村忠浩・三溝啓太・山中英・森光太郎
通讯作者：
山口晃一・吉村忠浩・三溝啓太・山中英・森光太郎