快速硬件整数除法

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 uop，最坏情况延迟为 26 个周期，但吞吐量为 6 个周期。（https://uops.info/和https://agner.org/optimize/，并且Trial-division 代码在 Windows 上的 32 位运行速度比在 Linux 上的 64 位运行速度快 2 倍，有详细的探索。）

除法单元的构建方式没有发生根本性变化，只是扩大了硬件除法器以不需要扩展精度微代码。（英特尔为 FP 提供快速除法器的时间要长得多，这基本上是同样的问题，只是只有 53 位而不是 64 位。 FP 除法的困难部分是尾数的整数除法；减去指数很容易，可以在平行线。）

增量变化是指扩大基数以在每一步处理更多位。例如，在初始（表查找？）值之后对细化步骤进行管道化，以提高吞吐量而不是延迟。

有关的：

• GCC的sqrt()编译后如何工作？使用哪种root方法？牛顿-拉夫森？现代 CPU 使用的 div/sqrt 单元的简要高级概述，例如 Broadwell 中新增的 Radix-1024 除法器。

• FP 和整数除法在 x86 CPU 上争夺相同的吞吐量资源吗？（在 Ice Lake 和后来的 Intel 中没有；使用专用整数单元而不是使用 FP 尾数除法/平方单元的低位元素可能与使其成为 64 位宽有关。）

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

但随着更宽的 CPU 管道和更高的 IPC 缩小了各部门之间的周期差距，这更值得做。此外，由于晶体管预算巨大，如果对某些程序非常有帮助，那么在大多数程序中花费大量时间闲置的东西仍然是有意义的。pdep（例如更广泛的 SIMD，以及 x86 BMI2 /等专用执行单元pext）。 必须使用暗硅，否则芯片会熔化；功率密度是一个巨大的问题，请参阅现代微处理器：90 分钟指南！

此外，越来越多的软件是由对性能一无所知的人编写的，并且越来越多的代码避免编译时常量以支持灵活性（最终来自某些配置选项的函数参数），我猜现代软件不像旧程序那样避免分裂。

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

因此，FP 动机很可能是英特尔改进除法吞吐量和延迟背后的实际驱动力，尽管他们在 Ice Lake 之前将 64 位整数除法留下了垃圾性能。