是否有任何有效的算法(或处理器指令)可以帮助将数字(32位和64位)划分为几个数字,其中只有一个1位。
我想将每个集合位隔离为一个数字。例如,
输入:01100100
输出:
01000000
00100000
00000100
只想到number & mask
。组件或С++。
是的,与Brian Kernighan的计算集位的算法类似,只是我们提取的位不是计数,而是在每个中间结果中使用最低的集位:
while (number) {
// extract lowest set bit in number
uint64_t m = number & -number;
/// use m
...
// remove lowest set bit from number
number &= number - 1;
}
在现代x64程序集中,number & -number
可以编译为blsi
,number &= number - 1
可以编译为blsr
,这两者都很快,因此这只需要几个有效的指令即可实现。
由于m
可用,可以用number ^= m
重置最低设置位,但这可能会使编译器更难看到它可以使用blsr
,这是一个更好的选择,因为它只直接依赖于number
,因此缩短了循环携带的依赖链。
标准方式是
while (num) {
unsigned mask = num ^ (num & (num-1)); // This will have just one bit set
...
num ^= mask;
}
例如,从num = 2019
开始,您将获得有序的
1
2
32
64
128
256
512
1024
如果要一次迭代一个单比特隔离掩码,则一次生成一个掩码是有效的;看看@harold的回答
但如果你真的只想要所有的掩码,x86与AVX512F可以有效地并行化(至少根据周围的代码可能有用。更可能的是,这只是应用AVX512的一个有趣练习,对大多数用例都没有用处)。
关键构建块是AVX512Fvpcompressd
:给定掩码(例如,来自SIMD比较),它将把所选的双字元素混洗到向量底部的连续元素。
AVX512 ZMM/__m512i
向量包含16x 32位整数,因此我们只需要2个向量来保存每个可能的单比特掩码我们的输入编号是一个掩码,用于选择这些元素中的哪一个应该是输出的一部分(不需要将它广播到向量和vptestmd
或类似的东西中;我们可以将它kmov
广播到掩码寄存器中并直接使用它。)
另请参阅我在AVX2上的AVX512答案,什么是最有效的基于口罩的包装方式?
#include <stdint.h>
#include <immintrin.h>
// suggest 64-byte alignment for out_array
// returns count of set bits = length stored
unsigned bit_isolate_avx512(uint32_t out_array[32], uint32_t x)
{
const __m512i bitmasks_lo = _mm512_set_epi32(
1UL << 15, 1UL << 14, 1UL << 13, 1UL << 12,
1UL << 11, 1UL << 10, 1UL << 9, 1UL << 8,
1UL << 7, 1UL << 6, 1UL << 5, 1UL << 4,
1UL << 3, 1UL << 2, 1UL << 1, 1UL << 0
);
const __m512i bitmasks_hi = _mm512_slli_epi32(bitmasks_lo, 16); // compilers actually do constprop and load another 64-byte constant, but this is more readable in the source.
__mmask16 set_lo = x;
__mmask16 set_hi = x>>16;
int count_lo = _mm_popcnt_u32(set_lo); // doesn't actually cost a kmov, __mask16 is really just uint16_t
_mm512_mask_compressstoreu_epi32(out_array, set_lo, bitmasks_lo);
_mm512_mask_compressstoreu_epi32(out_array+count_lo, set_hi, bitmasks_hi);
return _mm_popcnt_u32(x);
}
在Godbolt上使用clang和gcc进行了很好的编译,而不是使用mov、movzx和popcnt进行一些次要的次优选择,并无故生成帧指针。(它也可以使用-march=knl
编译;它不依赖于AVX512BW或DQ。)
# clang9.0 -O3 -march=skylake-avx512
bit_isolate_avx512(unsigned int*, unsigned int):
movzx ecx, si
popcnt eax, esi
shr esi, 16
popcnt edx, ecx
kmovd k1, ecx
vmovdqa64 zmm0, zmmword ptr [rip + .LCPI0_0] # zmm0 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768]
vpcompressd zmmword ptr [rdi] {k1}, zmm0
kmovd k1, esi
vmovdqa64 zmm0, zmmword ptr [rip + .LCPI0_1] # zmm0 = [65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648]
vpcompressd zmmword ptr [rdi + 4*rdx] {k1}, zmm0
vzeroupper
ret
在Skylake-VX512上,vpcompressd zmm{k1}, zmm
对于端口5是2个uops。输入向量->输出的延迟为3个周期,但输入掩码->输出的等待时间为6个周期。(https://www.uops.info/table.html/https://www.uops.info/html-instr/VPCOMPRESSD_ZMM_K_ZMM.html)。内存目标版本是4个uop:2p5+通常的存储地址和存储数据uops,当它是较大指令的一部分时,无法进行微融合。
最好压缩到ZMM reg中,然后存储(至少在第一次压缩时),以节省总uop。第二个可能仍然应该利用vpcompressd [mem]{k1}
的屏蔽存储功能,这样输出数组就不需要填充来进行操作。IDK如果这有助于缓存行拆分,即屏蔽是否可以避免为第二个缓存行中具有全零屏蔽的部分重播存储uop。
在KNL上,vpcompressd zmm{k1}
只是单个uop。Agner Fog没有用内存目的地测试它(https://agner.org/optimize/)。
这是Skylake-X上前端的14个融合域uop,用于实际工作(例如,在通过多个x
值内联到循环中之后,因此我们可以将vmovdqa64
负载从循环中提升出来。否则,这是另外2个uop)。因此前端瓶颈=14/4=3.5个周期
后端端口压力:端口5为6 uops(2x kmov(1)+2x vpcompressd(2)):每6个循环1次迭代。(不幸的是,即使在IceLake(instlatx64)上,vpcompressd
的吞吐量仍然是2c,所以显然ICL的额外shuffle端口无法处理这两个uop。并且kmovw k, r32
仍然是1/时钟,所以推测仍然是端口5。)
(其他端口也可以:popcnt在端口1上运行,当512位uop运行时,该端口的矢量ALU会关闭。但不是它的标量ALU,它是唯一一个处理3周期延迟整数指令的ALU。movzx dword, word
无法消除,只有movzx dword,byte可以做到这一点,但它在任何端口上运行。)
延迟:整数结果仅为一个popcnt
(3个周期)。存储器结果的第一部分在掩模准备好之后大约7个周期被存储。(kmov->vpcompressd)。vpcompressd的矢量源是一个常量,因此OoO exec可以提前做好准备,除非它在缓存中未命中。
压缩1<<0..15
常数是可能的,但可能不值得,通过移位来构建它。例如,用vpmovzxbd
加载16字节的_mm_setr_epi8(0..15)
,然后将其与vpsllvd
一起用于set1(1)的向量(您可以从广播中获得或使用vpternlogd
+移位动态生成)。但是,即使你在asm中手工编写,这可能也不值得(所以这是你的选择,而不是编译器),因为这已经使用了大量的shuffle,并且持续生成至少需要3或4条指令(每条指令至少有6个字节长;仅EVEX前缀就有4个字节长)。
不过,我会从lo
转换生成hi
部分,而不是单独加载。除非周围的代码在端口0上出现严重瓶颈,否则ALU uop并不比加载uop差。一个64字节的常量将填充整个缓存行。
您可以使用vpmovzxwd
加载来压缩lo常数:每个元素适合16位。值得考虑的是,如果你能把它举到循环之外,这样每次操作就不会花费额外的洗牌时间。
如果您想将结果存储在SIMD矢量中,而不是存储到内存中,您可以将vpcompressd
乘以寄存器,并可能使用count_lo
查找vpermt2d
的混洗控制矢量。可能来自数组上的滑动窗口,而不是16x 64字节的矢量?但是,除非你知道你的输入设置了16位或更少的位,否则不能保证结果适合一个向量。
64位整数的情况要糟糕得多8x 64位元素意味着我们需要8个向量。因此,与标量相比,这可能不值得,除非你的输入设置了很多位。
不过,您可以在循环中使用vpslld
乘以8来移动矢量元素中的位。你可能认为kshiftrq
会很好,但由于有4个周期的延迟,这是一个长循环携带的dep链。无论如何,您都需要每个8位块的标量popcnt来调整指针。因此,您的循环应该使用shr
/kmov
和movzx
/popcnt
。(使用计数器+=8和bzhi
来馈送popcnt将花费更多的uops)。
循环携带的依赖关系都很短(并且循环只运行8次迭代来覆盖掩码64位),因此无序的exec应该能够很好地重叠多次迭代的工作。特别是如果我们按2展开,那么向量和掩码依赖关系可以提前于指针更新。
- 矢量:
vpslld
立即数,从矢量常数开始 - 掩码:从
x
开始的shr r64, 8
。(在移出所有位后,当它变为0时,可能会停止循环。这个1周期的dep链足够短,OoO exec可以快速通过它,并在发生错误预测时隐藏大部分惩罚。) - 指针:
lea rdi, [rdi + rax*4]
,其中RAX保存popcnt结果
其余的工作在迭代中都是独立的。根据周围的代码,我们可能会在端口5上使用vpcompressd
混洗和kmov