PCクラスタにおける高速フーリエ変換の並列アルゴリズムに関する研究

PC集群上快速傅里叶变换并行算法研究

• 批准号: 14780185
• 负责人: 高橋 大介
• 金额: $ 1.86万
• 依托单位: University of Tsukuba
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14780185/
• 关键词: 高速フーリエ変換; PCクラスタ

本研究の目的は,PCクラスタにおける高速フーリエ変換(fast Fourier transform,以下FFT)の並列アルゴリズムの実現および評価が挙げられる。近年,PCクラスタの普及に伴い,並列FFTアルゴリズムが様々な研究者によって提案されており,ライブラリとなっているものも多い。ところが、これらの並列FFTアルゴリズムはデータ数がN=2^pのように,2のべき乗で表される場合についてのものが多い。そこで本研究では,PCクラスタにおいてデータ数がN=2^p3^q5^rの場合について多次元の並列FFTアルゴリズムの実現および評価を行った。PCクラスタでは,一つのノードがSMP構成になっている場合があり,この場合にはPCクラスタが共有メモリ型並列計算機と分散メモリ型並列計算機の両方のアーキテクチャの特性を兼ね備えたものになるが,それぞれのアーキテクチャにおいて最適な並列FFTアルゴリズムは異なるために,本研究では異なるアーキテクチャについてそれぞれ並列FFTアルゴリズムを実現し,評価を行った。そして,これらの並列FFTアルゴリズムを実際にPCクラスタ上に実現し,今までの逐次FFTアルゴリズムに対する性能向上率を評価した。さらに,並列FFTアルゴリズムでは,各プロセッサ内におけるFFTの計算量をできるだけ削減する必要があるが,より演算量の少ないFFTアルゴリズムについても研究を行った。また,平成15年度に行った研究成果を,国際会議等で発表すると共に,それらの内容をまとめて学術雑誌等で論文を発表した。

这项研究的目的是实现和评估PC簇中快速傅立叶变换（FFT）的并行算法。近年来，随着PC簇的扩散，各种研究人员提出了平行的FFT算法，许多研究人员已成为图书馆。但是，这些平行的FFT算法大多在数据数表示为2的幂时，例如n = 2^p。因此，在这项研究中，我们在PC群集中实现并评估了数据数为n = 2^p3^q5^r的多维并行FFT算法。在PC群集中，可以将一个节点配置为SMP，在这种情况下，PC群集结合了共享存储器并行计算机和分布式内存并行计算机架构的特征，但是由于每个体系结构的最佳fft算法是不同的，因此在本研究中，我们实现并评估了每个架构的并行FFT Algorithm。然后实际上在PC群集上实现了这些平行的FFT算法，并评估了先前的顺序FFT算法的性能提高率。此外，平行的FFT算法要求尽可能减少每个处理器中的FFT的计算量，但是对FFT算法进行了较少计算量的研究。此外，在2003年进行的研究结果在国际会议上提出，并编译了这些结果，并在学术期刊上介绍了论文，等等。

项目成果

Daisuke Takahashi: "A Radix-16 FFT Algotithm Suitable for Multiply-Add Instruction Based on Goedecker Method"Proceeding of 2003 IEEE International Conference on Aceustics, Speech, and Signal Processing (ICASSP 2003). (to appear). (2003)

Daisuke Takahashi：“基于 Goedecker 方法的适用于乘加指令的 Radix-16 FFT 算法”2003 年 IEEE 国际声学、语音和信号处理会议记录 (ICASSP 2003)。

Daisuke Takahashi: "A parallel 1-D FFT algorithm for the Hitachi SR8000"Parallel Computing. Vol.29,No.6. 679-690 (2003)

Daisuke Takahashi：“适用于 Hitachi SR8000 的并行一维 FFT 算法”并行计算。

Daisuke Takahashi: "A Radix-16 FFT Algorithm Suitable for Multiply-Add Instruction Based on Goedecker Method"Proceedings of 2003 IEEE International Conference on Multimedia and Expo(ICME 2003). Vol.2. 845-848 (2003)

Daisuke Takahashi：“基于 Goedecker 方法的适用于乘加指令的 Radix-16 FFT 算法”2003 年 IEEE 国际多媒体会议和博览会（ICME 2003）论文集。

Daisuke Takahashi: "A parallel 1-D FFT algorithm for the Hitachi SR8000"Parallel Computing. (to appear). (2003)

Daisuke Takahashi：“适用于 Hitachi SR8000 的并行一维 FFT 算法”并行计算。

高橋大介, 朴泰祐, 佐藤三久: "PCクラスタにおける並列一次元FFTのブロックアルゴリズム"情報処理学会論文誌:ハイパフォーマンスコンピューティングシステム. 43巻・SIG6(HPS5). 134-142 (2002)

Daisuke Takahashi、Taisuke Park、Miku Sato：“PC 集群中并行一维 FFT 的块算法”日本信息处理学会杂志：高性能计算系统第 43 卷/SIG6(HPS5)。