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クラスタにおける高速フーリエ変換(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年度に行った研究成果を,国際会議等で発表すると共に,それらの内容をまとめて学術雑誌等で論文を発表した。