在没有加速FFT的情况下增加占用率

Question

问题

我必须计算许多傅里叶变换.我想与我的许多内核并行执行这些操作.请注意,我不想要并行FFT算法,我只想发布许多令人尴尬的并行FFT.

我发现,当我的CPU使用率上升时,我的完成时间不会减少.

例

我们创建一些随机数据

In [1]: import numpy as np

In [2]: x = np.random.random(10000000)  # some random data

并计算一次计算FFT的时间和计算一次FFT所需的时间.

In [3]: %time _ = np.fft.rfft(x)        # cost of one run
CPU times: user 589 ms, sys: 23.9 ms, total: 612 ms
Wall time: 613 ms

In [4]: %time _ = np.fft.rfft(x)        # there is some speedup from mulitple runs
CPU times: user 365 ms, sys: 12.4 ms, total: 378 ms
Wall time: 381 ms

我们按顺序在一系列数据上运行它

In [5]: %time _ = map(np.fft.rfft, [x] * 12)  # many runs sequentially
CPU times: user 4.4 s, sys: 135 ms, total: 4.54 s
Wall time: 4.54 s

In [6]: 4.54 / 12                       # Same cost per FFT
Out[6]: 0.37833333333333335

我们做同样的事情,但现在使用四个线程的线程池.

In [7]: from multiprocessing.pool import ThreadPool

In [8]: pool = ThreadPool(4)            # I have four physical cores

In [9]: %time _ = pool.map(np.fft.rfft, [x] * 12)
CPU times: user 15.5 s, sys: 1.3 s, total: 16.8 s
Wall time: 4.79 s

我们发现没有加速.但是,我们确实发现CPU的使用率top接近400%.这不是GIL的问题.关于FFT的一些东西不能很好地并行化.也许我们正在颠覆更高级别的缓存？

硬件: Intel(R)Core(TM)i5-3320M CPU @ 2.60GHz

题

通常这里发生了什么,有没有办法利用多个内核并行加速多个FFT？

Answer 1

在我的工作站上，ThreadPool确实提供了加速（尽管不是完美的）：

In [42]: x = np.random.random(2**23)

In [43]: %time _ = list(map(np.fft.rfft, [x]*12))
CPU times: user 3.32 s, sys: 380 ms, total: 3.7 s
Wall time: 3.7 s

In [44]: tpool = ThreadPool(4)

In [45]: %time _ = list(tpool.map(np.fft.rfft, [x]*12))
CPU times: user 5.4 s, sys: 596 ms, total: 6 s
Wall time: 1.62 s

In [46]: 3.7/4
Out[46]: 0.925

我正在使用Python3，所以也许有什么东西？否则，它可能是硬件。FFT 受内存限制，因此单个线程很可能会导致内存系统饱和。通过下降到允许您控制关联性的环境，您也许能够获得更好的内存系统局部性。

硬件

英特尔(R) 酷睿(TM) i7-4930K CPU @ 3.40GHz。