c - 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's instruction tables .

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

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。
这使得 256 位的 3 微秒、1.5 个周期延迟 = 每位 1/171 = 每个 QWord 0.37 个周期 = 快 10 倍，不错。
如果您能够获得每 256 位 1.33 个周期 = 每位 1/192 = 每个 QWord 0.33 个周期 = 快 12 倍。

'It’s the Memory, Stupid!'
显然我没有添加循环开销和加载/存储到/从内存。
考虑到跳转目标的正确对齐，循环开销很小，但是内存
访问很容易成为最大的减速。
Skylake 上主内存的一次缓存未命中可能会让您付出代价 more than 250 cycles¹ .
正是在巧妙地管理内存中，才能取得重大进展。
相比之下，使用 AVX256 的 12 倍加速可能是小菜一碟。

我没有计算 CL 中类次计数器的设置。/(YMM3/YMM4)因为我假设您将在多次迭代中重用该值。

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

*) 所有这些时间都是最佳情况下的值，应被视为指示，而不是硬性值。
¹) Skylake 中缓存未命中的成本:42 个周期 + 52ns = 42 + (52*4.6Ghz) = 281 个周期。