【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: | Amazon EC2 m5.2xlarge インスタンス |
| OS: | Ubuntu 18.04 |
| Compiler: | GCC 7.4 |
| OpenMP Runtime: | libgomp (GCC default) |
| cores/threads: | 8 cores/8 threads |
| FFTW Version: | 3.3.8 |
| FFTW Mode: | FFTW_ESTIMATE (AVX-512 enabled) |
| 浮動小数点数の精度: | 倍精度 |
マルチスレッド性能に関するベンチマーク結果は以下のようになります。
------+-----------+-----------------+-----------------+-----------------+--- length|FFTW3[usec]| OOURA [usec]| SimpleFFT [usec]| OTFFT [usec]|err ------+-----------+-----------------+-----------------+-----------------+--- 2^( 1)| 0.02| 0.02( 86%)| 0.02(100%)| 0.01( 67%)| - 2^( 2)| 0.03| 0.03(115%)| 0.04(169%)| 0.02( 65%)| - 2^( 3)| 0.04| 0.05(129%)| 0.08(223%)| 0.02( 61%)|-28 2^( 4)| 0.07| 0.11(147%)| 0.15(208%)| 0.04( 58%)|-27 2^( 5)| 0.19| 0.32(173%)| 0.35(190%)| 0.09( 49%)|-27 2^( 6)| 0.37| 0.73(198%)| 0.69(187%)| 0.19( 51%)|-25 2^( 7)| 0.69| 1.58(229%)| 1.69(246%)| 0.40( 58%)|-25 2^( 8)| 1.39| 3.45(249%)| 3.28(236%)| 0.84( 60%)|-24 2^( 9)| 2.89| 7.59(263%)| 8.43(292%)| 2.12( 73%)|-23 2^(10)| 6.23| 16.47(264%)| 15.72(252%)| 4.44( 71%)|-23 2^(11)| 13.73| 36.40(265%)| 41.64(303%)| 10.52( 77%)|-22 2^(12)| 38.43| 79.52(207%)| 96.30(251%)| 29.02( 76%)|-21 2^(13)| 82.34| 262.63(319%)| 277.06(336%)| 46.32( 56%)|-20 2^(14)| 256.89| 471.02(183%)| 482.24(188%)| 73.21( 28%)|-20 2^(15)| 341.58| 806.55(236%)| 827.87(242%)| 132.28( 39%)|-19 2^(16)| 585.29| 1607.68(275%)| 1564.80(267%)| 274.30( 47%)|-19 2^(17)| 1074.42| 3200.84(298%)| 3008.99(280%)| 623.88( 58%)|-18 2^(18)| 1983.59| 6418.62(324%)| 5212.14(263%)| 1342.56( 68%)|-17 2^(19)| 8618.11| 9915.29(115%)| 10864.88(126%)| 2534.65( 29%)|-16 2^(20)| 21554.30| 24417.30(113%)| 23729.76(110%)| 6844.34( 32%)|-16 2^(21)| 49105.12| 50010.24(102%)| 59947.50(122%)| 18426.61( 38%)|-15 2^(22)| 112704.38| 121692.12(108%)| 157766.83(140%)| 44509.07( 39%)|-15 2^(23)| 229717.97| 222479.64( 97%)| 365531.20(159%)| 106846.93( 47%)|-14 2^(24)| 533694.13| 506646.31( 95%)| 830597.08(156%)| 205374.47( 38%)|-14 ------+-----------+-----------------+-----------------+-----------------+--- cost | 195645.65| 315271.99(161%)| 361335.55(185%)| 92337.03( 47%)| ------+-----------+-----------------+-----------------+-----------------+---
length の欄は FFT の系列長を表しています。 そして、言うまでもなく FFTW3 の欄が FFTW3 での実行時間です。 DFT と IDFT の実行時間の和を表示しています。 OOURA の欄は大浦さんの FFT ライブラリ fftsg.c での実行時間です。 SimpleFFT の欄はごく単純な4基底の Cooley-Tukey アルゴリズムの実行時間です。 そして OTFFT の欄が私 OK おじさんが提案する FFT ライブラリでの実行時間です。 実行時間の単位はマイクロ秒で、 初期化の時間(FFTW3 のプランの作成等)は含まれていません。 括弧の中の％付きの数字は FFTW3 の実行時間に対して何パーセントの実行時間になるかを表しています。 ただし、ベンチマーク結果が安定しなかったので、何度かベンチマークした結果、 OTFFT の成績が最も良くなる結果を選んだことを白状しておきます。 err の欄は FFTW3 と OTFFT の２乗誤差の対数です。 エラーチェックのために付けてあります。開発者用なので気にしないでください。 cost は全てのサイズで平均した速さの目安です。小さいほど高速です。
どうでしょう。2 のべき乗サイズで OTFFT が FFTW3 より速くなっています。 OTFFT が正式にサポートするサイズは \(2^{24}\) までです。 一応、\(2^{30}\) までは、メモリが許せば実行できるはずですけどね。
cost で比較するとだいたい OTFFT が FFTW3 の 47% ほどの実行時間で済みます。 AVX が Stockham のアルゴリズムに見事にはまり、加えて C++ の template によって、 ループの長さがコンパイル時に決まる、 固定長のループになっているところが効いているのかもしれません。
ただ、皆さんが自分のノートパソコンなどでベンチマークすると、 このような結果にはならず、大きなサイズの FFT で FFTW3 の方が速いと思います。 どうもノートパソコンは、マルチスレッドで CPU をフル回転させたりすると、 熱設計的にブレーキがかかるようです。OTFFT は、熱設計などお構いなく、 容赦なく CPU を酷使しようとするので強くブレーキがかかってしまうようです。
つまり、OTFFT は電力をバカ食いしてフル回転しようとしますが、 FFTW3 は省電力でそこそこの速度が出るということです。 熱設計に余裕がないと、結果として省電力の方が速くなります。
さて、ベンチマークの条件を、
FFTW_ESTIMATE にして誤摩化してないで、
とっとと FFTW_MEASURE で比較した結果を見せろ！
と言う方も居るかもしれませんので、一応結果を載せておきます。
こんな感じです。
------+-----------+-----------------+-----------------+-----------------+--- length|FFTW3[usec]| OOURA [usec]| SimpleFFT [usec]| OTFFT [usec]|err ------+-----------+-----------------+-----------------+-----------------+--- 2^( 1)| 0.02| 0.02( 83%)| 0.02( 97%)| 0.01( 65%)| - 2^( 2)| 0.03| 0.03(115%)| 0.04(169%)| 0.02( 65%)| - 2^( 3)| 0.04| 0.05(137%)| 0.08(236%)| 0.02( 64%)|-28 2^( 4)| 0.07| 0.11(151%)| 0.15(215%)| 0.04( 61%)|-27 2^( 5)| 0.15| 0.32(214%)| 0.35(235%)| 0.09( 59%)|-27 2^( 6)| 0.26| 0.73(277%)| 0.68(259%)| 0.19( 71%)|-26 2^( 7)| 0.50| 1.58(314%)| 1.69(335%)| 0.39( 78%)|-25 2^( 8)| 1.05| 3.45(328%)| 3.27(311%)| 0.84( 80%)|-24 2^( 9)| 2.41| 7.59(314%)| 8.35(346%)| 2.12( 88%)|-23 2^(10)| 5.49| 16.46(300%)| 15.74(287%)| 4.44( 81%)|-23 2^(11)| 12.51| 36.42(291%)| 41.95(335%)| 10.49( 84%)|-22 2^(12)| 30.93| 79.78(258%)| 96.42(312%)| 28.92( 93%)|-21 2^(13)| 66.13| 263.41(398%)| 275.81(417%)| 44.65( 68%)|-20 2^(14)| 257.42| 470.51(183%)| 494.81(192%)| 71.23( 28%)|-20 2^(15)| 375.95| 810.45(216%)| 852.00(227%)| 130.95( 35%)|-19 2^(16)| 549.83| 1611.12(293%)| 1551.18(282%)| 283.60( 52%)|-19 2^(17)| 1056.07| 3197.87(303%)| 3044.32(288%)| 628.98( 60%)|-18 2^(18)| 1945.74| 6314.46(325%)| 5297.66(272%)| 1333.40( 69%)|-17 2^(19)| 5822.68| 9853.01(169%)| 10823.18(186%)| 2523.95( 43%)|-16 2^(20)| 14376.30| 24093.52(168%)| 23898.31(166%)| 6965.61( 48%)|-16 2^(21)| 32449.85| 51240.93(158%)| 59484.48(183%)| 18572.95( 57%)|-15 2^(22)| 69312.50| 124160.37(179%)| 160015.50(231%)| 44645.45( 64%)|-15 2^(23)| 141994.60| 226413.23(159%)| 367998.46(259%)| 105419.03( 74%)|-14 2^(24)| 297037.80| 509076.86(171%)| 832253.21(280%)| 201982.33( 68%)|-14 ------+-----------+-----------------+-----------------+-----------------+--- cost | 150344.96| 316015.09(210%)| 363115.84(242%)| 92014.39( 61%)| ------+-----------+-----------------+-----------------+-----------------+---
念のため書いておきますが、 ダウンロードのページ から OTFFT をダウンロードしてご自分の環境で試したという方が居たとして、 その実行結果がここに示されている結果と一致しなくとも驚かないでください。 実行結果は環境によってまちまちです。 CPU とかが違えばまったく違った結果が出ますし、 CPU が同じでも macOS の Clang でコンパイルしたりすると、 また違った結果が出ます。それに FFTW3 は日々進歩しています。 新しいテクノロジーが登場すると積極的にそれを採用しています。 ですから、あなたがこのページを見て試すころには FFTW3 が進歩して OTFFT が陳腐化しているかもしれません。 そんなわけで、ここに書いてある通りにならなくともご了承ください。