performance - 快速硬件整数除法

Question

整数除法的硬件指令历来非常慢。例如，对于 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

Answer 1

在 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 位整数除法。