FFTW Introduction - FFTW@wiki

Introduction

　このマニュアルはFFTW(the Fastest Fourier Transform in the West)バージョン3.1.2のものです.FFTWは離散フーリエ変換を計算する包括的な高速Cルーチン集であり、以下のような特徴があります.

• 複素数データ,実数データ,偶対称,奇対称な実数データのDFT(*1),実数データの離散Hartley変換(DHT)を計算可能
• 入力データは任意のサイズがとれる.O(nlogn)アルゴリズムを,素数を含む,すべてのサイズで採用.
• 計算の時間の次元がデータ数nに対して,nlogn
• 任意の多次元データをサポート
• SSE/SSE2/3DNow!/Altivecの命令セットをサポート
• FFTW3.1.2は共有メモリシステムに対しては、並列(マルチスレッド)変換が可能。FFTW3.1.2は分散メモリ並列変換ができないが、MPIバージョンをじきに実装予定
• 当面の間は,FFTW2.1.3に実装されたMPIが利用可能

　ここでは、どんなアプリケーションに利用するかに関わらず、DFTの性質および使い方を熟知しているものとして話を進めます。もしそうでなければ、例えば、"The Fast Fourier Transform and Its Applications"(*2),を参照してください.

　我々のWebページにもFFT関係の情報のリンク集があります。
FFTWを効果的に使うためには、FFTWの内部構造の基本的なコンセプトについて知っている必要があります。すなわち、FFTWはDFT変換を計算する時に固定のアルゴリズムではなく、パフォーマンスを最大化するために、細かいハードウェア条件に合わせたアルゴリズムを用います。つまり、計算は大きくわけて2段階にわけることができます。
　第一にFFTWのプランナーはあなたのマシンで計算する時にもっとも速くなる方法を”学習”します。プランナーはこの情報を含んだ「プラン」と呼ばれるデータ構造体を生成します。
　続いて、プランによって示された入力データ配列を変換するために、プランが実行されます。
　このプランは何回でも再利用可能です。高性能なアプリケーションでは、同じサイズの変換が何度も計算されます。そのため、初期化の計算コストが比較的高くても、許容可能でしょう。
　一方で、特定のサイズの一回限りの変換を行いたい時には、プラン生成にかかる時間が重要になります。この場合は、FFTWはヒューリスティックにあるいは前回計算されたプランに基づいて、高速にプランを計算します。
　FFTWは任意の長さ、ランク、次元そして、一般的なメモリレイアウトの変換をサポートしています。しかし、簡単なケースではこの様に一般性を持たせることは不必要で、混乱を招くことでしょう。そういうわけで、我々は三つのレベルの一般性に対し、それぞれインターフェースを作りました。

• ベーシックインターフェース
  • 連続データの単一の変換を行う場合
• アドバンストインターフェース
  • 多次元配列、規則的な配列の変換を行う場合
• グルインターフェース
  • 最も一般的なデータ配置、次元、規則を持つ場合の変換を行う場合

我々は、大多数のユーザーがベーシックインターフェースで最も良い結果を得られることを期待しています。グルインターフェースは、諸問題を避けるために注意深くドキュメントを読む必要があります。
プランナーは、自動でプランの最適化を行ってくれる一方で、上級ユーザ向けの機能として、マニュアルでカスタマイズすることも可能です。例えば、コードの大きさが懸案事項である場合には、FFTWをリンクする際に、そのアプリケーションに必要な部分のみをリンクするツールも用意しています。反対に、標準のFFTWでは機能的に不十分で、拡張の必要があるかもしれません。例えば、標準のFFTWでは、配列サイズが、小さい素数(2,3,5,7)で素因数分解される場合に最も効率的に機能します。一方で、その他の場合には、一般的な利用を想定した遅いルーチンを使います。もし、その他の配列サイズに対し、効率的な計算をする必要があれば、FFTWのコードジェネレータが役に立ちます。コードジェネレータは高速なCプログラム(コードレット)を任意の配列サイズに対し生成します。例えば、513(=19*33)のサイズの変換がしたい場合、FFTWを因子19が効率的に計算できるようカスタマイズできます。

　FFTWに関する詳細の情報に関しては、"FFTW: An adaptive software arrchitecture for the FFT”(*3)や"The Fastest Fourier Transform in the West"(*4)を参照してください。
　コードジェネレータについては、"A fast Fourier transform compiler"(*5)を参照してください。
　これらの論文は、最新バージョンのFFTW,FAQ,性能テスト,その他のリンクと合わせてFFTWのホームページ(*6)から入手可能です。

FFTWの現在のバージョンは、過去30年間にわたるFFTの文献の様々なアイデアを反映しています。
FFTWには、何らかの形で、Cooley-Tukeyアルゴリズム(素因数のアルゴリズム)、Raderのアルゴリズム(素数サイズのアルゴリズム)、そしてsplit-radixアルゴリズム(Dan Bernsteinによる改良版)が盛り込まれてます。FFTWのコードジェネレータも我々は完全に理解できていないアルゴリズムを実装しています。適宜、引用文献のこと。

(*1)これらの対称な変換はそれぞれ、一般的に離散コサイン/サイン変換として知られている
(*2) "The Fast Fourier Transform and Its Applications",E. O. Brigham, Prentice-Hall, Englewood Cliffs, NJ, 1988
(*3) FFTW: An adaptive software architecture for the FFT,M. Frigo and S. G. Johnson, 23rd International Conference on Acoustics, Speech, and Signal Processing (Proc. ICASSP 1998 3, p. 1381)
(*4) The Fastest Fourier Transform in the West, M. Frigo and S. G. Johnson, technical report MIT-LCS-TR-728 (Sep. ’97)
(*5) A fast Fourier transform compiler, M. Frigo, in the Proceedings of the 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Atlanta, Georgia, May 1999
(*6) http://www.fftw.org/