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] には、0 <= i < 2^16 のすべてについて、i のバイナリ表現の 1 ビットの数が含まれます。

高速化のためにopenMPを使用しようとしましたが、うまくいきません。MS Visual Studio 2010 を使用していること、および openMP ディレクティブを有効にしていることを付け加えなければなりません。openMP が高速化しない理由の 1 つは、メモリ アクセス時間にあると思います。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