【计算机组成 课程笔记】4.2 除法器的硬件实现_硬件除法器

 课程链接：

计算机组成_北京大学_中国大学MOOC(慕课)

4 - 5 - 405-除法的运算过程（09-'43--）_哔哩哔哩_bilibili

在加减乘除这样的基本算数运算中，除法是最为复杂的，因此我们想要实现硬件的除法器，还是从最简单的情况开始说起。

1. 除法的运算过程

回想一下手算除法的过程。这里是两个由0和1组成的被除数和除数。首先将除数和被除数从高位开始对齐，将对齐的部分进行减法，当我们发现减完的结果是一个正数，也就是够减的时候，我们就在商的对应位标一个1，然后把减完的差放在下面。再从被除数后面的位中拿一位下来（10），继续判断是否够减。我们发现在这个例子中它不够减，于是我们在商的对应位标一个0。再多拿一位也还不够（101），所以再标1个0。然后再拿一位下来（1010），够减了，于是标1，然后把减完的差放在下面，减完的结果已经没有多余的被除数位可以拿下来了，所以这个数就是余数。

我们仔细观察上面的运算过程，其实中间忽略了一些步骤，完整的运算相当于是把除数每次右移1位，与被除数的对应位数进行比较，如果被除数大，则商为1，如果除数大，则商为0，被除数减掉除数以后剩下的就是当前轮次的余数。而商是从最高位开始计算，直到最低位，这也可以看成是一个左移的操作。

好，我们整理一个除法器的工作流程。以32位除法器为例：

2. 除法器的硬件实现

为了简便起见，我们以4位的除法器来进行说明。一个4位的除法器，需要1个8位的余数寄存器，需要1个8位的除数寄存器，且带右移功能，还需要一个4位的商寄存器，且带左移的功能。最后需要1个8位的ALU，支持加法和减法的运算。这里需要支持加法运算，主要是因为2b中有一个回退的操作。最后还需要1个控制逻辑控制这几个寄存器和ALU的工作。

现在我们就有了一个完整的除法器，我们就来看一下这个除法器是如何工作的。

0. 初始化

初始化各个寄存器，将8位的被除数放入余数寄存器；将4位的除数放入除数寄存器的高4位，并将低4位补上0；将4位的商寄存器置为0。

1. 减法运算

初始化后正式进入计算的过程。第一步是进行减法运算，将当前余数寄存器的内容减去除数寄存器的内容，得到结果是11100111。这时控制逻辑还会向余数寄存器发出写入的信号，在下一个时钟上升沿到来的时候，11100111就会写入余数寄存器。

2. 检查余数

现在余数寄存器已经更新了，第二步就是检查这个余数寄存器，如果大于等于0，就执行2a分支，否则执行2b分支。对于当前这个例子，我们发现余数寄存器的最高位是1，表示小于0，所以执行的是2b分支。

2b. 当余数<0

因为余数<0，意味着我们不应该进行刚才那次减法，所以我们这里就要回退刚才第1步的操作，即执行加法运算。控制逻辑会给ALU一个加法信号，让它进行计算，同时也会给余数寄存器一个写入的信号，在下一个时钟上升沿到来的时候，00000111就又会写入余数寄存器，这样就完成了回退的工作。

另外，我们还需要做的是将商寄存器左移1位，并将新的最右位设为0。这样这一步的内容就完成了。

2a. 当余数>=0

当余数>=0时，我们不需要进行回退的操作。举例，在第5轮的时候，第2步的运算结果得到的余数寄存器中的值时00000001，由于最高位是0，说明余数是1个正数。

那么此时要做的事情就是将商寄存器左移1位，新的最右位置为1。

3. 对除数进行右移

为了下一步运算做准备，我们现在要把除数寄存器右移1位。

4. 判断是否进行下一轮

因为这是1个4位的除法器，所以我们需要检查的是当前是不是第5轮循环。那经过检查，如果现在还不是第5轮，所以我们还需要进行下一轮计算，即重复上述1~4步的过程。

如果已经是最后1轮，则结束。结果如下图所示。所以对于这个例子来说00000111 / 0010 = 7 / 2 = 3，余1，与下面寄存器中的结果相符。

3. 除法器的优化1

这是我们已经有了的一个除法器的实现，我们称它为第1版。

我们首先来考虑面积方面的优化，目前有的问题是，除数寄存器实际只使用了其中的一半，商寄存器初始时是空的，从右到左逐位填满，余数寄存器初始时是满的，有实际意义的位从左到右逐渐减少。

从这些问题出发，我们可以进行如下的优化：

4. 除法器的优化2

除了面积优化以后，从乘法器那边得到启发，是不是还能做一些性能方面的优化呢？

但是乘法的特点是每个部分积是独立的，可以并行计算各个部分的积。而对于除法来说，需要检查上一轮做完以后的余数，并且如果余数<0，还需要进行回退，这样的话它每一轮的运算就不是相互独立的了，因此无法进行并行。所以在这个除法器的大框架下，很难进行进一步的性能优化。

当然，正是由于除法的优化非常困难，也引来了很多人对除法运算进行深入的研究，如果对此有兴趣，可以进一步深入地探索。