optimization - ビットレベル操作のアドバイス

Question

私は現在、比較、マスキング、シフトなど、データのビット レベル操作を多く含むプロジェクトに取り組んでいます。基本的に、長さが 20 ～ 40 バイトのビット パターンについては、長さが 8k バイト ～ 32k バイトのビットストリームのチャンクを検索する必要があります。

CUDAでそのような操作を最適化するための一般的なリソースを知っている人はいますか?

Answer 1

CUDA を使用してテキスト検索を行う方法について、SO に関する少なくとも 2 つの質問がありました。つまり、長いバイト文字列内の短いバイト文字列のインスタンスを見つけます。それはあなたがやりたいことと似ています。つまり、バイト文字列検索はビット文字列検索によく似ており、バイト文字列のビット数は 8 の倍数にしかならず、アルゴリズムは 8 ビットごとに一致のみをチェックします。SO で CUDA 文字列の検索または照合を検索し、それらが見つかるかどうかを確認します。

これに関する一般的なリソースはわかりませんが、次のようなことを試してみます。

各検索ビット文字列の 8 つのバージョンを準備することから始めます。各ビットストリングは、異なる数のビットをシフトしました。開始マスクと終了マスクも準備します。

start
01111111 
00111111 
...
00000001

end
10000000
11000000
...
11111110

次に、基本的に、さまざまなビット文字列とマスクを使用してバイト文字列検索を実行します。

計算能力が 2.0 以上のデバイスを使用している場合は、シフトされたビット文字列をグローバル メモリに格納します。開始マスクと終了マスクは、おそらくプログラム内の定数である可能性があります。

次に、バイト位置ごとに、8 つのスレッドを起動し、それぞれが 8 つのシフトされたビット文字列の異なるバージョンを長いビット文字列 (バイト文字列のように扱う) に対してチェックします。ブロックごとに、たとえば 32 バイトをチェックするのに十分な数のスレッドを起動し、ブロックあたりのスレッドの総数が 32 * 8 = 256 になるようにします。L1 キャッシュは、ブロックごとにシフトされたビット文字列を保持できる必要があります。良いパフォーマンスが得られますように。