电器工程 - 为什么硬件除法比乘法花费更长的时间？ - 吾爱随笔录

为什么硬件除法比乘法花费更长的时间？

电器工程微控制器硬件数学算法算术除法

2022-01-06 05:44:01

为什么硬件除法比微控制器上的乘法需要更长的时间？例如，在 dsPIC 上，除法需要 19 个周期，而乘法只需要一个时钟周期。

我浏览了一些教程，包括维基百科上的除法算法和乘法算法。这是我的推理。

除法算法，就像维基百科上的慢除法一样，是一种递归算法。这意味着 step 的（中间）结果k用作 step 的输入k+1，这意味着这些算法不能并行化。n因此，完成除法至少需要几个周期，而n被除数中的位数是多少。对于 16 位除数，这至少等于 16 个周期。

乘法算法不需要是递归的，这意味着可以并行化它。但是，有许多不同的乘法算法，我不知道微控制器可以使用哪一种。乘法如何在硬件/微控制器上工作？

我找到了一个Dadda 乘法器算法，它应该只需要一个时钟周期即可完成。但是，我在这里没有得到的是 Dadda 的算法分三个步骤进行，而步骤 1 的结果用于步骤 2，依此类推。据此，这至少需要三个时钟周期才能完成。

4个回答

分隔器映射到典型硬件的优雅程度要低得多。以 Lattice ICE40 FPGA 为例。

让我们比较两种情况：这个 8x8 位到 16 位乘法器：

module multiply (clk, a, b, result);
   input clk;
   input [7:0]a;
   input [7:0]b;
   output [15:0]result;
   always @(posedge clk)
     result = a * b;
endmodule // multiply

这个除法器将 8 位和 8 位操作数减少为 8 位结果：

module divide(clk, a, b, result);
   input clk;
   input [7:0] a;
   input [7:0] b;
   output [7:0] result;
   always @(posedge clk)
     result = a / b;
endmodule // divide

（是的，我知道，时钟不做任何事情）

将乘法器映射到 ICE40 FPGA 时生成的原理图概览可在此处找到，除法器可 在此处找到。

Yosys 的综合统计数据为：

乘

电线数量：155
线位数：214
公共线数：4
公线位数：33
记忆数：0
内存位数：0
进程数：0
细胞数量：191
- SB_CARRY 10
- SB_DFF 16
- SB_LUT4 165

划分

电线数量：145
线位数：320
公共线数：4
公线位数：25
记忆数：0
内存位数：0
进程数：0
细胞数量：219
- SB_CARRY 85
- SB_DFF 8
- SB_LUT4 126

值得注意的是，为全宽乘法器和最大除法器生成的 verilog 的大小并不是那么极端。但是，如果您查看下面的图片，您会注意到乘数的深度可能为 15，而分隔符看起来更像是 50 左右；关键路径（即运行期间可能出现的最长路径）是速度的定义！

无论如何，您将无法阅读此内容以获得视觉印象。我认为复杂性的差异是可以发现的。这些是单周期乘法器/除法器！

乘

在 ICE40 上相乘（警告：~100 Mpixel 图像）

划分

（在 ICE40 上划分）（警告：~100 Mpixel 图像）

每个时钟周期我们可以有多个逻辑层，但是有一个限制，我们可以拥有多少层逻辑以及这些层的复杂程度取决于我们的时钟速度和我们的半导体工艺。

但是，有许多不同的乘法算法，我不知道微控制器可以使用哪一种

计算机中的大多数乘法使用二进制长乘法的变体。二进制长乘法涉及

将一个操作数移位各种不同的数量
根据第二个操作数屏蔽移位的数字
将掩蔽的结果加在一起。

因此，让我们看一下在硬件中实现这一点。

换档只是我们如何连接的问题，所以它是免费的。
屏蔽需要与门。这意味着一层逻辑，所以从时间的角度来看它很便宜。
由于需要携带链，因此添加相对昂贵。幸运的是，我们可以使用一个技巧。对于大多数加法阶段，我们可以添加三个数字来产生两个，而不是添加两个数字来产生一个。

因此，让我们大致了解一下 8x8 乘法器需要多少个逻辑级才能得到 16 位结果。为简单起见，假设我们不尝试优化并非所有中间结果在所有位置都有位的事实。

让我们假设一个全加器在两个“门级”中实现。

1 用于掩蔽以产生 8 个中间结果。
2 添加三个数字为一组，将 8 个中间结果减少到 6 个
2 添加三个数字为一组，将 6 个中间结果减少到 4 个
2 将一组三个数字相加，将4个中间结果减少到3个
2 将一组三个数字相加，将3个中间结果减少到2个
32 将最后两个结果相加。

所以总共大约有 41 个逻辑级。其中大部分用于将最后两个中间结果相加。

这可以通过利用并非所有中间结果都存在所有位的事实来进一步改进（这基本上是dada乘法器所做的），通过在最后一步使用进位超前加法器。通过添加 7 个数字来产生 3 而不是 3 产生两个（以更多的门和更宽的门为代价减少阶段的数量）等等。

不过，这都是次要的细节，重要的是，将两个 n 位数字相乘并产生 2n 位结果所需的阶段数大致与 n 成正比。

另一方面，如果我们查看除法算法，我们会发现它们都有一个迭代过程。

一次迭代所做的工作很大程度上取决于前一次迭代的结果。
实现一次迭代所需的逻辑级数大致与 n 成正比（减法和比较在复杂性上与加法非常相似）
迭代次数也大致与 n 成正比。

所以实现除法所需的逻辑级数大致与n的平方成正比。

慢除法本质上是迭代的，因此往往需要更长的时间。使用查找表有比简单算法更快的慢速除法算法。SRT 算法每个周期产生两位。此类表中的错误是臭名昭著的Pentium FDIV 错误（约 1994 年）的原因。然后是所谓的快速除法算法。

当然，原则上，您可以简单地使用一个巨大的查找表来计算两个数字的乘积或商，从而在一个周期内得到结果，但是随着每个数字的位数增加，这往往会很快变得不切实际。

实际的除法算法都是基于收敛到商的数值套件。

有一些加法方法，如非恢复或 SRT，它通过将 2^N 添加或删除到商并相应地将 2^N * 除数添加或删除到部分余数，直到它收敛到零。
有乘法方法，如 Newton-Raphson 或 Goldshmidth，它们是求根方法，其中除法计算为乘法的倒数。

加法方法每个周期给出一个或几个位。乘法方法将每个周期的位数加倍，但需要一些初始近似值，通常通过常数表获得。

“慢”和“快”的名称具有误导性，因为实际速度取决于位数，用于该功能的硬件数量（并且快速乘法器非常大）......

除法比乘法慢，因为没有直接的并行计算方法：要么存在迭代，要么复制硬件以将迭代实现为级联（或流水线）块。

其它你可能感兴趣的问题