Edited at
AVX-512Day 12

vpconflictd

More than 3 years have passed since last update.

http://sbel.wisc.edu/Courses/ME964/Literature/LeeDebunkGPU2010.pdf

では、「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 について書きます。