vpconflictd

では、「conflict detection があれば Hist も速くなるネー」とか書いてあったけどちゃんと実装されました。

16要素の32bit値をそれぞれ比較して、値が衝突しているかどうかを調べます。

Histogram の処理、例えば、

for (int i=0; i<size; i++) {
    hist[ input[i] ]++;
}

が、SIMD化ができるかどうかは運に左右されて、input[i..(i+N-1)] に、同じ値が入っていなければ、Nの幅でSIMD化可能、入っていればSIMD化は難しいという処理になるのですが、これが実行時しか判定できない場合、99%SIMD化可能なのに、1%の衝突の為に全体をSIMD化できないということはよく起こりがちですね。(特に実行時の挙動に関する情報が全く無い自動ベクタライザの場合)

なので、ベクタの中に同じ値が入っている(衝突している)かどうかを高速に判定できれば、SIMD化できる範囲が広がる可能性が高まるわけです。

この、衝突しているかどうかを求めるのが、vpconflictd(_mm512_conflict_epi32)です。

他の15要素との比較結果を、下位16bitに入れます。

#include <immintrin.h>
#include <stdio.h>

unsigned int out[16];

void
test(unsigned int *p)
{
    __m512i v = _mm512_loadu_si512(p);
    v = _mm512_conflict_epi32(v);

    _mm512_storeu_si512(out, v);

    for (int i=0; i<16; i++) {
        printf("%d,", p[i]);
    }
    puts("");
    if (_mm512_test_epi32_mask(v,v)) {
        puts("conflict!!");
    }

    for (int i=0; i<16; i++) {
        int t = out[i];
        printf("%3d : ", i);
        for (int j=0; j<16; j++) {
            if (t & (1<<j)) {
                putchar('1');
            } else {
                putchar('0');
            }
        }

        puts("");
    }
}

int
main()
{
    unsigned int in0[16] = {0,1,2,3,
                            4,5,6,7,
                            8,9,10,11,
                            12,13,14,15};
    test(in0);

    puts("--");

    unsigned int in1[16] = {0,0,1,1,
                            2,2,3,3,
                            4,4,5,5,
                            6,6,7,7};

    test(in1);

    puts("--");
    unsigned int in2[16] = {0,1,2,3,
                            0,1,2,3,
                            0,1,2,3,
                            0,1,2,3};

    test(in2);
}

 $ gcc -mavx512cd conflict.c -O2 -std=c99
 $ sde -skx -- ./a.out

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
  0 : 0000000000000000
  1 : 0000000000000000
  2 : 0000000000000000
  3 : 0000000000000000
  4 : 0000000000000000
  5 : 0000000000000000
  6 : 0000000000000000
  7 : 0000000000000000
  8 : 0000000000000000
  9 : 0000000000000000
 10 : 0000000000000000
 11 : 0000000000000000
 12 : 0000000000000000
 13 : 0000000000000000
 14 : 0000000000000000
 15 : 0000000000000000
--
0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,
conflict!!
  0 : 0000000000000000
  1 : 1000000000000000
  2 : 0000000000000000
  3 : 0010000000000000
  4 : 0000000000000000
  5 : 0000100000000000
  6 : 0000000000000000
  7 : 0000001000000000
  8 : 0000000000000000
  9 : 0000000010000000
 10 : 0000000000000000
 11 : 0000000000100000
 12 : 0000000000000000
 13 : 0000000000001000
 14 : 0000000000000000
 15 : 0000000000000010
--
0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,
conflict!!
  0 : 0000000000000000
  1 : 0000000000000000
  2 : 0000000000000000
  3 : 0000000000000000
  4 : 1000000000000000
  5 : 0100000000000000
  6 : 0010000000000000
  7 : 0001000000000000
  8 : 1000100000000000
  9 : 0100010000000000
 10 : 0010001000000000
 11 : 0001000100000000
 12 : 1000100010000000
 13 : 0100010001000000
 14 : 0010001000100000
 15 : 0001000100010000

AVX512CD というまた別の拡張になっているので、コンパイルには-mavx512cd フラグが必要です。

AVX512F とは別の拡張になっていますが、KNL でも Skylake でも動くようです。

明日は @tanakmura が vpmadd52luq について書きます。