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

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

• 批准号: 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アルゴリズムに比べて高い性能を示すことが分かった.またこれらの研究成果をもとに,雑誌論文や国際会議において研究成果を発表した。

The purpose of this study is to evaluate the performance of parallel computer systems with fast Fourier transform (FFT). In recent years, parallel computers have become popular, and parallel FFT has become popular among researchers. For example, the number of parallel FFT is N= 2p, and the number of parallel FFT is 2. In this study, the number of parallel computers is N=2^p3^q5^r. Parallel computers are distributed parallel computers and distributed parallel computers. In this study, parallel FFT is implemented and evaluated. The performance improvement rate of these parallel FFT systems is evaluated when they are implemented on parallel computers of both distributed and distributed types. In this study, we have realized that parallel FFT has a high performance in parallel computers, such as distributed parallel computers, distributed parallel computers, and distributed parallel computers. The results of this research are presented at international conferences.

项目成果

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 期（出版中）。