快速硬件整数除法

人气:340 发布:2022-10-16 标签: performance x86 cpu-architecture arm integer-division

问题描述

用于整数除法的硬件指令在历史上一直非常慢。例如,对于64位输入,Skylake上的DIVQ延迟为42-95个周期[1](倒数吞吐量为24-90)。

不过,也有性能更好的较新处理器:Goldmont有14-43个延迟,而Ryzen有14-47个延迟[1],M1的吞吐量显然是每个分频2个时钟周期[2],甚至Raspberry Pico也有每个内核的8周期带符号/无符号分频/模数电路(尽管这似乎是针对32位输入)[3]。

我的问题是,什么发生了变化?有没有发明一种新的算法?不管怎样,新处理器采用了什么除法算法?

[1]https://www.agner.org/optimize/#manuals [2]https://ridiculousfish.com/blog/posts/benchmarking-libdivide-m1-avx512.html [3]https://raspberrypi.github.io/pico-sdk-doxygen/group__hardware__divider.html#details

推荐答案

在冰湖之前的英特尔上,64位操作数大小是一个异常值,比用于整数除法的32位操作数大小要慢得多。div r32为10个uop,最坏情况延迟为26个周期,吞吐量为6个周期。(https://uops.info/和https://agner.org/optimize/和Trial-division code runs 2x faster as 32-bit on Windows than 64-bit on Linux有详细介绍。)

除法单元的构建方式没有根本改变,只是扩大了硬件分割器,不再需要扩展精度的微码。(英特尔拥有fast-ish dividers for FP的时间要长得多,这基本上也是同样的问题,只是只有53位而不是64位。Fp除法的难点是尾数的整数除法;指数的减法很容易,而且是并行完成的。)

增量更改类似于扩大基数以在每一步中处理更多位。例如,在初始(表查找?)之后对细化步骤进行流水线处理值,以提高吞吐量而不是延迟。

相关:

How sqrt() of GCC works after compiled? Which method of root is used? Newton-Raphson?简要概述现代CPU使用的div/SQRT单元,例如Broadwell中新增的Radix-1024除法器。

Do FP and integer division compete for the same throughput resources on x86 CPUs?(在Ice Lake和后来的Intel中不是;使用专用的整数单元而不是使用Fp尾数除法/SQRT单元的低元素可能与使其64位宽有关。)

除法单元在历史上通常根本不是流水线的,因为我认为这很困难,因为它需要复制许多门,而不是在相同的乘法器上迭代。大多数软件通常避免(或避免)整数除法,因为在历史上是非常昂贵的,至少它不够频繁,不会从具有相同延迟的更高吞吐量的除法器中获益很多。

但随着更宽的CPU管道和更高的IPC缩小了部门之间的周期差距,这更值得一做。此外,由于晶体管预算巨大,在大多数程序中花费大量时间闲置的东西仍然是有意义的,如果它对少数程序非常有帮助的话。(像更宽的SIMD,以及像x86BMI2pdep/pext这样的专用执行单元)。Dark silicon是必需的,否则芯片会融化;功率密度是一个巨大的问题,请参阅Modern Microprocessors: A 90-Minute Guide!

此外,越来越多的软件是由对性能一无所知的人编写的,越来越多的代码避免编译时常量以支持灵活性(最终来自某个配置选项的函数参数),我猜现代软件不像旧程序那样避免除法。

浮点除法通常比整数除法更难避免,因此使用快速FP除法器绝对值得。如果没有专用的整数除法单元,INTEGER可以从低SIMD元素借用尾数除法器。

因此,FP动机可能是英特尔改进吞吐量和延迟划分的实际驱动力,尽管它们将具有垃圾性能的64位整数除法留给了Ice Lake。

526