【OTFFT のダウンロード】

　Stockham のアルゴリズムと AVX/FMA/AVX-512 を使った高速な FFT ライブラリ OTFFT は以下のリンクからダウンロードできます。OTFFT は MIT ライセンスです。

　ホームページのディスク使用量節約のため、 ダウンロードには Dropbox を使っています。 ログインやアカウント作成は、 「×」ボタンでキャンセルしてダウンロードしてください。

• OTFFT ソースコード (Linux/Cygwin 用) - otfft-11.6.tar.gz (New! 2023/12/21)
• OTFFT ソースコードシングルスレッド版 (Mac/Linux/Cygwin 用) - otfft-11.5o.tar.gz (2019/9/24)
• OTFFT ソースコード (Visual Studio 2019 nmake 用) - otfft-11.5v.zip (2019/9/9)
• OTFFT ソリューション(Visual Studio 2019 用) - otfft-11.5s.zip (2019/9/9)
• OktinyMP 版 OTFFT - こちらのページへどうぞ

　コンパイルするには非常に長い時間がかかります。辛抱強くお待ちください。 使い方は セクション11 を参照してください。

　バージョン 11.6 をリリースです。 え？OTFFTってまだ生きてたの？って感じですが、 久々に新しいパソコンを買ったのでベンチマークしてみたんです。 インテルが１０年に１度の改革と言うだけあって、１２世代 CPU は速いです。 そこで、その CPU に合わせて各種パラメータを微調整しました。 なので、古い CPU だとかえって遅くなってるかもしれません。 あと、ベンチマークまわりを大改革しました。

　実は、今まで新しい CPU が出ても、 大きなサイズの FFT では Haswell 世代にかなわない状況が続いていました。 Skylake で高負荷をかけるとフリーズするバグの影響だと思うのですが、 古い CPU より遅いってひどいですよね。 たぶん、Skylake で Haswell で使われていた省電力機能を外したことが原因だと思う。 電力消費をうまくコントロールできずに発熱して、 熱設計的にブレーキがかかるんじゃないかな。 しかし、１２世代 CPU は高性能コアと高効率コアを分けて、 負荷のかかりそうなタスクを高効率コアにまかせることで発熱が抑えられているんだと思う。この設計思想が OTFFT にはピッタリはまったようです。

　バージョン 11.5o は、 マルチスレッド機能を取り除いたシングルスレッド版です。 今までもシングルスレッドモードはありましたが、 ビルド時にマクロを定義するのが分かりにくいかもしれないので作りました。 Amazon EC2 ではベンチマークはふるいませんが、 ノートパソコンだと良い結果が出ます。

　バージョン 11.5 では、ffttune コマンドの微修正をしました。

　バージョン 11.4s は、Visual Studio 2019 のソリューションです。 今時コマンドラインで nmake なんて正気の沙汰ではない。 IDE でなければやってられるか！という人もいるかもしれないので作ってみました。 でも、パフォーマンスは nmake 版の方がいいんですよ。

　バージョン 11.4 では、ファイルの参照関係を整理しました。 本質的な変更点はありません。

　バージョン 11.3 では、初期化ルーチンの改良を行いました。

　バージョン 11.2x は、 OpenMP の代わりに C++11 のスレッド機能で実装されたバージョンです。 こちら からダウンロードできます。 OktinyMP という OK おじさん作の並列処理環境で実装されています。 OpenMP 版よりちょっとだけ性能が良いです。 また、macOS や Cygwin の GCC でコンパイルしても OpenMP 版のように性能低下したりしません。 macOS や Cygwin の GCC でコンパイルしても性能低下しないポータブルでメジャーな OpenMP 実装はありませんので、 いろんな環境でハイパフォーマンスな並列処理をしたいなら OktinyMP です！

　バージョン 11.2 では、バージョン 11.1 で取り切れなかったバグを修正。 OTFFT 本体ではなく、比較検証する側に原因がありました。 そりゃないっすよ～。比較するプログラムをおとなしめのものに変更しました。 なんか、最近 GCC のバージョンに関するバグばかり修正してる気がする。 GCC にはより良いコンパイラになって欲しいけど、 互換性も維持して欲しいなぁ。

　バージョン 11.1 では、GCC 8 以降で計算結果がおかしくなるバグを修正しました。 ただ、Fedora + GCC 8 以降で、 ダイナミックリンクライブラリがうまく機能しないバグは修正できませんでした。

　OTFFT はコードの自動生成等の手順があり、 利用するのに多少ハードルが高いです。 そこで、自動生成をスキップして最も無難なアルゴリズムに固定し、対応マシンを AVX が使えるマシンに限定したコンパイル済みの共有ライブラリを作ってみました。 libotfft-11.0.tar.gz です。お手軽に OTFFT を使いたい人はお試しください。

　バージョン 11.0 では、AVX-512 への対応を行いました。 でも、効果のほどは微妙なんですよね。 中程度のサイズの FFT では AVX-512 を使うと反って遅くなります。うーん。 ところで、せっかく長いベクトル長に対応するのだから、 この際、OTFFT のアルゴリズム上の限界のベクトルサイズまで対応しました。 1024 bit ベクトルや 2048 bit ベクトルで計算します。 ハードウェアのサポートがないのにソフトウェア的に長くしても無意味では？ とおもわれるかもしれませんが、 ベクトル長を長くするとループアンロール最適化が効いて速くなることがあるんです。 遅くなることもありますけどね。 とにかく、アルゴリズム的に大改革を行ったのでメジャーバージョン上げました。 乾いた雑巾をしぼる程度ではありますけれど、それなりに速くなってます。

