【OTFFT -- FFTW より速い FFT ライブラリ】
セクション1, セクション2 で、 せっかく高速な Stockham FFT アルゴリズムを導いたのですから、 実際にそれを使ったらどうなるか試してみたいですよね。 そこで、Stockham のアルゴリズムを用いた FFT ライブラリを作ってみました。 その名も OTFFT です(OK おじさん Template FFT の略)。 実はこっそり Six-Step FFT アルゴリズム も使ってます。 その他、アルゴリズムではありませんが、 C++ の template によるメタプログラミング技法を駆使し、 さらに、AVX/AVX-512 イントリンシックを用いて実装してあります。 ですから、Intel アーキテクチャ CPU 専用ライブラリです (AVX/AVX-512 を使えない環境でも動くことは動きますけどね)。 また、FFT を任意の系列長で実行できる Bluestein's FFT を実装してあります。 さらにさらに、C99 や Fortran 2003 から使うためのインターフェイスもあります。
それにしても、FFTW より速いとは大きく出たなと思うでしょう。
でも、本当なんですよ。
まあ、特定の CPU 特定の系列長に限っての話ですけどね(^^;
それではベンチマーク結果を示しましょう。以下のようなベンチマークを行いました。
ソースコードは ダウンロードのページ で公開するとして(MIT ライセンスです)、 ここでは、マルチスレッド性能に関するベンチマークを示します。 ベンチマークの条件は以下の通りです。
| Machine: | Surface Laptop 5 13.5 inch |
| OS: | Ubuntu 22.04.3 on WSL2 |
| Compiler: | GCC 11.4.0 |
| OpenMP Runtime: | libgomp (GCC default) |
| cores/threads: | 10 cores/12 threads |
| OTFFT Version: | 11.6 |
| FFTW Version: | 3.3.10 |
| FFTW Mode: | FFTW_ESTIMATE (AVX2 enabled) |
| 浮動小数点数の精度: | 倍精度 |
マルチスレッド性能に関するベンチマーク結果は以下のようになります。
------+-----------+-----------------+-----------------+-----------------+--- length|FFTW3[usec]| OOURA [usec]| SimpleFFT [usec]| OTFFT [usec]|err ------+-----------+-----------------+-----------------+-----------------+--- 2^( 1)| 0.02| 0.01( 67%)| 0.02( 84%)| 0.01( 37%)| - 2^( 2)| 0.02| 0.02( 77%)| 0.03(111%)| 0.01( 49%)| - 2^( 3)| 0.03| 0.04(106%)| 0.05(160%)| 0.02( 62%)|-28 2^( 4)| 0.05| 0.09(173%)| 0.10(206%)| 0.03( 66%)|-27 2^( 5)| 0.08| 0.19(223%)| 0.22(259%)| 0.06( 76%)|-27 2^( 6)| 0.29| 0.44(154%)| 0.55(192%)| 0.12( 42%)|-26 2^( 7)| 0.60| 0.94(156%)| 1.19(197%)| 0.28( 47%)|-25 2^( 8)| 1.40| 2.12(151%)| 2.78(198%)| 0.64( 45%)|-24 2^( 9)| 2.98| 4.77(160%)| 6.02(202%)| 1.40( 47%)|-23 2^(10)| 6.15| 10.43(169%)| 13.66(222%)| 3.28( 53%)|-22 2^(11)| 13.60| 23.13(170%)| 28.69(211%)| 7.73( 57%)|-22 2^(12)| 44.03| 50.52(115%)| 73.95(168%)| 22.22( 50%)|-21 2^(13)| 120.90| 290.82(241%)| 174.82(145%)| 44.51( 37%)|-21 2^(14)| 261.38| 382.94(147%)| 470.05(180%)| 77.93( 30%)|-20 2^(15)| 568.78| 541.48( 95%)| 652.81(115%)| 140.48( 25%)|-19 2^(16)| 1314.54| 1037.85( 79%)| 1262.16( 96%)| 297.33( 23%)|-18 2^(17)| 1979.95| 2453.69(124%)| 2330.30(118%)| 659.42( 33%)|-18 2^(18)| 3793.36| 6828.67(180%)| 5172.61(136%)| 1161.03( 31%)|-17 2^(19)| 8358.94| 10296.29(123%)| 11737.12(140%)| 2783.19( 33%)|-16 2^(20)| 18387.82| 19227.21(105%)| 27581.71(150%)| 8819.07( 48%)|-16 2^(21)| 38320.13| 48852.39(127%)| 77364.76(202%)| 22485.61( 59%)|-15 2^(22)| 84923.35| 103790.65(122%)| 169834.00(200%)| 49140.68( 58%)|-14 2^(23)| 171470.17| 218252.27(127%)| 355714.71(207%)| 123948.11( 72%)|-14 2^(24)| 298024.14| 448253.79(150%)| 791393.71(266%)| 187790.20( 63%)|-13 ------+-----------+-----------------+-----------------+-----------------+--- cost | 192293.34| 254371.05(132%)| 319798.15(166%)| 86636.64( 45%)| ------+-----------+-----------------+-----------------+-----------------+---
length の欄は FFT の系列長を表しています。 そして、言うまでもなく FFTW3 の欄が FFTW3 での実行時間です。 DFT と IDFT の実行時間の和を表示しています。 OOURA の欄は大浦さんの FFT ライブラリ fftsg.c での実行時間です。 SimpleFFT の欄はごく単純な4基底の Cooley-Tukey アルゴリズムの実行時間です。 そして OTFFT の欄が私 OK おじさんが提案する FFT ライブラリでの実行時間です。 実行時間の単位はマイクロ秒で、 初期化の時間(FFTW3 のプランの作成等)は含まれていません。 括弧の中の％付きの数字は FFTW3 の実行時間に対して何パーセントの実行時間になるかを表しています。 ただし、ベンチマーク結果が安定しなかったので、何度かベンチマークした結果、 OTFFT の成績が最も良くなる結果を選んだことを白状しておきます。 err の欄は FFTW3 と OTFFT の FFT の結果の２乗誤差の対数です。 エラーチェックのために付けてあります。開発者用なので気にしないでください。 cost は全てのサイズで平均した速さの目安です。小さいほど高速です。
どうでしょう。2 のべき乗サイズで OTFFT が FFTW3 より速くなっています。 OTFFT が正式にサポートするサイズは \(2^{24}\) までです。 一応、\(2^{30}\) までは、メモリが許せば実行できるはずですけどね。
cost で比較するとだいたい OTFFT が FFTW3 の 45% ほどの実行時間で済みます。 AVX が Stockham のアルゴリズムに見事にはまり、加えて C++ の template によって、 ループの長さがコンパイル時に決まる、 固定長のループになっているところが効いているのかもしれません。
実は最近、新しいパソコンを買ったので、 久々に OTFFT のベンチマークをしてみたのですが、 インテルの１２世代 CPU は OTFFT との相性が抜群でした。 インテル１２世代 CPU には高性能コアと高効率コアあって、 負荷のかかるマルチスレッド処理などは高効率コアにまかせて電力消費を押さえます。 結果として CPU の発熱が押さえられ、熱設計的なブレーキを回避できます。
OTFFT は、 熱設計のことなどお構いなしに電力をバカ食いしてフル回転しようとしますので、 CPU の省電力機能がお粗末だと、 盛大に発熱して熱設計的なブレーキがかかっていました。 Skylake に高い負荷をかけるとフリーズするバグがありましたが、 たぶん、その影響で、長いこと大きなサイズの FFT の成績は 省電力性能が優秀な Haswell 世代にすらかなわないという状況が続いていました。 しかし、インテル１２世代 CPU は Skylake からの問題を克服したようです。 まあ、私は Icelake 世代のパソコンを持っていないので、 ひょっとすると Icelake で既に克服していたのかもしれませんけれど。
ただ、数値計算という分野が、 長時間にわたって CPU に高い負荷をかけ続けるのが当たり前なのだとすると、 このページで紹介したベンチマークは真実の性能を語っていません。 実際に、パソコンのファンがうるさく回るような状況でベンチマークすると、 OTFFT は FFTW3 より性能が悪いです。 なので、使い方次第では FFTW3 を使った方が良いかもしれません。
さて、ベンチマークの条件を、
FFTW_ESTIMATE にして誤摩化してないで、
とっとと FFTW_MEASURE で比較した結果を見せろ！
と言う方も居るかもしれませんので、一応結果を載せておきます。
こんな感じです。
------+-----------+-----------------+-----------------+-----------------+--- length|FFTW3[usec]| OOURA [usec]| SimpleFFT [usec]| OTFFT [usec]|err ------+-----------+-----------------+-----------------+-----------------+--- 2^( 1)| 0.02| 0.01( 68%)| 0.02( 85%)| 0.01( 39%)| - 2^( 2)| 0.02| 0.02( 77%)| 0.03(109%)| 0.01( 49%)| - 2^( 3)| 0.03| 0.04(108%)| 0.05(159%)| 0.02( 56%)|-28 2^( 4)| 0.05| 0.09(178%)| 0.10(205%)| 0.03( 66%)|-27 2^( 5)| 0.08| 0.18(226%)| 0.21(262%)| 0.06( 76%)|-27 2^( 6)| 0.14| 0.43(303%)| 0.55(384%)| 0.12( 86%)|-26 2^( 7)| 0.30| 0.94(311%)| 1.17(387%)| 0.27( 91%)|-25 2^( 8)| 0.64| 2.11(328%)| 2.77(431%)| 0.64( 99%)|-24 2^( 9)| 1.55| 4.73(306%)| 5.96(386%)| 1.41( 91%)|-23 2^(10)| 4.07| 10.35(255%)| 13.52(332%)| 3.31( 81%)|-22 2^(11)| 8.41| 22.90(272%)| 28.45(338%)| 7.47( 89%)|-22 2^(12)| 22.22| 50.46(227%)| 72.21(325%)| 20.53( 92%)|-21 2^(13)| 49.05| 291.59(594%)| 173.81(354%)| 41.77( 85%)|-21 2^(14)| 104.65| 379.71(363%)| 395.46(378%)| 76.19( 73%)|-20 2^(15)| 275.93| 525.62(190%)| 565.19(205%)| 136.22( 49%)|-19 2^(16)| 1199.67| 989.61( 82%)| 1074.55( 90%)| 279.28( 23%)|-18 2^(17)| 1776.86| 2716.19(153%)| 2405.51(135%)| 677.31( 38%)|-18 2^(18)| 3050.84| 7313.65(240%)| 5134.60(168%)| 1323.54( 43%)|-17 2^(19)| 6746.79| 10752.24(159%)| 12999.56(193%)| 3093.32( 46%)|-16 2^(20)| 13798.07| 20286.32(147%)| 27882.82(202%)| 11011.15( 80%)|-16 2^(21)| 25776.60| 51000.31(198%)| 76165.69(295%)| 22345.99( 87%)|-15 2^(22)| 54350.75| 104982.50(193%)| 177285.93(326%)| 50237.75( 92%)|-14 2^(23)| 117092.40| 225383.00(192%)| 388589.37(332%)| 100327.30( 86%)|-14 2^(24)| 247933.53| 464576.71(187%)| 927083.27(374%)| 206509.40( 83%)|-13 ------+-----------+-----------------+-----------------+-----------------+--- cost | 134169.67| 259137.43(193%)| 322765.86(241%)| 86923.47( 65%)| ------+-----------+-----------------+-----------------+-----------------+---
念のため書いておきますが、 ダウンロードのページ から OTFFT をダウンロードしてご自分の環境で試したという方が居たとして、 その実行結果がここに示されている結果と一致しなくとも驚かないでください。 実行結果は環境によってまちまちです。 CPU とかが違えばまったく違った結果が出ますし、 CPU が同じでも macOS の Clang でコンパイルしたりすると、 また違った結果が出ます。それに FFTW3 は日々進歩しています。 新しいテクノロジーが登場すると積極的にそれを採用しています。 ですから、あなたがこのページを見て試すころには FFTW3 が進歩して OTFFT が陳腐化しているかもしれません。 そんなわけで、ここに書いてある通りにならなくともご了承ください。