为什么除法比其他算术运算复杂得多?

计算科学 计算机算术
2021-12-17 19:43:36

我最近遇到了一个案例,我需要在缺少整数除法运算的芯片(ARM Cortex-A8)上进行整数除法运算。在尝试研究为什么必须如此时,我发现在几乎任何整数(或定点)架构上,除法通常比加法、减法或乘法花费更多的周期。为什么会这样?它不能像其他所有东西一样用两层 AND-OR 逻辑来表示吗?

2个回答

除法是一种迭代算法,其中商的结果必须使用欧几里得度量转移到余数,请参见2而乘法可以简化为(固定的)一系列位操作技巧。

正如aterrel 所建议的那样,虽然当前所有 CPU 似乎都使用迭代方法,但在非迭代方法上已经完成了一些工作。可变精度浮点除法和平方根讨论了在FPGA中浮点除法和平方根的非迭代实现,使用查找表和泰勒级数展开。

我怀疑相同的技术可以使这些操作降低到一个周期(吞吐量,如果不是延迟),但您可能需要巨大的查找表,因此大面积的硅房地产是不可行的.

为什么不可行?

在设计 CPU 时,需要做出许多权衡。功能、复杂性(晶体管数量)、速度和功耗都是相互关联的,在设计过程中做出的决定会对性能产生巨大影响。

现代处理器可能一个主浮点单元,它在硅片上提供足够多的晶体管以在单个周期内执行浮点除法,但不太可能有效地使用这些晶体管。

十年前,浮点乘法实现了从迭代到非迭代的转变。如今,即使在移动处理器中,单周期乘法甚至乘法累加也很常见。

在它成为晶体管预算的有效使用之前,乘法和除法一样,通常是通过迭代方法执行的。那时,专用 DSP 处理器可能会将其大部分芯片专用于单个快速乘法累加 (MAC)单元。一个 Core2duo CPU 的浮点乘法延迟为 3(该值在它进入后 3 个周期从管道中出来),但一次可以进行 3 个乘法运算,从而产生单周期吞吐量,同时它的 SSE2 单元可以在一个周期内抽出多个 FP 乘法。

现代 CPU 不是将大面积的硅片专用于一个单周期除法单元,而是具有多个单元,每个单元都可以并行执行操作,但针对自己的特定情况进行了优化。事实上,一旦你考虑到SIMD指令,如SSESandy Bridge或更高版本 CPU 的 CPU集成显卡,你的CPU 上可能会有很多这样的浮点除法单元。

如果通用浮点除法对现代 CPU 更重要,那么将足够的硅面积用于使其成为单周期可能是有意义的,但是大多数芯片制造商显然已经决定他们可以通过将这些门用于其他事情来更好地利用该硅. 因此,一项操作速度较慢,但​​总体而言(对于典型的使用场景),CPU 速度更快和/或功耗更低。