並列計算機における高速フーリエ変換のアルゴリズムに関する研究

并行计算机上的快速傅里叶变换算法研究

• 批准号: 12780190
• 负责人: 高橋 大介
• 金额: $ 1.34万
• 依托单位: University of Tsukuba (2001)Saitama University (2000)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-12780190/
• 关键词: 高速フーリエ変換; 並列計算機; キャッシュメモリ

本研究の目的は,並列計算機における高速フーリエ変換(fast Fourier transform,以下FFT)のアルゴリズムの実現および評価が挙げられる。近年,並列計算機の普及に伴い,並列FFTアルゴリズムが様々な研究者によって提案されており,ライブラリとなっているものも多い。ところが,これらの並列FFTアルゴリズムはデータ数がN=2^pのように,2のべき乗で表される場合についてのものが多い。そこで本研究では,並列計算機においてデータ数がN=2^p3^q5^rの場合について並列FFTアルゴリズムの実現および評価を行った。並列計算機は,大きく分けて共有メモリ型並列計算機と分散メモリ型並列計算機があるが,それぞれのアーキテクチャにおいて最適な並列FFTアルゴリズムは異なるために,本研究では異なるアーキテクチャについてそれぞれ並列FFTアルゴリズムを実現し,評価を行った。そして,これらの並列FFTアルゴリズムを実際に共有メモリ型および分散メモリ型の並列計算機上に実現し,今までの逐次FFTアルゴリズムに対する性能向上率を評価した。本研究で実現した並列FFTアルゴリズムでは,キャッシュブロッキングという手法を用いてキャッシュメモリを有効に活用することにより,共有メモリ型並列計算機と分散メモリ型並列計算機という複数のプラットホームにおいて,従来提案されている並列FFTアルゴリズムに比べて高い性能を示すことが分かった.またこれらの研究成果をもとに,雑誌論文や国際会議において研究成果を発表した。

这项研究的目的是实现和评估并行计算机中快速傅立叶变换（FFT）的算法。近年来，随着平行计算机的传播，各种研究人员已经提出了平行的FFT算法，许多研究人员已成为库。但是，这些平行的FFT算法大多在数据数表示为2的幂时，例如n = 2^p。因此，在这项研究中，我们在平行计算机中的数据数为n = 2^p3^q5^r的情况下实现并评估了平行的FFT算法。平行计算机可以广泛分为共享存储器并行计算机和分布式存储器并行计算机，但是每个体系结构的最佳并行FFT算法都是不同的，因此在这项研究中，我们意识到了不同体系结构的并行FFT算法并评估了它们。这些并行的FFT算法实际上是在共享内存和分布式存储器并行计算机上实现的，并且评估了先前顺序FFT算法的性能提高率。这项研究中实现的平行FFT算法表明，通过使用一种称为“缓存阻塞的方法”有效地利用缓存存储器，发现性能高于多个平台上常规提出的并行FFT算法的性能，例如共享存储器平行计算机和分布式并行计算机。基于这些研究结果，在期刊论文和国际会议上提出了研究结果。

项目成果

Daisuke Takahashi: "A Mixed-Radix Parallel Three-Dimensional FFT Algorithm on Clusters of Vector SMPs"Proc.Tenth SIAM Conference on Parallel Processing for Scientific Computing. (CD-ROM). (2001)

Daisuke Takahashi：“矢量 SMP 簇上的混合基并行三维 ​​FFT 算法”Proc.第十届 SIAM 科学计算并行处理会议。

Daisuke Takahashi: "An Extended Split-Radix FFT Algorithm"IEEE Signal Processing Letters. Vol.8,No.5. 145-147 (2001)

Daisuke Takahashi：“一种扩展的分割基数 FFT 算法”IEEE 信号处理快报。

高橋大介: "PCクラスタにおける並列三次元FFTのブロックアルゴリズム"2002年ハイパフォーマンスコンピューティングと計算科学シンポジウム HPCS2002論文集. 59-64 (2002)

Daisuke Takahashi：“PC 集群上并行 3D FFT 的块算法”2002 年高性能计算和计算科学研讨会 HPCS2002 论文集 59-64 (2002)。

Daisuke Takahashi: "A Parallel 3-DFFT Algorithm on Clusters of Vector SMPs"Proc.Fifth International Workshop on Applied Parallel Computing (PARA 2000). (in press). (2000)

Daisuke Takahashi：“矢量 SMP 集群上的并行 3-DFFT 算法”Proc.第五届应用并行计算国际研讨会 (PARA 2000)。

高橋大介: "共有メモリ型並列計算機における並列FFTのブロックアルゴリズム"情報処理学会論文誌. 43巻4号(印刷中). (2002)

Daisuke Takahashi：“共享内存并行计算机上的并行 FFT 的块算法”，日本信息处理学会汇刊，第 43 卷，第 4 期（出版中）。