SHLD/SHRD 指令的 SIMD 版本

Question

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

考虑以下问题：

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

实现

left_shift

和

right_shift

这两个函数的最有效方法是什么，这两个函数对四个 64 位无符号整数数组进行移位操作，就好像它是一个大的 256 位无符号整数一样？

最有效的方法是使用 SHLD/SHRD 指令，还是现代架构上有更好的（如 SIMD 版本）指令？

Answer 1

在这个答案中我只讨论 x64。
x86 已经过时了 15 年，如果你在 2016 年编码，那么停留在 2000 年几乎没有意义。
所有时间均根据Agner Fog 的说明表。

Intel Skylake 示例时序*

shld

/

shrd

指令在 x64 上相当慢。
即使在 Intel skylake 上，它们也有 4 个周期的延迟并使用 4 个 uops，这意味着它使用了大量的执行单元，在较旧的处理器上它们甚至更慢。
我假设你想移动一个可变的量，这意味着a

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 寄存器。
这样做我怀疑您是否会从 VPOR 0.33 的低延迟中获益，因此我将假设 0.5 的延迟。
这使得 3uops、256 位的 1.5 个周期延迟 = 1/171 每位 = 0.37 个周期每 QWord = 快 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 + (524.6Ghz) = 281 个周期。