　バージョン 10.2 では、gcc8 でコンパイルすると、 計算結果がおかしくなるバグを修正しました。

　バージョン 10.1 では、Six-Step FFT のコードを整理しました。 その他、コードの実行順序を色々いじって最適化したつもり…。効果あるかな？ って感じ(^^; 余談ながら、今回、gcc7 のバグに苦しめられました。 clang や gcc6 では問題ないコードが gcc7 でコンパイルすると、 おかしな計算結果になります。問題の部分は突き止めたのですが、 バグが再現する最小のコードを切り出そうとしても再現しないという。 多分、gcc7 は最適化周りにバグがあります。他の人のプログラムでも、 知らないうちにおかしな結果になってるものがあるんじゃないかな。 コンパイラのバグって恐ろしいですね。

　バージョン 10.0 では、1024 以上の系列長でのメモリ消費量を削減しました。 メモリ消費量が従来の 5/8 程度になりました。ただし、 混合基数 FFT は従来のままです。 また、OpenMP を用いないバージョンで、 実数 FFT や DCT で stop メンバ関数が実装されていないかったバグを修正しました。

　バージョン 9.5 では、実質的な変更点はありません。 ベンチマーク用の simple_fft.h のコードを整理しました。 その代わり、OktinyMP という並列処理ライブラリを作って、 OpenMP の代わりにそれを用いて OTFFT を書き換えたバージョンをリリースしました。

　バージョン 9.4 では、 fwdn, inv0 メンバ関数がリンクできなかったバグを修正しました。 やっぱテストをサボるとダメですね。orz

　バージョン 9.3 では、OTFFT のユーザーからのフィードバックで complex_t のインターフェイスのバグを修正しました。えっ？ OTFFT にユーザーっていたの？ ええ、いるんですよ。えっへん！

　バージョン 9.2 では、Mac のデフォルトの Makefile のコンパイラを GCC から Clang に変更し、ベンチマークも Clang で行いました。なぜかって？ Clang でコンパイルすると FFTW のパフォーマンスが劇的に低下して、 相対的に OTFFT の成績が向上するからです！(おいー) と、思ったら、FFTW が バージョン 3.3.5 で遅くなったみたいですね。う〜ん。 変更の本当の理由は、 Mac で AVX と OpenMP を使おうとすると MacPorts の Clang が最も簡単だからです。 私以外の人がベンチマークするとき、簡単な方が良いでしょ？

　バージョン 9.1 では、Visual Studio での重大なバグを修正しました。 noexcept を使っているコードがうまくコンパイル出来ませんでした。 私が確認しているベンチマークプログラムでは、 うまい具合にバグをよけていて、問題なくコンパイル出来ていたので発見が遅れました。

　バージョン 9.0 では、 場当たり的に対応してきた古いコンパイラのサポートを廃止し、 ごちゃごちゃとした汚いコードを削除しました。 そもそも古いコンパイラでコンパイルして確認してはおらず、 実際に動くかどうか分からない状態でした。 そんなわけで、あまり意味がないと判断しました。

　バージョン 8.4 では、Visual Studio で、 AVX2 がうまく使えていなかったのを修正しました。

　バージョン 8.3 では、Mac の Xcode 付属の clang++ で、 コンパイル時に warning が出ないように修正しました。

　バージョン 8.2 では、実行環境に合わせてチューンニングするコマンドを調整して、 より適切なヘッダーファイルを生成するようにしました。以前より、ffttune に、 ちょっと時間がかかるようになりますが、大きなサイズで効果があります。

　バージョン 8.1 では、OTFFT が混合基数 FFT になりました。また、 扱うメモリがアラインされていなくても動作する、 アンアラインモードを用意しました。

　バージョン 7.0 では、OS X/Linux/Cygwin 用で、 OTFFT を C99 と Fortran 2003 から呼び出すインターフェイスを用意しました。 Visual Studio nmake 版ではサポートされません。

　バージョン 6.5 では、 シングルスレッドモードのバグを修正しました。 初期化がシングルスレッドで実行されていませんでした(^^; 初期化の時間を含まないベンチマークには影響ありません。

　バージョン 6.4 では、シングルスレッドモードをサポートしました。 また、Amazon EC2 で 32 並列のベンチマークを行い、 メニーコアに対するパラメータ調整を行いました。

　バージョン 6.3 では、C++11 と C++98 の切り替えを __cplusplus マクロで自動判定するようにしました。

　バージョン 6.2 では、四捨五入まわりのコードを整理しました。 6.1 と実質的な違いはありません。

　バージョン 6.1 では Makefile のバグを修正しています。その他、 sleep 系関数を C++11 の sleep_for で実装しました。これで、 C++11 以降の標準以外の関数は SSE2/AVX/AVX2 のイントリンシックのみとなりました。 個人的には、かな〜り気持ちいいですね。

　バージョン 6.0 から OTFFT 自身のコンパイルには C++11 を使うようになりました。 時間計測に chrono を用いています。リンクするプログラムは C++03 でも OK です。