3月
24

x86 のビットスキャン命令の SIMD 化

梅澤 威志 技術ネタ 2013-03-24

6月に Haswell が出ると予想されています。Haswell には AVX2 が搭載され、256bit レジスタで整数 SIMD 演算ができるようになります。他にも色々と新命令が追加されています。

新命令（具体的には VPGATHERDD）を眺めながら、「これ使ったらハフマンデコードの並列実行ができるんじゃね？」と思って Ut Video Codec Suite のハフマンデコードのアセンブラソースを見ていたのですが、1つ問題点がありました。BSR (Bit Scan Reverse) 命令の SIMD 版が無いのです。

元のアルゴリズムをそのまま SIMD 化したい場合、「4つのダブルワードそれぞれの BSR の結果を4つのダブルワードに格納する」という、PBSRD とでも命名されるような処理が必要になります。

汎用レジスタに移動して処理する場合

もっとも簡単なのは、一旦スカラーにして処理するというものです。たとえば以下の通り。

    pextrd      eax, xmm0, 0
    bsr         eax, eax
    pinsrd      xmm1, eax, 0
    pextrd      eax, xmm0, 1
    bsr         eax, eax
    pinsrd      xmm1, eax, 1
    pextrd      eax, xmm0, 2
    bsr         eax, eax
    pinsrd      xmm1, eax, 2
    pextrd      eax, xmm0, 3
    bsr         eax, eax
    pinsrd      xmm1, eax, 3

処理は自明だし分かりやすくていいのですが、pextrd/pinsrd はそれほど速くないのが問題です。ymm レジスタに対して処理しようとするとさらに倍書くことになって遅さ倍増ですし、命令デコーダに対する負荷も心配です。できれば他の方法を取りたいところです。

浮動小数点数に変換して処理する場合

実は、BSR 命令相当の処理は浮動小数点数に変換することで達成できることが知られています。（「よく」知られているかどうかは分かりません）

たとえば、2進数で 100101002 を浮動小数点数に変換すると 1.00101002 × 27 になりますが、指数部に出てくる 7 こそが元の 100101002 の BSR の結果となります。

というわけで、以下のコードで上と同じ処理ができます。

    cvtdq2ps    xmm1, xmm0
    psrld       xmm1, 23
    psubd       xmm1, 0000007f0000007f0000007f0000007fh
    ; 実際には上のような即値は使えないので、
    ; メモリに置いておくか、それをレジスタにロードして使う

cvtdq2ps で4つのダブルワードを4つの単精度浮動小数点数に変換し、psrld で指数部を LSB まで移動し、psubd で指数部に履かされたゲタを取り除きます。浮動小数点数が出てくるので速度が気になるところですが、cvtdq2ps 命令のレイテンシはたったの3クロックなので問題ではありません。この方法だと ymm レジスタになっても全く同じなので遅くなる心配もありません。

# てゆーか、 CVTDQ2PS 命令が実装されているってことは、
# 回路的には PBSRD 命令と等価な処理は実装されているわけで、
# それがアーキテクチャ命令として存在していないのが残念。

たった3命令で実現できて万々歳…と言いたいところですが、上のコードだと2つの点でうまく動きません。

  • 最上位ビットが立っている場合（BSR の結果が 31 になる場合）に正しい結果にならない。
  • 入力に立っているビットが多い場合に正しい結果にならないことがある。

最上位ビットが立っている場合のケア

最上位ビットが立っている場合に正しい結果にならないのは、cvtdq2ps 命令の入力は4つの「符号付き」ダブルワードであるためにマイナスの数として扱われてしまうからです。

という訳で、最上位ビットが立っている場合に無理やり 31 になるようにしなければなりません。以下のようなコードでしょうか。

    cvtdq2ps    xmm1, xmm0
    psrld       xmm1, 23
    psubd       xmm1, 0000007f0000007f0000007f0000007fh

    psrad       xmm0, 31
    por         xmm1, xmm0
    pand        xmm1, 0000001f0000001f0000001f0000001fh

SSE4.1 だと PBLENDVB が使えるので、以下のようにちょっと短くできます（速いかどうかは謎）。

    cvtdq2ps    xmm1, xmm0
    psrld       xmm1, 23
    psubd       xmm1, 0000007f0000007f0000007f0000007fh

    psrad       xmm0, 31
    pblendvb    xmm1, 0000001f0000001f0000001f0000001fh, xmm0

ちなみに、PBLENDVB はマスクレジスタとして xmm0 しか取れず若干使いづらいのですが、AVX の VPBLENDVB だと任意の xmm/ymm レジスタを指定できるようになって使い勝手が向上しています。

ビットがたくさん立っている場合のケア

