整数除法的硬件指令历来非常慢。例如,对于 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
最佳答案
在 Ice Lake 之前的 Intel 上,64 位操作数大小是一个异常值,整数除法比 32 位操作数大小慢得多。 div r32
为 10 微指令,最坏情况下延迟为 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 位宽有关。)
过去,除法单元通常根本没有流水线,因为这很难,因为我认为它需要复制大量门而不是在相同的乘法器上迭代。而且大多数软件通常会避免(或避免)整数除法,因为它在历史上非常昂贵,至少这样做的频率不够高,不会从具有相同延迟的更高吞吐量除法器中获益太多。
但是随着具有更高 IPC 的更宽 CPU 流水线缩小了部门之间的周期差距,这更值得做。此外,由于晶体管预算巨大,如果对一些程序非常有用,那么在大多数程序中花很多时间闲置的东西仍然是有意义的。 (比如更宽的 SIMD,以及像 x86 BMI2 pdep
/pext
这样的专用执行单元)。 Dark silicon是必要的,否则切屑会熔化;功率密度是一个巨大的问题,参见 Modern Microprocessors: A 90-Minute Guide!
此外,越来越多的软件是由对性能一无所知的人编写的,并且越来越多的代码避免编译时常量以支持灵 active (最终来自某些配置选项的函数参数),我会我猜现代软件不像旧程序那样避免除法。
浮点除法通常比整数更难避免,因此绝对值得拥有快速 FP 除法器。如果没有专用的整数除法单元,整数可以从低 SIMD 元素中借用尾数除法器。
因此,FP 动机可能是英特尔改进吞吐量和延迟划分的实际驱动力,尽管他们在 Ice Lake 之前留下了垃圾性能的 64 位整数除法。
关于performance - 快速硬件整数除法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/70132913/