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

Question

问题

我必须计算许多傅里叶变换。我想与我的许多核心并行地做这些。请注意，我不想要并行 FFT 算法，我只想启动许多令人尴尬的并行 FFT。

我发现，虽然我的 CPU 使用率增加了，但完成时间并没有减少。

例子

我们创建一些随机数据

In [1]: import numpy as np

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

以及计算 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。

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

Increased occupancy without speedup in FFT

python

multithreading

numpy

fft

scipy

问题

例子

问题

硬件