现代X86处理器如何计算乘法？

Question

我正在观看一些算法讲座，教授以乘法为例说明了如何改进天真的算法... 这让我意识到乘法并不是那么显而易见，尽管在编码时，我只把它视为一个简单的原子操作，但乘法需要一个算法来运行，它不能像加法那样工作。所以我想知道，现代台式机处理器实际上使用的是什么算法？我想它们不依赖对数表，也不会进行数千次循环的累加操作...

- speeder

---

请参阅：https://zh.wikipedia.org/wiki/%E4%BA%8C%E8%BF%9B%E5%88%B6%E4%B9%98%E6%B3%95 + https://zh.wikipedia.org/wiki/Wallace%E6%A0%91 + https://zh.wikipedia.org/wiki/Dadda%E4%B9%98%E6%B3%95 - Paul R

你需要指定“整数”或“浮点数”，可能还需要指定CPU。请注意，对于浮点数，指数是相加的，而有效数字是相乘的，并且有效数字大多在1.0到1.9999 *的范围内，这使它们“更适合”于不适用于整数的方法。 - Brendan

你需要挑选一款特定的CPU并查看它的完整数据手册（我指的是10兆字节或更大的PDF文档）。它们有时会提到这样的东西。但要确切知道，你需要询问CPU的开发/制造商或检查其芯片（http://www.righto.com/2013/09/the-z-80-has-4-bit-alu-heres-how-it.html），Visual6502包含了许多芯片的拍摄，选择其中一个……较旧的整数乘法器使用移位加法乘法，现在谁知道（LUTs、近似值、Karatsuba……） - Spektre

如果你是指FP（浮点数）的话：很多FP乘法器都是整数尾数乘法器。加上指数很容易，只需假设输入和结果已经规范化，重新调整尾数结果所需的仅是额外的0或1偏移量。 - Peter Cordes

ALU的内部设计可以成为CPU快速和节能的秘密武器的一部分。这对于CPU架构师来说很有趣，但对于软件甚至是低级别的汇编手动调优来说完全无关紧要。重要的是性能：延迟和吞吐量。话虽如此，就硬件设计而言，它是一个编程问题，但它询问的是现有设计是如何完成的。 - Peter Cordes

Answer 1

Mitch Alsup（曾在Motorola 88K、Ross SPARC、AMD x86等领域工作）在comp.arch新闻组中表示：

所有现代乘法器设计师都使用Dadda方法构建树形结构。

（Message-ID: <[e-mail]> — 2018年12月14日）

并且（关于AMD/Intel/NVIDIA使用的最近参考文献的可用性）：

仅在专利局中。

（Message-ID: <[e-mail]> — 2020年1月14日）

请参阅维基百科，了解 Dadda树乘法器的相关信息。

- user2467198

---

（时间范围：处理器设计是20世纪90年代的，Alsup先生是千年之交Athlon K9的首席架构师，并于2015年左右退休。这些消息来自2018年12月和2020年1月。） - greybeard

Answer 2

有各种乘法程序可在 CPU 中使用，例如，在大多数计算机架构/组织课程中教授的 2 的补码二进制数字的 Booth 乘法器。在二进制中进行乘法比在十进制表示中更简单。计算部分积很简单。被乘数 M（如果乘数位是 1）或 0（如果乘数位是 0）。与十进制相比，它可以是任何介于（0*M 到 9*M）之间的东西。每当有人设计自定义 CPU（如 FPGA 上的软核）时，开发人员可以选择适当的乘法程序。一些常用的是CORDIC乘法器、Radix-2、Radix-4、Radix-8... Booth乘法器。所有这些乘法器算法都会产生部分积（就像手动乘法一样）。将所有部分积相加即可得到最终积。现代处理器有多种方法来完成这个过程，例如使用 Dadda 乘法器、Wallace 树等。

简而言之，每个处理器设计者都可以使用任何乘法器算法来生成部分积，并添加部分积以获得最终结果。根据处理器寄存器内部使用的二进制表示、寄存器位大小，最优算法将有所不同。

- ajit

---

（我猜在保罗·A·克莱顿回答之前，加速器很清楚上述内容。而真正的问题是：“通用处理器目前使用哪些乘法器？”这是一个动态变化的目标。阿尔斯普先生建议检查专利申请和（侵权）挑战以及授权可能是你了解情况的最佳途径。） - greybeard

我详细阐述了Speeder所提到的“我猜他们不依赖对数表，也不会用成千上万个求和循环……”。我的回答解释说，它不会是“成千上万个求和”，只有N个或更少的部分积将被添加到N位操作数/寄存器中。如果使用CORDIC实现，则像Billy Bob建议的LUT就会发挥作用。 - ajit

一个快速的谷歌搜索找到了https://www.dsprelated.com/thread/3151/details-of-a-cordic-multiplier，其中链接了[A survey of CORDIC algorithms for FPGA based computers](http://www.andraka.com/files/crdcsrvy.pdf)。+1，这个答案确实比只说所有东西最终都使用Dadda树更详细。 - Peter Cordes

Answer 3

现代处理器具有内置数学协处理器。我相信它们包含用于乘法的查找表（LUT）。

- Billy_Bob

---

有人能否确认一下这个人刚才写的内容是正确的还是错误的？ - speeder

@speeder，由于您没有指定CPU和操作系统，所以没有高声望用户回答您的问题。因为没有明确规定，您的问题是无法回答的。 - Spektre