1

私が理解している限り、「最新の」CPU には、同じ操作で多くのデータをストリーミングするなど、バイナリ データを操作するための非常に印象的なルーチンがあります。

その場限りで、これらの CPU または GPU ハードウェアを使用して単純な命令 (1 GB のメモリに 5 ビットごとに設定) を作成するためのライブラリが見つかりません。古典的な| << &トリックだけです。

しかし、5 ビットごとまたは 721 ビットごとに設定することは、幅 5 または幅 721 の白黒写真に縦の黒い線を描くのと同じでなければならず、そのための高速な方法があると思います。

私の質問: Mainstream x86_64 Intel/AMD CPU または GPU で高速かつ効率的な方法でビットを操作する方法のヒントはありますか? オープンソースは副次的な条件です。

4

1 に答える 1

0

まず第一に、メモリの巨大なチャンクに対してこれを行うと、キャッシュ ミスによってボトルネックが発生します。現在の CPU は、ロード/ストアごとにかなりの数の命令を実行できますが、それでもメモリ帯域幅を最大限に活用できます。すでに L1 キャッシュにある数 k のメモリについて話している場合、この問題はさらに興味深いものになります。

721 番目のビットごとに設定している場合、ベクトルは役に立ちません。あなたのストライドは 90.125 バイトで、AVX512 ベクトルよりも大きいです。したがって、最適な解決策はOR、適切なアドレスで 1 バイトを実行することです。バイト内のビット位置とバイト位置を追跡するためのループの作成は簡単ではありません。コンパイル時の定数ストライドの場合は、8 ずつ展開すると簡単になります。(8 番目ごとに 1 バイトの追加インクリメントOR。)

; pointer in rdi
; loop counter in ecx
.loop:
    or byte ptr [rdi+90*0],  1<<0
    or byte ptr [rdi+90*1],  1<<1
    or byte ptr [rdi+90*2],  1<<2
    or byte ptr [rdi+90*3],  1<<3
    or byte ptr [rdi+90*4],  1<<4
    or byte ptr [rdi+90*5],  1<<5
    or byte ptr [rdi+90*6],  1<<6
    or byte ptr [rdi+90*7],  1<<7
    add rdi, 90*8 + 1
    sub ecx, 8
    jg .loop
    ; handle the last up to 7 iterations

コンパイル時の定数ではないストライドの場合、8 ビット レジスタを回転させることができstride % 8ますptr += stride/8 + carry。実際、レジスタからのカウントによるローテーションは、通常の ALU ops (最近の Intel) よりも少し遅くなりますが、可変カウント シフトも同様です。 

; ecx = unsigned int stride.  rdi=char *dest
mov  ebx, ecx
and  ecx, 7    ; ecx = stride%8
shr  ebx, 3    ; ebx = stride/8

mov  al, 1
.loop:
    or    byte ptr [rdi], al
    rol   al, cl
    add   rdi, rbx
    ;  efficiently figure out when we need to add an extra 1 to rdi
    ; lost interest at this point, feel free to edit or post another answer finishing this code.
    dec   edx
    jg   .loop

ラップ時にキャリーフラグを設定するバイト内ビット位置をインクリメントする方法を考えているので、実行できadcますptr+= stride + carry。または、追加する 0 または 1 を取得します。

短い歩幅

ビット ストライドが 128b に等しい場合、問題はありません。定数マスクを使用して読み取り/変更し、保存するだけPORです。

ストライドが小さければ、物事は面白くなります。ベクトル レジスタのビット単位の回転命令はありません。xmm レジスター内の複数のセット・ビットをシフトすることは、巧妙な方法で可能になる場合があります。

于 2015-08-02T01:33:59.203 に答える