SIMD版本的SHLD/SHRD指令

Question

SHLD/SHRD指令是用于实现多精度移位的汇编指令.

请考虑以下问题:

uint64_t array[4] = {/*something*/};
left_shift(array, 172);
right_shift(array, 172);

什么是实行最有效的方法left_shift和right_shift,经营4个64位无符号整数数组上的转变,就好像它是一个巨大的256位无符号整数两种功能？

最有效的方法是使用SHLD/SHRD指令,还是有更好的(如SIMD版本)现代架构指令？

Answer 1

在这个答案中,我只想谈谈x64.
x86已经过时了15年,如果你在2016年进行编码,那么在2000年陷入困境几乎没有意义.
所有时间都是根据Agner Fog的指令表.

英特尔Skylake示例时序* x64上
的shld/ shrd指令相当慢.
即使在英特尔Skylake上,它们也有4个周期的延迟并且使用4个uop意味着它占用了大量的执行单元,在较旧的处理器上它们甚至更慢.
我假设你想要换一个可变数量,这意味着一个

SHLD RAX,RDX,cl        4 uops, 4 cycle latency.  -> 1/16 per bit

使用2班+添加你可以做到这一点 快点 慢点.

@Init:
MOV R15,-1
SHR R15,cl    //mask for later use.    
@Work:
SHL RAX,cl        3 uops, 2 cycle latency
ROL RDX,cl        3 uops, 2 cycle latency
AND RDX,R15       1 uops, 0.25 latency
OR RAX,RDX        1 uops, 0.25 latency    
//Still needs unrolling to achieve least amount of slowness.

请注意,这只会移位64位,因为RDX不受影响.
所以你试图每64位击败4个周期.

//4*64 bits parallel shift.  
//Shifts in zeros.
VPSLLVQ YMM2, YMM2, YMM3    1uop, 0.5 cycle latency.  

但是,如果您希望它完全与SHLD一样,您需要使用额外的VPSLRVQ和OR来组合这两个结果.

VPSLLVQ YMM1, YMM2, YMM3    1uop, 0.5 cycle latency.  
VPSRLVQ YMM5, YMM2, YMM4    1uop, 0.5 cycle latency.   
VPOR    YMM1, YMM1, YMM5    1uop, 0.33 cycle latency.   

您将需要交错4套这些成本(3*4)+ 2 = 14 YMM寄存器.
这样做我怀疑你会从VPADDQ的低.33延迟中获利,所以我假设延迟为0.5.
这使得3uops,256位的1.5周期延迟=每位1/171 =每QWord 0.37个周期=快10倍,不错.
如果每个256位能够获得1.33个周期=每位1/192 =每QWord 0.33个周期= 12倍速.

"这是记忆,愚蠢!"
显然我没有添加循环开销和加载/存储到内存.
在跳跃目标正确对齐的情况下,循环开销很小,但内存
访问很容易成为最大的减速.
Skylake主内存的单个缓存未命中可能会花费超过250个周期¹.
巧妙的记忆管理将取得重大进展.
相比之下,使用AVX256进行12次加速可能是小马铃薯.

我不计算CL/ 中的移位计数器的设置,(YMM3/YMM4)因为我假设你将在多次迭代中重用该值.

你不会用AVX512指令击败它,因为带有AVX512指令的消费级CPU尚不可用.
目前唯一支持的处理器是Knights Landing.

*)所有这些时间都是最佳案例值,应作为指示,而不是硬值.
¹)Skylake的高速缓存未命中成本:42个周期+ 52ns = 42 +(52*4.6Ghz)= 281个周期.