c++ - 如何加快从内存到 CPU 的数据传输？

Question

我正在尝试加速 popcount 函数。这是代码:

extern ll LUT16[];
typedef long long ll;
typedef unsigned char* pUChar;
ll LUT16Word32Monobit(pUChar buf, int size) {
    assert(buf != NULL);
    assert(size > 0);
    assert(size % sizeof(unsigned) == 0);
    int n = size / sizeof(unsigned);
    unsigned* p = (unsigned*)buf;
    ll numberOfOneBits = 0;
    for(int i = 0; i < n; i++) {
        unsigned int val1 = p[i];
        numberOfOneBits += LUT16[val1 >> 16] + LUT16[val1 & 0xFFFF];
    }
    return numberOfOneBits;
}

这里有一些细节:

• buf 包含 1 GB 的数据
• LUT16[i] 包含 i 的二进制表示中的一位数，对于所有 0 <= i < 2^16

我尝试使用 openMP 来加快速度，但它不起作用。我必须补充一点，我使用的是 MS Visual Studio 2010，并且我已经启用了 openMP 指令。我相信 openMP 不能加快速度的原因之一是内存访问时间。有什么方法可以利用 DMA(直接内存访问)？

此外，我应该警告您我的 openMP 技能缺失；这里所说的是 openMP 部分(与上面的代码类似):

#pragma omp for schedule(dynamic,CHUNKSIZE)
for(int i = 0; i < n; i++) {
    unsigned int val1 = p[i];
    numberOfOneBits += LUT16[val1 >> 16] + LUT16[val1 & 0xFFFF];
}

CHUNKSIZE 设置为 64。如果我将它设置得更低，结果会比串行版本差，如果我将它设置得更高，它也没有任何好处。

此外，我不想使用处理器提供的 popcount 指令，也不想使用 SSE 指令。

Answer 1

你的 LUT16 数组是 512kB(假设一个 long long 是 64 位)，这将完全破坏你的 L1/L2 缓存性能对于任意/随机数据(L1通常为 32kB，L2 通常为 256kB)。

首先，您不需要为此long long。其次，试试 LUT8。第三，只需使用内置的 __popcnt内在的。