laszukdawid
commented
6 months ago Hey @Aphexus, good question. The benefit of GPU depends on the type of problem and the amount of data. Since finding extrema, in the simplest form, is comparing whether a sample is larger/smaller than it's neigbours, then we could do that independently for all samples (provided that we include neigbours in their batches). Thus, on GPU the complexity of finding extrema is O(1) (constant execution time), whereas, if we do one at the time, then that's O(N) (we do a single sweep over all data). However, when using GPU, one also needs to consider the cost of sending the data back and forth, onto the GPU, and converting data types. And, that adds up.
Given that we're using numpy under the hood, which is a compiled and optimized numerical library, doing simple arithmetic operations is just a few clock cycles. So, doing that for a small data set, that's almost instantaneous; the most time is spent actually understanding the python command. However, in general, O(N) is better than O(1) so at some point it'd be beneficial to use GPU. In this case, I don't know where the inflection point is. In my old experiments, even time series of over thousands of data samples were better to compute on CPU than GPU. Improving the cpu parallelization and minimizing data type conversion was a bigger gain, and, I'm guessing, that pushed the "gain threshold" to over a few tens of thousands of samples before considering GPU. In my case, there was no benefit.
The biggest gain in EMD is definitely making the whole procedure parallelizable, rather than wait for consecutive proto-IMFs. Then, the improvements to spline creations would be beneficial.
What about using the GPU to batch the data to speed up extrema finding? One should be able to partition the data basically at the Nyquist frequency and then have the GPU parallelize finding the max and min over each segment. This should give an extreme boost in performance. As long as there are not multiple extrema per segment then it should be very easy to do.