流的有效内存带宽使用

Question

我有一个通过250 MB数据流的应用程序，将一个简单而快速的神经网络阈值函数应用于数据块(每个数据块只有2个32位字)。根据(非常简单)计算的结果，该块不可预测地被推入64个桶中的一个。因此，这是一个大的流和64短(可变长度)流出来。

这是多次重复使用不同的检测功能。

计算内存带宽有限。我知道这一点，因为没有速度变化，即使我使用了一个判别式函数，它的计算量要大得多。

想象一下最坏的情况，我有我的64输出流，不幸的是，许多映射到相同的缓存线。然后，当我将接下来的64位数据写入流时，CPU必须将一条陈旧的缓存行清除到主存，并加载到适当的缓存行中。每个都需要64个字节的带宽.因此，我的带宽有限的应用程序可能正在浪费95%的内存带宽(不过，在这种假设的最坏情况下)。

甚至很难衡量效果，因此围绕它的设计方法就更加模糊了。或者，我甚至在追逐一个鬼瓶颈，不知怎么的，硬件优化比我更好？

如果有什么不同的话，我正在使用Core x86处理器。

编辑:下面是一些示例代码。它通过数组流，并将其元素复制到各种伪随机选择的输出数组中。使用不同数量的目标回收箱运行相同的程序会产生不同的运行时，尽管计算和内存读写量相同：

2输出流: 13秒

8输出流: 13秒

32输出流: 19秒

128输出流:29秒

512输出流: 47秒

使用512和2个输出流的区别是4X (可能？)由缓存线逐出开销引起的。

#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个输出框写入时，您将使用许多不同的内存位置。如果垃圾箱基本上是随机填充的，这意味着有时您将有两个存储库共享相同的缓存线。不是什么大问题；核心2 L1缓存是8路关联的.这意味着你只会遇到第9条缓存行的问题。只要在任何时候有65个活动内存引用(1读/64写)，8路联想就可以了。

L2缓存显然是12路关联(3/6MB总计，所以12不是一个奇怪的数字)。因此，即使您在L1中发生了碰撞，仍然很有可能没有命中主内存。

但是，如果你不喜欢这个，就重新安排内存中的垃圾桶。与其按顺序排列每个垃圾箱，不如将它们交织起来。对于bin 0，在偏移量0-63处存储块0-15，在偏移量8192-8255处存储块16-31。对于bin 1，将块0-15存储在偏移量64-127处，等等。这只需几个位移位和掩码，但结果是一对回收箱共享8条缓存线。

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

Answer 2

您是否可以选择将输出流写入带有内联元数据的单个流，以标识每个“块”？如果要读取“块”，在其上运行阈值函数，而不是将其写入特定的输出流，只需编写它所属的流(1字节)，然后是原始数据，则会大大减少对您的打击。

我不建议这样做，除非你说你必须多次处理这些数据。在每次连续运行时，您将读取输入流以获得bin号(1字节)，然后在接下来的8个字节上对该bin执行您需要做的任何操作。

就该机制的缓存行为而言，由于您只在两条数据流中滑动，并且在第一种情况下，写入正在读取的所有数据，硬件将为您提供所有您可能希望得到的帮助，包括预取、缓存线优化等。

如果每次处理数据时都要添加额外的字节，那么最糟糕的情况缓存行为就是一般情况。如果你能买得起仓库，对我来说这似乎是一场胜利。

Answer 3

如果你真的绝望了，这里有一些想法..。

您可以考虑升级硬件。对于有点类似于您的流式应用程序，我发现通过切换到i7处理器，速度有了很大的提高。另外，对于内存绑定的工作，AMD处理器应该比Core 2更好(尽管我最近还没有使用过它们)。

您可能考虑的另一个解决方案是使用像CUDA这样的语言在图形卡上进行处理。图形卡调整为具有非常高的内存带宽和快速浮点的数学。预计将花费5到20倍的开发时间为CUDA代码相对于一个直接的、非优化的C实现。