dft_comparison.py ドキュメント

概要

本プログラム dft_comparison.py は、離散フーリエ変換(DFT)および高速フーリエ変換(FFT)の実行時間を比較・検証するベンチマークツールです。 一次元の合成信号に対するベンチマークモードと、RGB画像に対する二次元FFTベンチマークモードを備えています。CPUを用いた直接計算(Python標準、およびNumbaによるJITコンパイル)と、NumPyによるCPU FFT、CuPyによるGPU FFTのパフォーマンスを測定し、結果をCSVファイルおよびプロット画像として出力します。

理論的背景と動作原理

プログラムの一次元ベンチマークモードでは、長さ \(N\) の入力信号 \(x_j\) に対する離散フーリエ変換 \(X_k\) を以下の数式に基づき計算します。

\[X_k = \sum_{j=0}^{N-1} x_j \exp\left(-i \frac{2\pi}{N} j k\right)\]

この定義に従った直接計算(関数 dft_python および dft_numba)の計算量は \(\mathcal{O}(N^2)\) となります。 一方、numpy.fft や cupy.fft が利用する高速フーリエ変換アルゴリズムを用いることで、計算量は大幅に少ない \(\mathcal{O}(N \log N)\) へと削減されます。

二次元画像モードでは、二次元空間上の信号(画像の各ピクセル値)に対して同様の変換を二次元方向に拡張した二次元FFTを実行し、周波数スペクトルを算出します。可視化の際には、低周波から高周波までの極端な振幅差を抑えるため、スペクトルの振幅 \(X\) を以下の対数スケールに変換し、正規化して表示します。

\[S = \log(1 + |X|)\]

本プログラムは、これらの計算に要する時間を測定し、アルゴリズムの違い(直接計算とFFT)、およびデバイスの違い(CPUとGPU、さらにGPUにおけるデータ転送オーバーヘッドの有無)による処理速度の差を明らかにします。

必要要件

本プログラムは Python 言語で記述されており、以下の標準ライブラリおよび非標準パッケージを使用します。

  • 標準ライブラリ

    • argparse, csv, math, os, platform, statistics, sys, pathlib, time

  • 非標準ライブラリ(必須)

    • matplotlib: 結果のグラフ描画や画像スペクトルの可視化

    • numpy: 配列操作、CPU FFT計算、および一次元合成信号の生成

  • 非標準ライブラリ(オプション)

    • psutil: 物理コア数やシステムメモリ情報の取得

    • numba: 直接DFTのJITコンパイルによる高速化

    • cupy: GPUを用いたFFT計算

    • Pillow: 二次元FFTモードにおける画像ファイルの読み込み

入出力仕様

入力

コマンドライン引数により、動作モードやベンチマークのパラメータを指定します。

  • 一次元DFT/FFTモード(画像ファイルを指定しない場合のデフォルト動作)

    • プログラム内部で、複数の正弦波に正規分布ノイズを加算した一次元複素数配列を自動生成します。

    • オプション引数:

      • --nmin : 最小サンプル数 \(N\) (デフォルト: 64)

      • --nmax : 最大サンプル数 \(N\) (デフォルト: 1048576)

      • --factor : サンプル数の増加係数(デフォルト: 2)

      • --python-max : Pythonによる直接DFTを実行する最大サンプル数(デフォルト: 1024)

      • --numba-max : Numbaによる直接DFTを実行する最大サンプル数(デフォルト: 8192)

      • --repeat : FFTの測定反復回数(デフォルト: 5)

      • --dft-repeat : 直接DFTの測定反復回数(デフォルト: 1)

      • --seed : 乱数シード値(デフォルト: 12345)

  • 二次元画像FFTモード

    • 位置引数 image に画像ファイルのパスを指定することで有効になります。画像はRGBの浮動小数点配列として読み込まれます。

  • 共通オプション

    • --no-gpu : GPU FFTの測定を無効化します。

    • --output-prefix : 出力ファイル名のプレフィックスを指定します(デフォルトは一次元モードでは dft_benchmark、二次元モードでは入力画像のファイル名に _fft を付加したものになります)。

    • --show : 処理完了後にグラフや画像を画面上に表示します。

出力

プログラム実行後、指定したプレフィックスに基づき以下のファイルが出力されます。

  • 一次元モード

    • [prefix].csv : 各サンプル数 \(N\) における各手法の実行時間(秒)、および CPU FFT を基準とした最大相対誤差を出力します。

    • [prefix].png : サンプル数 \(N\) と処理時間(中央値)の関係を示した両対数グラフの画像ファイルを出力します。

  • 二次元モード

    • [prefix].csv : 画像の幅、高さ、チャネル数、および CPU・GPU の実行時間、相対誤差を出力します。

    • [prefix]_spectrum.png : 元のRGB画像と、R・G・B各チャネルの二次元FFTスペクトル(対数スケール)を並べて比較できる画像ファイルを出力します。

実行例

一次元信号のDFT/FFTベンチマークをデフォルト設定で実行する例です。

python dft_comparison.py

サンプル数 \(N\) の最大値を 1,048,576 に設定し、GPUを使用せずにベンチマークを実行する例です。

python dft_comparison.py --nmax 1048576 --no-gpu

画像ファイル sample.png を入力として読み込み、反復回数を10回に設定して二次元FFTベンチマークを実行する例です。

python dft_comparison.py sample.png --repeat 10