ENH: Speed up frequency functions

[larsoner]

It sounds like a lot of folks are trying to get our (time)frequency functions to be faster. Supercedes the closed MKLFFT issue #1889, and slightly to the resampling issue of #2035.

Potential ways to enhance:

1. Use MKLFFT in our functions. WIP in WIP: initialize mklfft #2623. It looks like performance gains are not clear?

2. Use rfft instead of fft where we can -- I assumed fftpack.fft would triage based on input type whether to do real or complex DFT, but it sounds like it doesn't (!):

   signal.resample could be twice as fast using rfft scipy/scipy#5592

   This one is actually pretty low-hanging fruit. Any volunteer? (MRG: Faster raw resampling #2978)

3. Use CUDA. I have experimented with this and not gotten very far. The trick is just doing FFT and IFFT on GPU is not enough because the transfer overhead (CPU<->GPU) is too large. So we need to do multiple operations there. This is why the overlap-add filtering, which can do FFT, multiply, and IFFT on the GPU, is an order of magnitude faster than multicore CPU. There should be a way to do something similar for e.g. CWT functions (batching the wavelets to process a single segment using multiple filters maybe?), but I haven't figured it out.

Feel free to post or edit this issue with other ideas.

[larsoner]

Also relevant for places that we do convolve:

http://scipy-cookbook.readthedocs.org/items/ApplyFIRFilter.html

[jasmainak]

I think a good start would be a small script to see what we want to improve / make faster. Taking it from there, we can evaluate the three options better ...

[jasmainak]

By the way, we should start labeling issues -- it makes it easier to filter them. GSoC season will arrive soon and it would be handy to have the EASY issues filter-able. Also, helps in terms of improving the docs (filter DOC).

[jona-sassenhagen]

Wrt. 3, do you mean you haven't been able to get much speedup beyond what we already have in the current MNE CUDA code? Cause it seems to make a substantial improvement to me.

Wrt. the MKL stuff, maybe you have an idea what would actually be a good test case. But yes, in my personal tests, I see absolutely no gain.

[larsoner]

Wrt. 3, do you mean you haven't been able to get much speedup beyond what
we already have in the current MNE CUDA code? Cause it seems to make a
substantial improvement to me.

In filtering the difference is huge, yeah. But here I mean specifically for
the time-frequency (e.g., PSD, morlet) functions. I tried to optimize them
a couple times to use CUDA and actually lost a bit of speed.

Wrt. the MKL stuff, maybe you have an idea what would actually be a good

test case. But yes, in my personal tests, I see absolutely no gain.

I think @jasmainak had the same problem. But @agramfort has seen some gains
before? I have never used it.

[jona-sassenhagen]

Ah okay. Yes, my speed gains for CUDA were for filtering.

I've only tested MKL for filtering, too.

Is there an option to have a separate package that integrates with MNE and provides fftw capabilities withou GPL trouble?

[larsoner]

We looked into (Py)FFTW about 3 years ago and it yielded ~3x speed gains but we couldn't get around licensing problems. Read the referenced link if you're curious about it.

[jona-sassenhagen]

My idea was, how about a model similar to how Ubuntu handles nonfree software - a different small project, with its own repo and under GPL, that connects MNE to PyFFTW without being part of MNE, and without MNE code pointing to it.

[larsoner]

By monkey-patching, presumably? I think you could do it (assuming it's not a license problem) but it would be more work than it sounds like initially. Our code does some gymnastics to deal with cuda vs not so you'd have to deal with that, and then you'd also have to deal with the differences between FFTW outputs and fftpack outputs. It's not insurmountable (we actually already have it since CUDA uses the FFTW forms) but it is a pain. Right now I'm +0 on the idea but if others agree it's worthwhile I could work on it.

[jona-sassenhagen]

Yes, something like that. Maybe the TF code could be refactored to the extent that it could be arranged relatively hassle-free.
I couldn't code this btw - so it's not like I could volunteer. I think the best I can offer is search-and-replacing fft/rfft :)

My hunch is though in the long run betting on CUDA would be smarter.

[agramfort]

FYI scipy/scipy#5295 this was just released in scipy. looks like it could be the way out...

[larsoner]

@agramfort so you're okay with something like a import mne_gpl monkey-patching mne to provide FFTW, and/or other enhancements we can't include in the main package as BSD?