用于流式传输的高效内存带宽

Question

我有一个应用程序,通过250 MB的数据流,应用一个简单快速的神经网络阈值函数到数据块(每个只有2个32位字).基于(非常简单的)计算的结果,块被不可预测地推入64个箱中的一个.所以这是一个大流和64个较短(可变长度)的流.

使用不同的检测功能重复多次.

计算是内存带宽有限.我可以说这是因为即使我使用的计算密集程度更高的判别函数也没有速度变化.

构造新流的写入以优化内存带宽的最佳方法是什么？我特别认为理解缓存使用和缓存行大小可能在这方面发挥重要作用.想象一下最糟糕的情况,我有64个输出流,运气不好,许多映射到同一个缓存行.然后,当我将下一个64位数据写入流时,CPU必须将过时的高速缓存行清除到主存储器,然后加载到正确的高速缓存行中.每个都使用64 BYTES的带宽...所以我的带宽有限的应用可能会浪费95%的内存带宽(尽管在这个假设的最坏情况下).

甚至很难尝试测量效果,因此围绕它设计方法更加模糊.或者我甚至追逐一个幽灵瓶颈,以某种方式硬件优化得比我更好？

我正在使用Core II x86处理器,如果这有任何区别的话.

编辑:这是一些示例代码.它通过一个数组流,并将其元素复制到伪随机选择的各种输出数组.使用不同数量的目标bin运行相同的程序会产生不同的运行时,即使完成了相同数量的计算和内存读写操作:

2个输出流:13秒
8个输出流:13秒
32个输出流:19秒
128个输出流:29秒
512个输出流:47秒

使用512与2输出流之间的差异是由缓存行驱逐开销引起的4倍(可能是??).

#include <stdio.h>
#include <stdlib.h>
#include <ctime>

int main()
{
  const int size=1<<19;
  int streambits=3;
  int streamcount=1UL<<streambits; // # of output bins
  int *instore=(int *)malloc(size*sizeof(int));
  int **outstore=(int **)malloc(streamcount*sizeof(int *));
  int **out=(int **)malloc(streamcount*sizeof(int));
  unsigned int seed=0;

  for (int j=0; j<size; j++) instore[j]=j;

  for (int i=0; i< streamcount; ++i) 
    outstore[i]=(int *)malloc(size*sizeof(int));

  int startTime=time(NULL);
  for (int k=0; k<10000; k++) {
    for (int i=0; i<streamcount; i++) out[i]=outstore[i];
    int *in=instore;

    for (int j=0; j<size/2; j++) {
      seed=seed*0x1234567+0x7162521;
      int bin=seed>>(32-streambits); // pseudorandom destination bin
      *(out[bin]++)=*(in++);
      *(out[bin]++)=*(in++);
    }

  }
  int endTime=time(NULL);
  printf("Eval time=%ld\n", endTime-startTime);
}

Answer 1

当您写入 64 个出纸槽时，您将使用许多不同的内存位置。如果垃圾箱基本上是随机填充的，则意味着有时会有两个可以共享同一缓存行的垃圾箱。问题不大；Core 2 L1 缓存是 8 路关联的。这意味着只有第 9 个缓存行才会出现问题。任何时候只要 65 个实时内存引用（1 个读/64 个写），8 路关联就可以了。

L2 缓存显然是 12 路关联的（总共 3/6MB，所以 12 并不是一个奇怪的数字）。因此，即使您在 L1 中发生冲突，您也很有可能仍然没有到达主内存。

但是，如果您不喜欢这样，请重新排列内存中的垃圾箱。不要按顺序存储每个容器，而是将它们交错排列。对于 bin 0，将块 0-15 存储在偏移量 0-63 处，但将块 16-31 存储在偏移量 8192-8255 处。对于 bin 1，将块 0-15 存储在偏移量 64-127 等处。这仅需要一些位移和掩码，但结果是一对 bin 共享 8 个缓存线。

在这种情况下加速代码的另一种可能方法是 SSE4，尤其是在 x64 模式下。您将获得 16 个寄存器 x 128 位，并且可以优化读取 (MOVNTDQA) 以限制缓存污染。不过，我不确定这是否会对读取速度有很大帮助 - 我希望 Core2 预取器能够捕捉到这一点。读取连续整数是最简单的访问方式，任何预取器都应该对此进行优化。