my speedy FFT, 3x faster than CUFFT Options

[vvolkov]

my speedy FFT

Hi, I'd like to share an implementation of the FFT that achieves 160 Gflop/s on the GeForce 8800 GTX, which is 3x faster than 50 Gflop/s offered by the CUFFT. It is designed for n = 512, which is hardcoded. The implementation also includes cases n = 8 and n = 64 working in a special data layout.

Compile using CUDA 2.0 beta or later.

Vasily

Update (Sep 8, 2008): I attached a newer version that includes n = 16, n = 256 and n = 1024 cases. Here is its performance in Gflop/s when using driver 177.11 (up to ~40% slower with the newer 177.84 version):

CODE

...n     batch   8600GTS  8800GTX  9800GTX  GTX280
...8   2097152    22       67       52       102
..16   1048576    28       89       68       125
..64    262144    35      126      104       231
.256     65536    39      143      137       221
.512     32768    41      162      154       298
1024     16384    41      159      166       260

Update (Jan 12, 2009): I attached a quickly patched version that supports forward and inverse FFTs for n = 8, 16, 64, 256, 512, 1024, 2048, 4096 and 8192. Here are results for CUDA 2.1 beta, driver 180.60:

CODE

Device: GeForce GTX 280, 1296 MHz clock, 1024 MB memory.
Compiled with CUDA 2010.
             --------CUFFT-------  ---This prototype---  ---two way---
...N   Batch Gflop/s  GB/s  error  Gflop/s  GB/s  error  Gflop/s error
...8 1048576    8.8    9.4   1.8     83.0   88.6   1.6     82.8   2.1
..16  524288   19.7   15.8   2.1     91.9   73.5   1.5     92.5   1.8
..64  131072   55.8   29.8   2.3    185.6   99.0   2.4    185.4   3.0
.256   32768   97.1   38.8   2.2    160.1   64.1   2.0    160.1   3.0
.512   16384   65.2   23.2   2.9    240.9   85.6   2.5    240.9   3.7
1024    8192   86.7   27.8   2.7    211.4   67.7   2.5    211.9   3.9
2048    4096   50.6   14.7   3.7    160.0   46.6   3.0    159.6   4.5
4096    2048   48.9   13.0   4.0    171.0   45.6   3.3    170.2   4.9
8192    1024   47.4   11.7   4.4    185.9   45.8   3.4    184.1   5.2

Errors are supposed to be of order of 1 (ULPs).

Some of the layouts used are not straightforward. If you need filtering based on element-wise multiplication by a vector in the frequency space, I'd suggest using a similar layout for the vector.

This post has been edited by vvolkov: Jan 12 2009, 03:54 PM

Attached File(s)

 FFT_061408.zip ( 7.43K ) Number of downloads: 703
 FFT_090808.zip ( 11.04K ) Number of downloads: 541
 IFFT_011209.zip ( 19.55K ) Number of downloads: 644