OTFFT -- FFTW より速い FFT ライブラリ

OTFFT のシングルスレッドベンチマーク

 OTFFT はデフォルトでは OpenMP によるマルチスレッドで動作します。しかし、 中にはマルチスレッドの実装は、自前の仕組みを使いたい人もいるかもしれません。 そこで、シングルスレッドのバージョンも用意しました。

 そんなわけで、シングルスレッドのベンチマークもしてみました。 条件は以下のようになります。

Machine:MacBook Pro 15 inch Late 2016 (Core i7 2.6GHz)
OS:macOS Mojave
Compiler:Clang 8.0
cores/threads:4 cores/1 thread
FFTW Version:3.3.8
FFTW Mode:FFTW_MEASURE (AVX2 enabled)
浮動小数点数の精度:倍精度

ベンチマーク結果は以下のようになります。

------+-----------+-----------------+-----------------+-----------------+---
length|FFTW3[usec]|   OOURA   [usec]| SimpleFFT [usec]|   OTFFT   [usec]|err
------+-----------+-----------------+-----------------+-----------------+---
2^( 1)|       0.02|       0.01( 61%)|       0.01( 53%)|       0.01( 42%)| -
2^( 2)|       0.03|       0.02( 77%)|       0.03(133%)|       0.01( 45%)| -
2^( 3)|       0.03|       0.04(104%)|       0.06(171%)|       0.02( 59%)|-28
2^( 4)|       0.06|       0.07(116%)|       0.14(238%)|       0.04( 68%)|-27
2^( 5)|       0.11|       0.23(207%)|       0.25(230%)|       0.07( 65%)|-26
2^( 6)|       0.22|       0.53(245%)|       0.64(299%)|       0.15( 68%)|-26
2^( 7)|       0.45|       1.27(281%)|       1.30(288%)|       0.38( 84%)|-25
2^( 8)|       0.96|       2.79(292%)|       3.42(358%)|       0.76( 79%)|-24
2^( 9)|       2.28|       6.46(283%)|       6.45(283%)|       1.72( 75%)|-24
2^(10)|       4.90|      14.19(290%)|      15.55(318%)|       4.04( 83%)|-23
2^(11)|      12.79|      32.50(254%)|      34.17(267%)|      10.44( 82%)|-22
2^(12)|      34.72|      70.26(202%)|      95.78(276%)|      27.24( 78%)|-21
2^(13)|      70.81|     157.19(222%)|     217.72(307%)|      60.53( 85%)|-21
2^(14)|     172.76|     338.71(196%)|     507.11(294%)|     142.90( 83%)|-20
2^(15)|     404.53|     768.26(190%)|    1151.20(285%)|     302.49( 75%)|-19
2^(16)|     829.63|    1637.90(197%)|    2647.29(319%)|     798.94( 96%)|-19
2^(17)|    1986.72|    3733.97(188%)|    5684.38(286%)|    1776.99( 89%)|-18
2^(18)|    7765.57|    8208.45(106%)|   17001.13(219%)|    6231.60( 80%)|-17
2^(19)|   19391.43|   22212.53(115%)|   58043.84(299%)|   15343.95( 79%)|-16
2^(20)|   41074.85|   52242.91(127%)|  168200.99(409%)|   34498.74( 84%)|-16
2^(21)|   81829.61|  109663.70(134%)|  383436.57(469%)|   73210.23( 89%)|-15
2^(22)|  179010.29|  228701.05(128%)|  845191.32(472%)|  158326.91( 88%)|-15
2^(23)|  373002.22|  469632.27(126%)| 1813317.81(486%)|  334035.20( 90%)|-14
2^(24)|  821348.29| 1042829.71(127%)| 3892317.31(474%)|  664336.87( 81%)|-14
------+-----------+-----------------+-----------------+-----------------+---
 cost |  277291.85|  400070.07(144%)| 1015388.16(366%)|  227117.65( 82%)|
------+-----------+-----------------+-----------------+-----------------+---

 length の欄は FFT の系列長を表しています。 そして、言うまでもなく FFTW3 の欄が FFTW3 での実行時間です。 DFT と IDFT の実行時間の和を表示しています。 OOURA の欄は大浦さんの FFT ライブラリ fftsg.c での実行時間です。 SimpleFFT の欄はごく単純な4基底の Cooley-Tukey アルゴリズムの実行時間です。 そして OTFFT の欄が私 OK おじさんが提案する FFT ライブラリでの実行時間です。 実行時間の単位はマイクロ秒で、 初期化の時間(FFTW3 のプランの作成等)は含まれていません。 括弧の中の%付きの数字は FFTW3 の実行時間に対して何パーセントの実行時間になるかを表しています。 err の欄は FFTW3 と OTFFT の2乗誤差の対数です。 エラーチェックのために付けてあります。開発者用なので気にしないでください。 cost は全てのサイズで平均した速さの目安です。小さいほど高速です。

 このベンチマークはノートパソコンで行いました。 その方が Amazon EC2 m5.2xlarge インスタンスでやるより OTFFT の成績が良いからです。 どうやら、シングルスレッドで FFT を行う場合は、 1コアをフル回転させてもノートパソコンでも熱設計的に余裕があるらしく、 OTFFT が速くなるようです。


OTFFT -- FFTW より速い FFT ライブラリ