python - 加速 numpy 嵌套循环

Question

我正在使用 numpy 和 cython 在 python 中编写无线网络模拟，其中假设有许多节点 no_nodes 随机散布在二维平面上，它们发出一些波形及其各自的接收器，再次随机散布在 2d 平面上。每个发送节点都会产生一个波形，我称之为output(每个节点都可以产生不同长度的输出)。

我想做的是将每个节点的这些输出汇总为一个大波形，该波形将作为每个接收器的输入进行解调等。现在有两个关键点:

• 发送器异步发送，因此必须为每个发送节点维护一个start_clock和一个end_clock，以便正确地求和波形
• j 发送节点的输出在被i 节点接收之前根据函数attenuate(i,j)

代码如下:

#create empty 2d array (no_rx_nodes x no_samples for each waveform)
waveforms = np.zeros((no_nodes, max(end_clock))) 

for i in range(no_nodes): #calculate the waveform for each receiver
    for j in range(no_nodes): #sum the waveforms produced by each transmitter
        waveforms[i, start_clock[j]:end_clock[j]] += output[j,:] * attenuate(i,j)
return waveforms

对上面的一些评论:

• output[j, :]为发射机j的输出波形
• waveforms[i,:]是接收器i接收到的波形

我希望我在这里想要完成的事情已经很清楚了。因为产生的波形非常大(大约 10^6 个样本)，我也尝试将此代码转换为 cython，但没有注意到任何特定的加速(可能好 5-10 倍，但仅此而已)。我想知道是否还有其他方法可以加快速度，因为它是整个模拟的真正瓶颈(计算时间几乎与其余代码一样多，实际上相当比那更复杂)。

Answer 1

这是一个内存带宽受限问题，内存带宽约为 3GB/s，您可以从中获得的最佳内循环时间约为 2-4 毫秒。 要达到该界限，您需要阻止内部循环以更好地利用 cpu 缓存(numexpr 为您完成此操作):

for i in range(no_nodes):
    for j in range(no_nodes):
        # should be chosen so all operands fit in the (next-to-)last level cache
        # first level is normally too small to be usable due to python overhead
        s  = 15000 
        a = attenuation[i,j]
        o = output[j]
        w = waveforms[i]
        for k in range(0, w.size, s): 
            u = min(k + s, w.size)
            w[k:u] += o[k:u] * a
        # or: numexpr.evaluate("w + o * a", out=w)

使用 float32 数据而不是 float64 也应该将内存带宽要求减半并将性能提高一倍。

为了获得更大的加速，你必须重新设计你的完整算法以获得更好的数据局部性