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 算法。然后，我们在 PC 集群上实际实现了这些并行 FFT 算法，并评估了相对于传统顺序 FFT 算法的性能改进率。此外，在并行FFT算法中，需要尽可能减少每个处理器内部的FFT计算量，我们也研究了需要较少计算量的FFT算法。此外，我们还在国际会议等上展示了我们2003年的研究成果，并在学术期刊上发表了总结成果的论文。