Halide's FFT 實作與效能比較

在許多 Halide 相關論文的投影片都可以看到與 FFTW 的速度比較
宣稱以 Halide 實作的 FFT 相較為 FFTW 的 1.5X 快

像是 An Introduction to Halide (CVPR 2015
以及 Halide: Decoupling Algorithms fromSchedules for High-PerformanceImage Processing

但是一時間無法找到原始碼
而最終是透過這篇 github 上的討論
由其得知現在是在 Halide/apps/fft 目錄中

找到後就簡單多了, 接著在 Ubuntu 上準備環境

$ sudo apt-get install libfftw3-3 libfftw3-dev

接著在 Halide/apps/fft 目錄下, 首先編修 ../support/Makefile.inc

$ vi ../support/Makefile.inc

修改 HALIDE_BIN_PATH, LDFLAGS 與 LLVM_CONFIG 後如下編譯與執行

$ WITH_FFTW=1 make bench_16x16 bench_32x32 bench_48x48 bench_64x64

./bin/bench_fft 16 16 ./bin/
                       Halide                  FFTW    
    DFT type  Time (us)    MFLOP/s  Time (us)    MFLOP/s      Ratio
         c2c      0.370   27659.83      0.575   17808.48       1.55
         r2c      0.269   18998.29      0.517    9910.42       1.92
         c2r      0.271   18918.61      0.518    9888.96       1.91
./bin/bench_fft 32 32 ./bin/
                       Halide                  FFTW    
    DFT type  Time (us)    MFLOP/s  Time (us)    MFLOP/s      Ratio
         c2c      3.121   16403.89      2.372   21586.78       0.76
         r2c      1.222   20947.74      2.415   10601.24       1.98
         c2r      1.372   18661.48      2.591    9878.77       1.89
./bin/bench_fft 48 48 ./bin/
                       Halide                  FFTW    
    DFT type  Time (us)    MFLOP/s  Time (us)    MFLOP/s      Ratio
         c2c     10.113   12724.26      8.103   15879.26      0.801
         r2c      3.986   16141.35      8.057    7985.28       2.02
         c2r      4.221   15242.53      7.610    8454.44        1.8
./bin/bench_fft 64 64 ./bin/
                       Halide                  FFTW    
    DFT type  Time (us)    MFLOP/s  Time (us)    MFLOP/s      Ratio
         c2c     21.800   11273.26     11.506   21358.44      0.528
         r2c      7.588   16193.94     11.638   10558.20       1.53
         c2r      7.530   16319.53     11.560   10629.47       1.54

在 m3-7y30 平台執行結果如上, 可以觀察到常使用的 r2c/c2r 的 2D FFT 效能相當優異, 也比 2015 年的數據出色