快速硬件整数除法

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

分频单元的构建方式没有根本的改变，只是将硬件分频器扩展到不需要扩展精度微码。（英特尔为FP提供快速除法器的时间要长得多，这基本上是相同的问题，只需要53位而不是64位。FP除法的困难部分是尾数的整数除法；减去指数很容易，而且是并行的。）

增量更改是诸如扩大基数以在每个步骤中处理更多位之类的事情。例如，在初始（表查找？）值之后流水线化细化步骤，以提高吞吐量而不是延迟。

相关:

> GCC的sqrt()编译后如何工作？用的是哪种根的方法？牛顿-拉夫森？简要概述现代CPU使用的div/sqrt单元，例如Broadwell中新出现的Radix-1024分频器。

FP 和整数除法是否会在 x86 CPU 上争用相同的吞吐量资源？（在Ice Lake和后来的英特尔中没有，使用专用的整数单元而不是使用FP尾数除法/sqrt单元的低元素可能与使其宽度为64位有关。

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

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

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

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

因此，FP动机很可能是Intel改进吞吐量和延迟划分的实际驱动力，尽管他们在冰湖之前留下了64位整数划分和垃圾性能。