1

我正在尝试加速 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 指令。

4

1 回答 1

3

您的LUT16阵列是 512kB（假设 along long是 64 位），这将完全破坏任意/随机数据的 L1/L2 缓存性能（L1 通常为 32kB，L2 通常为 256kB）。

首先，你不需要long long这个。其次，LUT8改为尝试。第三，只需使用内置的__popcnt内在函数。

于 2013-09-11T20:47:19.800 回答