3

よく知られているMITビットカウントアルゴリズムのバージョンを使用して、SSE2命令を使用してコンウェイのライフゲームで隣人をカウントしたいと思います。

これがcのMITビットカウントで、63ビットを超えるビットカウントをカウントするように拡張されています。

int bitCount(unsigned long long n)
{
unsigned long long uCount;

uCount = n – ((n >> 1) & 0×7777777777777777)
           - ((n >> 2) & 0×3333333333333333)
           - ((n >> 3) & 0×1111111111111111);
return ((uCount + (uCount >> 4))
& 0x0F0F0F0F0F0F0F0F) % 255;
}

これがPascalのバージョンです

function bitcount(n: uint64): cardinal;
var ucount: uint64;
begin
  ucount:= n - ((n shr 1) and $7777777777777777)
             - ((n shr 2) and $3333333333333333) 
             - ((n shr 3) and $1111111111111111);
  Result:= ((ucount + (count shr 4)) 
           and $0F0F0F0F0F0F0F0F) mod 255;
end;

この構造のビットを並行してカウントしようとしています。

  32-bit word where the pixels are laid out as follows.
  lo-byte         lo-byte neighbor
  0 4 8 C  048C   0 4 8 C 
   +---------------+
  1|5 9 D  159D   1|5 9 D 
   |               |
  2|6 A E  26AE   2|6 A E  
   +---------------+
  3 7 B F  37BF   3 7 B F 
 |-------------|            << slice A
   |---------------|        << slice B
     |---------------|      << slice C

この構造の中央に16ビットがあり、検索する必要があることに注意してください。SSE2を使用して、中央の16ビットのそれぞれのネイバーカウントを計算したいと思います。これを行うために、スライスAをXMM0ローワードワードに、スライスBをXXM0-dword1などに配置します。XMM0をXMM1にコピーし、XMM0のローワードのビットのビット
をマスクします。XMM0のワード1についても同じようにします。異なるスライスとマスクを使用して、XMM0とXMM1の各単語が異なるピクセルのネイバーを保持していることを確認します。012-456-89A5

質問
MITビットカウントを微調整して、各XMMワードのワード/ピクセルあたりのビットカウントを取得するにはどうすればよいですか。

備考
ルックアップテーブルを使用したくないのは、すでにそのアプローチがあり、SSE2がルックアップテーブルへのメモリアクセスを必要としないことでプロセスを高速化するかどうかをテストしたいからです。

私はこれをDelphiでプログラミングしており、x86 + SSE2アセンブリコードを使用しているため、SSEアセンブリを使用した回答が最適です。

4

1 に答える 1

3

... % 255最終式に使用できる整数モジュラス命令がないため、MIT アルゴリズムを SSE2 に実装するのは困難です。そこにあるさまざまな popcnt メソッドの中で、SSE に最も簡単かつ効率的に役立つものは、おそらくHenry S. Warren による「Hackers Delight」の第 5 章の最初のものであり、ここでは SSE 組み込み関数を使用して C で実装しました。

#include <stdio.h>
#include <emmintrin.h>

__m128i _mm_popcnt_epi16(__m128i v)
{
    v = _mm_add_epi16(_mm_and_si128(v, _mm_set1_epi16(0x5555)), _mm_and_si128(_mm_srli_epi16(v, 1), _mm_set1_epi16(0x5555)));
    v = _mm_add_epi16(_mm_and_si128(v, _mm_set1_epi16(0x3333)), _mm_and_si128(_mm_srli_epi16(v, 2), _mm_set1_epi16(0x3333)));
    v = _mm_add_epi16(_mm_and_si128(v, _mm_set1_epi16(0x0f0f)), _mm_and_si128(_mm_srli_epi16(v, 4), _mm_set1_epi16(0x0f0f)));
    v = _mm_add_epi16(_mm_and_si128(v, _mm_set1_epi16(0x00ff)), _mm_and_si128(_mm_srli_epi16(v, 8), _mm_set1_epi16(0x00ff)));
    return v;
}

int main(void)
{
    __m128i v0 = _mm_set_epi16(7, 6, 5, 4, 3, 2, 1, 0);
    __m128i v1;

    v1 = _mm_popcnt_epi16(v0);

    printf("v0 = %vhd\n", v0);
    printf("v1 = %vhd\n", v1);

    return 0;
}

次のようにコンパイルしてテストします。

$ gcc -Wall -msse2 _mm_popcnt_epi16.c -o _mm_popcnt_epi16
$ ./_mm_popcnt_epi16 
v0 = 0 1 2 3 4 5 6 7
v1 = 0 1 1 2 1 2 2 3
$

約 16 の算術/論理命令のように見えるので、1 ポイントあたり約 16 / 8 = 2 クロックで実行する必要があります。

必要に応じて、これを生のアセンブラーに簡単に変換できます。各組み込みは単一の命令にマップされます。

于 2011-06-22T07:57:14.473 に答える