mne-tools/mne-python — pull request #405 by mluessi (2013-01-22 22:02:53+00:00)
Title: WIP: Optimal FFT length selection for overlap-add filtering

There was a bug in the code for selecting the optimal FFT length based on the number of multiplications (see http://en.wikipedia.org/wiki/Overlap%E2%80%93add_method). This was also discussed in #393

With the current master, I get:

filter length: 4096
n_jobs=1, time: 84.4s
n_jobs=6, time: 43.2s
n_jobs=cuda, time: 17.2s
filter length: 8192
n_jobs=1, time: 84.6s
n_jobs=6, time: 43.5s
n_jobs=cuda, time: 17.4s
filter length: 16384
n_jobs=1, time: 84.3s
n_jobs=6, time: 44.4s
n_jobs=cuda, time: 17.3s
filter length: 32768
n_jobs=1, time: 139.2s
n_jobs=6, time: 63.3s
n_jobs=cuda, time: 21.3s

With the fixed FFT length selection:

filter length: 4096
n_jobs=1, time: 51.9s
n_jobs=6, time: 50.7s
n_jobs=cuda, time: 15.3s
filter length: 8192
n_jobs=1, time: 54.2s
n_jobs=6, time: 21.6s
n_jobs=cuda, time: 15.8s
filter length: 16384
n_jobs=1, time: 61.6s
n_jobs=6, time: 33.0s
n_jobs=cuda, time: 15.6s
filter length: 32768
n_jobs=1, time: 71.9s
n_jobs=6, time: 35.3s
n_jobs=cuda, time: 17.9s

This is a speedup of almost a factor of 2, which is quite good. However, for long signals the FFTs are too long due to a FFT suboptimal cost function. The FFT cost we use looks like this:

![cost](https://f.cloud.github.com/assets/647005/88113/46fe2a50-64de-11e2-9aa9-0e8d81643828.png)

However, the runtime is slightly different (created using https://gist.github.com/4598852):

![time](https://f.cloud.github.com/assets/647005/88116/5c4ec40a-64de-11e2-9fb4-a24b7fba82c0.png)

and when CUDA is used:

![time_cuda](https://f.cloud.github.com/assets/647005/88122/b7f02966-64de-11e2-87e9-b268971336cf.png)

The red dots are the FFT lengths selected using the cost function.

This makes me think that the high runtime for long signals in combination with long FFTs is related to memory transfer overhead. I will do some searching if there are any papers on this. Maybe we could also use a different constant for the memory transfer cost when CUDA is used.