たとえば、 0x7ffffff0 を入力した場合、その浮動小数点数表現は 1.111111111111111111111111112 × 230 （小数点の後ろに 1 が 26 個）ですが、単精度浮動小数点数は仮数部が（小数点以下）23ビットしかないので、丸めて 1.02 × 231 に変換されます。結果として正しい結果より 1 大きくなります。

丸めを防止するには下の方のビットを落としてしまえばいいのですが、どこまでが落としていいビットなのかは BSR の結果を知らなければ判断できないため、別の方法が必要です。結果が1大きくなっている（結果で示されるビットが立っている）かどうかで判断するほうが楽でしょう。

    cvtdq2ps    xmm1, xmm0
    psrld       xmm1, 23
    psubd       xmm1, 0000007f0000007f0000007f0000007fh

    vpsllvd     xmm2, 00000001000000010000000100000001h, xmm1 ; AVX2 only
    pand        xmm2, xmm0
    pcmpeqd     xmm2, 00000000000000000000000000000000h
    paddd       xmm1, xmm2

3/26追記: たぶん以下の方が1クロック速い。

    cvtdq2ps    xmm1, xmm0
    psrld       xmm1, 23
    psubd       xmm1, 0000007f0000007f0000007f0000007fh

    vpsrlvd     xmm2, xmm0, xmm1 ; AVX2 only
    pcmpeqd     xmm2, 00000000000000000000000000000000h
    paddd       xmm1, xmm2

3/27追記: どうせ VEX プレフィックス付き SIMD 命令を使わなければいけないのだから、以下のように命令の依存関係を改善すればたぶんさらに1クロック速い。

    vcvtdq2ps   xmm1, xmm0
    vpsrld      xmm1, xmm1, 23
    vpsubd      xmm3, xmm1, 00000080000000800000008000000080h
    vpsubd      xmm1, xmm1, 0000007f0000007f0000007f0000007fh

    vpsrlvd     xmm2, xmm0, xmm1 ; AVX2 only
    vpaddd      xmm1, xmm3, xmm2

各ダブルワードごとに異なるビット数のシフトをするために、AVX2 で追加された VPSLLVD/VPSRLVD 命令が必要になってしまいました。なお、上のコードはテストしていません（AVX2 エミュレータを使えばテストできますが）。

入力が 24bit 以下であることが保証されていれば丸めは起きないので、そちらの方向で対処した方がいいかもしれません。ついでに最上位ビットが立っている場合のケアも不要です。

倍精度浮動小数点数に変換して処理する場合

丸めを回避するには倍精度浮動小数点数を使う方法もあります。こちらは仮数部が52ビットあるので丸めは起きません。CVTDQ2PD の入力は CVTDQ2PS と同じく符号付きダブルワードなので、最上位ビットが立っている場合のケアは相変わらず必要です。

    pshufd      xmm1, xmm0, 0dh
    pshufd      xmm0, xmm0, 08h

    cvtdq2pd    xmm0, xmm0
    psrld       xmm0, 52
    psubd       xmm0, 00000000000003ff00000000000003ffh

    cvtdq2pd    xmm1, xmm1
    psrld       xmm1, 52
    psubd       xmm1, 00000000000003ff00000000000003ffh

    pslld       xmm1, 32
    por         xmm1, xmm0

でもこれは長いですね。

速いの？

で、当然「これは速いのか？」という疑問が出てくるわけですが… ベンチマークは別の記事で。

# そもそもどうやって計測しようか

BSF の場合

以上は BSR (Bit Scan Reverse) の場合ですが、下位ビットからスキャンする BSF (Bit Scan Forward) 命令の場合は浮動小数点数に変換する方法は直接的には使えません。

最も下位の1のビットだけを抽出してしまえば BSF も BSR も結果は同じになるので、その方針で行くと以下のようになります。

    movdqa      xmm1, xmm0
    psubd       xmm0, 00000001000000010000000100000001h
    pandn       xmm0, xmm1

    cvtdq2ps    xmm1, xmm0
    psrld       xmm1, 23
    psubd       xmm1, 0000007f0000007f0000007f0000007fh

この場合、最上位ビットが立っている場合のケアは（場合によっては）必要ですが、ビットがたくさん立っている場合のケアは不要です。

他の方法はありますかね？

Address: http://umezawa.dyndns.info/wordpress/?p=3743
«
»
Trackback

only 1 comment untill now

  1. 或るプログラマの一生 @ 2013-04-02 22:01

    x86 のビットスキャン命令の SIMD 化（その２）

    ひとつ改善点を思いついたのとベンチマークです。 改善点 浮動小数点数に変換して処理する場合でビットがたくさん立っている場合のケアですが、一番上の 1 のビットから連続して 25 ビ…

Add your comment now