是否可以使用 Wojciech Mula 算法 popcount __m256i 并将结果存储在 8 个 32 位字而不是 4 个 64 位字中?
Is it possible to popcount __m256i and store result in 8 32-bit words instead of the 4 64-bit using Wojciech Mula algorithm's?
我最近发现 AVX2 没有 __m256i 的 popcount,我发现做类似事情的唯一方法是遵循 Wojciech Mula 算法:
__m256i count(__m256i v) {
__m256i lookup = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2,
2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 1, 2, 2, 3,
1, 2, 2, 3, 2, 3, 3, 4);
__m256i low_mask = _mm256_set1_epi8(0x0f);
__m256i lo =_mm256_and_si256(v,low_mask);
__m256i hi = _mm256_and_si256( _mm256_srli_epi32(v, 4), low_mask);
__m256i popcnt1 = _mm256_shuffle_epi8(lookup,lo);
__m256i popcnt2 = _mm256_shuffle_epi8(lookup,hi);
__m256i total = _mm256_add_epi8(popcnt1,popcnt2);
return _mm256_sad_epu8(total,_mm256_setzero_si256());
}
问题是return我把8个short的和变成long而不是4个short的和变成int。
当前情况:
我有 __m256i x 其中包含 8 个 32 位 int:
- 01101011111000011100000000000000
- 01110101011010010111100000000000
- 10100100011011000101010000000000
- 11101010100001001111000000000000
- 10010011111111001001010000000000
- 00011110101100101000000000000000
- 00011101011000111011000000000000
- 10011011100010100000110000000000
__m256i res = count(x);
资源包含:
- 24
- 21
- 22
- 21
结果为4长64位
期望值:
我有 __m256i x 其中包含 8 个 32 位整数:
- 01101011111000011100000000000000
- 01110101011010010111100000000000
- 10100100011011000101010000000000
- 11101010100001001111000000000000
- 10010011111111001001010000000000
- 00011110101100101000000000000000
- 00011101011000111011000000000000
- 10011011100010100000110000000000
__m256i res = count(x);
资源包含:
- 11
- 13
- 10
- 11
- 12
- 9
- 11
- 10
结果是 8 int 32 位。
希望我说的很清楚,请不要犹豫向我询问更精确的信息。
谢谢。
AVX-512VPOPCNTDQ 具有 _mm256_popcnt_epi32
to popcount in 32-bit chunks, also a 64-bit chunk size version. Outside of Xeon Phi, it's new in Ice Lake,它还引入了 AVX512BITALG,它也具有 vpopcnt
.
的字节和字(16 位)块大小
使用 AVX2
您引用的原始代码依赖于 _mm256_sad_epu8
内在函数,它专门用于对 64 位字内的字节求和。
要使用 32 位字的总和获得相同的结果,您需要做一些稍微不同的事情。以下应该有效:
__m256i popcount_pshufb32(__m256i v) {
__m256i lookup = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2,
2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 1, 2, 2, 3,
1, 2, 2, 3, 2, 3, 3, 4);
__m256i low_mask = _mm256_set1_epi8(0x0f);
__m256i lo = _mm256_and_si256(v, low_mask);
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(v, 4), low_mask);
__m256i popcnt1 = _mm256_shuffle_epi8(lookup, lo);
__m256i popcnt2 = _mm256_shuffle_epi8(lookup, hi);
__m256i sum8 = _mm256_add_epi8(popcnt1, popcnt2);
return _mm256_srli_epi32(
_mm256_mullo_epi32(sum8, _mm256_set1_epi32(0x01010101)), 24);
// vpmulld is slowish (2 uops) on most recent Intel CPUs
// but still single-uop on AMD
}
所以我们用乘法和移位代替了_mm256_sad_epu8
。这应该是合理的。在我的测试中,it is slightly slower than the original 64-bit version, but the difference is relatively small.
通过使用不同的两条指令从字节累加到 32 位块,您可以以多一个向量常量为代价在 Intel 上获得稍微更好的性能。 AMD Zen1/2/3 至少与上面的版本一样有效。
32 位 SIMD 整数乘法在最近的 Intel CPU 上是 2 微指令(对于 SIMD 整数乘法单元),但是成对的乘法累加指令(8->16 和 16->32)是每个一个。 (https://uops.info/) 这需要多一个常量,但指令数量相同,以减少 uops,特别是如果编译器可以在循环中重用这些常量。
__m256i popcount_pshufb32(__m256i v) {
__m256i lookup = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2,
2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 1, 2, 2, 3,
1, 2, 2, 3, 2, 3, 3, 4);
__m256i low_mask = _mm256_set1_epi8(0x0f);
__m256i lo = _mm256_and_si256(v, low_mask);
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(v, 4), low_mask);
__m256i popcnt1 = _mm256_shuffle_epi8(lookup, lo);
__m256i popcnt2 = _mm256_shuffle_epi8(lookup, hi);
__m256i sum8 = _mm256_add_epi8(popcnt1, popcnt2);
return _mm256_madd_epi16(_mm256_maddubs_epi16(sum8, _mm256_set1_epi8(1)),
_mm256_set1_epi16(1));
}
我最近发现 AVX2 没有 __m256i 的 popcount,我发现做类似事情的唯一方法是遵循 Wojciech Mula 算法:
__m256i count(__m256i v) {
__m256i lookup = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2,
2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 1, 2, 2, 3,
1, 2, 2, 3, 2, 3, 3, 4);
__m256i low_mask = _mm256_set1_epi8(0x0f);
__m256i lo =_mm256_and_si256(v,low_mask);
__m256i hi = _mm256_and_si256( _mm256_srli_epi32(v, 4), low_mask);
__m256i popcnt1 = _mm256_shuffle_epi8(lookup,lo);
__m256i popcnt2 = _mm256_shuffle_epi8(lookup,hi);
__m256i total = _mm256_add_epi8(popcnt1,popcnt2);
return _mm256_sad_epu8(total,_mm256_setzero_si256());
}
问题是return我把8个short的和变成long而不是4个short的和变成int。
当前情况:
我有 __m256i x 其中包含 8 个 32 位 int:
- 01101011111000011100000000000000
- 01110101011010010111100000000000
- 10100100011011000101010000000000
- 11101010100001001111000000000000
- 10010011111111001001010000000000
- 00011110101100101000000000000000
- 00011101011000111011000000000000
- 10011011100010100000110000000000
__m256i res = count(x);
资源包含:
- 24
- 21
- 22
- 21
结果为4长64位
期望值:
我有 __m256i x 其中包含 8 个 32 位整数:
- 01101011111000011100000000000000
- 01110101011010010111100000000000
- 10100100011011000101010000000000
- 11101010100001001111000000000000
- 10010011111111001001010000000000
- 00011110101100101000000000000000
- 00011101011000111011000000000000
- 10011011100010100000110000000000
__m256i res = count(x);
资源包含:
- 11
- 13
- 10
- 11
- 12
- 9
- 11
- 10
结果是 8 int 32 位。
希望我说的很清楚,请不要犹豫向我询问更精确的信息。
谢谢。
AVX-512VPOPCNTDQ 具有 _mm256_popcnt_epi32
to popcount in 32-bit chunks, also a 64-bit chunk size version. Outside of Xeon Phi, it's new in Ice Lake,它还引入了 AVX512BITALG,它也具有 vpopcnt
.
使用 AVX2
您引用的原始代码依赖于 _mm256_sad_epu8
内在函数,它专门用于对 64 位字内的字节求和。
要使用 32 位字的总和获得相同的结果,您需要做一些稍微不同的事情。以下应该有效:
__m256i popcount_pshufb32(__m256i v) {
__m256i lookup = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2,
2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 1, 2, 2, 3,
1, 2, 2, 3, 2, 3, 3, 4);
__m256i low_mask = _mm256_set1_epi8(0x0f);
__m256i lo = _mm256_and_si256(v, low_mask);
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(v, 4), low_mask);
__m256i popcnt1 = _mm256_shuffle_epi8(lookup, lo);
__m256i popcnt2 = _mm256_shuffle_epi8(lookup, hi);
__m256i sum8 = _mm256_add_epi8(popcnt1, popcnt2);
return _mm256_srli_epi32(
_mm256_mullo_epi32(sum8, _mm256_set1_epi32(0x01010101)), 24);
// vpmulld is slowish (2 uops) on most recent Intel CPUs
// but still single-uop on AMD
}
所以我们用乘法和移位代替了_mm256_sad_epu8
。这应该是合理的。在我的测试中,it is slightly slower than the original 64-bit version, but the difference is relatively small.
通过使用不同的两条指令从字节累加到 32 位块,您可以以多一个向量常量为代价在 Intel 上获得稍微更好的性能。 AMD Zen1/2/3 至少与上面的版本一样有效。
32 位 SIMD 整数乘法在最近的 Intel CPU 上是 2 微指令(对于 SIMD 整数乘法单元),但是成对的乘法累加指令(8->16 和 16->32)是每个一个。 (https://uops.info/) 这需要多一个常量,但指令数量相同,以减少 uops,特别是如果编译器可以在循环中重用这些常量。
__m256i popcount_pshufb32(__m256i v) {
__m256i lookup = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2,
2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 1, 2, 2, 3,
1, 2, 2, 3, 2, 3, 3, 4);
__m256i low_mask = _mm256_set1_epi8(0x0f);
__m256i lo = _mm256_and_si256(v, low_mask);
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(v, 4), low_mask);
__m256i popcnt1 = _mm256_shuffle_epi8(lookup, lo);
__m256i popcnt2 = _mm256_shuffle_epi8(lookup, hi);
__m256i sum8 = _mm256_add_epi8(popcnt1, popcnt2);
return _mm256_madd_epi16(_mm256_maddubs_epi16(sum8, _mm256_set1_epi8(1)),
_mm256_set1_epi16(1));
}