8.3 定点补码乘法器
本节介绍定点补码乘法器的设计。乘法指令在科学计算程序中很常见，矩阵运算、快速傅里叶变换操作中都有大量的定点或浮点乘法操作。在计算机发展的早期，由于硬件集成度较低，只通过ALU实现了加减法、移位等操作，乘法这样的复杂操作需要由软件通过迭代的移位-累加操作来实现。随着处理器运算部件的升级，现代处理器已经使用硬件方式来实现定点和浮点乘法操作。
8.3.1 补码乘法器
对于定点乘法器而言，最简单的实现方式就是通过硬件来模拟软件的迭代操作，这种乘法实现方式被称为移位加。其逻辑结构如图8.26所示。
图8.26 迭代式硬件原码乘法器
以两个8位数的乘法为例，乘法器的输入包括一个8位的乘数和一个8位的被乘数，输出则是16位的乘法结果。通过触发器将这3个数存储下来，并执行以下步骤：
1）最初时，将乘法结果设置为0。
2）在每个时钟周期，判断乘数的最低位。如果值为1，则将被乘数加到乘法结果；如果值为0，则不进行加法操作。此后将乘数右移1位，将被乘数左移1位，将参与运算的3个数锁存，进入下一个时钟周期。
3）执行8次操作，得到正确的乘法结果。
实现上述移位加算法需要的硬件很简单，组合逻辑延迟也较小，缺点是完成一条乘法需要很多个时钟周期，对于64位的乘法而言就需要64拍。但是，上述算法是将操作数视为一个无符号二进制数来设计的，如果计算的输入是补码形式，那么就需要先根据输入的正负情况判断出结果的符号位，随后将输入转换为其绝对值后进行上述迭代运算，最后再根据结果符号位转换回补码形式。很显然这样操作略显复杂，有没有直接根据补码形式进行运算的方法呢？
在8.1.1节中介绍过，现代处理器中的定点数都是按照补码形式来存储的，同时有［X］补+［Y］补=［X+Y］补的特性。那么，应该如何计算［X×Y］补呢？是否可以简单地将［X］补与［Y］补相乘得到呢？
还是以8位乘法为例。假定有8位定点数Y，［Y］补的二进制格式写作y7y6y5y4y3y2y1y0，根据补码定义，Y的值等于：
Y=-y7×27+y6×26+y5×25+…+y1×21+y0×20
由此推出：
［X×Y］补=［X×（-y7×27+y6×26+…+y1×21+y0×20）］补
=［X×-y7×27+X×y6×26+…+X×y1×21+X×y0×20］补
根据补码加法具有的特性，有：
［X×Y］补=［X×-y7×27］补+［X×y6×26］补+…+［X×y0×20］补
需要注意，这个公式中位于方括号外的加法操作为补码加法，而之前两个公式中位于方括号内部的加法为算术加法。由于yi只能取值为0或者1，再根据补码减法的规则，继续推导公式，有：
［X×Y］补=-y7×［X×27］补+y6×［X×26］补+…+y0×［X×20］补
公式中最开头的减号是补码减法操作。为了继续运算，需要引入一个定理：
［X×2n］补=［X］补×2n
该定理的证明可以较容易地根据补码的定义得出，留作本章的课后习题。据此定理，补码乘法的公式可以继续推导如下：
［X×Y］补=-［X］补×（y7×27）+［X］补×（y6×26）+…+［X］补×（y0×20）
=［X］补×（-y7×27+y6×26+…+y0×20）
最后得到的公式与移位加算法的原理很类似，但是存在两个重要区别：第一，本公式中的加法、减法均为补码运算；第二，最后一次被累加的部分积需要使用补码减法来操作。这就意味着［X］补×［Y］补不等于［X×Y］补。图8.27给出两个4位补码相乘的例子。注意在补码加法运算中，需要进行8位的符号位扩展，并仅保留8位结果。
图8.27 补码乘法计算示例
简单地修改之前的迭代式硬件原码乘法器，就可以实现补码乘法，如图8.28所示。
图8.28 迭代式硬件补码乘法器
依此方法，也可以计算32位数、64位数的补码乘法。运算数据更宽的乘法需要更多的时钟周期来完成。
8.3.2 Booth乘法器
Booth乘法器由英国的Booth夫妇提出。按照8.3.1节中的补码乘法算法，需要特地挑出第N个部分积，并使用补码减法操作，这就需要实现一个额外的状态机来控制，增加了硬件设计复杂度。因此他们对补码乘法公式进行变换，试图找到更适合于硬件实现的算法。
Booth一位乘变换的公式推导如下：
（-y7×27+y6×26+…+y1×21+y0×20）
=（-y7×27+（y6×27-y6×26）+（y5×26-y5×25）+…
+（y1×22-y1×21）+（y0×21-y0×20）+（0×20））
=（y6-y7）×27+（y5-y6）×26+…+（y0-y1）×21+（y-1-y0）×20
其中y-1取值为0。经过变换，公式变得更加规整，不再需要专门对最后一次部分积采用补码减法，更适合硬件实现。这个新公式被称为Booth一位乘算法。
为了实现Booth一位乘算法，需要根据乘数的最末两位来确定如何将被乘数累加到结果中，再将乘数和被乘数移一位。根据算法公式，很容易得出它的规则，如表8.5所示。
表8.5 Booth一位乘运算规则
注意算法开始时，要隐含地在乘数最右侧补一个y-1的值。图8.29给出了Booth一位乘算法的示例。
图8.29 Booth一位乘示例
在Booth一位乘算法中，为了计算N位的补码乘法，依然需要N-1次加法。而数据宽度较大的补码加法器面积大、电路延迟长，限制了硬件乘法器的计算速度，因此重新对补码乘法公式进行变换，得到Booth两位乘算法：
（-y7×27+y6×26+…+y1×21+y0×20）
=（-2×y7×26+y6×26+（y5×26-2×y5×24）+…
+（y1×22-2×y1×20）+y0×20+y-1×20）
=（y5+y6-2y7）×26+（y3+y4-2y5）×24+…+（y-1+y0-2y1）×20
根据Booth两位乘算法，需要每次扫描3位的乘数，并在每次累加完成后，将被乘数和乘数移2位。根据算法公式，可以推导出操作的方式，参见表8.6。注意被扫描的3位是当前操作阶数i加上其左右各1位。因此操作开始时，需要在乘数最右侧隐含地补一个0。
表8.6 Booth两位乘运算规则
还是以4位补码乘法为例，如图8.30所示。
图8.30 Booth两位乘示例
如果使用Booth两位乘算法，计算N位的补码乘法时，只需要
次加法，如果使用移位加策略，则需要N/2个时钟周期来完成计算。龙芯处理器就采用了Booth两位乘算法来实现硬件补码乘法器，大多数现代处理器也均采用该算法。
同理，可以推导Booth三位乘算法、Booth四位乘算法。其中Booth三位乘算法的核心部分为：
（yi-1+yi+2yi+1-4yi+2）×2i（i=0，每次循环i+3）
对于Booth三位乘而言，在扫描乘数低位时，有可能出现补码加3倍［X］补的操作。不同于2倍［X］补可以直接通过将［X］补左移1位来实现，3倍［X］补的值很难直接获得，需要在主循环开始之前进行预处理，算出3倍［X］补的值并使用额外的触发器记录下来。对于越复杂的Booth算法，需要的预处理过程也越复杂。所以，相比之下Booth两位乘算法更适合硬件实现，更为实用。本节接下来将介绍这个算法的电路实现方式。
Booth乘法的核心是部分积的生成，共需要生成N/2个部分积。每个部分积与［X］补相关，总共有-X、-2X、+X、+2X和0五种可能，而其中减去［X］补的操作，可以视作加上按位取反的［X］补再末位加1。为了硬件实现方便，将这个末位加1的操作提取出来，假设［X］补的二进制格式写作x7x6x5x4x3x2x1x0，再假设部分积P等于p7p6p5p4p3p2p1p0+c，那么有：
当部分积的选择为2X时，可以视作X输入左移1位，此时pi就与xi-1相等。如果部分积的选择是-X或者-2X，则此处对xi或者xi-1取反，并设置最后的末位进位c为1。
根据上述规则，经过卡诺图分析，可以得出每一位pi的逻辑表达式：
pi=~（~（S-X＆~xi）＆~（S-2X＆~xi-1）＆~（S+X＆xi）＆~（S+2X＆xi-1））
其中S+X信号在部分积选择为+X时为1，其他情况为0；另外三个S信号含义类似。画出pi的逻辑图，如图8.31所示。
图8.31 Booth结果选择逻辑
下文将使用图中箭头右侧的小示意图来代表pi的生成逻辑。生成逻辑中需要使用部分积选择信号，因此还需要考虑如何根据yi-1、yi和yi+1三个信号生成图8.31用到的4个选择信号。根据表8.6中的规则，很容易通过卡诺图化简得到：
S-X=~（~（yi+1＆yi＆~yi-1）＆~（yi+1＆~yi＆yi-1））
S+X=~（~（~yi+1＆yi＆~yi-1）＆~（~yi+1＆~yi＆yi-1））
S-2X=~（~（yi+1＆~yi＆~yi-1））
S+2X=~（~（~yi+1＆yi＆yi-1））
画出选择信号生成部分的逻辑图，并得到如图8.32所示的示意图。
图8.32 Booth选择信号生成逻辑
将两部分组合起来，形成每个Booth部分积的逻辑图，并得到如图8.33所示的示意图。
图8.33 Booth部分积生成逻辑
这个逻辑就是两位Booth乘法的核心逻辑。调用该逻辑，并通过移位加策略实现两位Booth补码乘的结构，如图8.34所示。
乘法操作开始时，乘数右侧需要补1位的0，而结果需要预置为全0。在每个时钟周期的计算结束后，乘数算术右移2位，而被乘数左移2位，直到乘数为全0时，乘法结束。对于N位数的补码乘法，操作可以在N/2个时钟周期内完成，并有可能提前结束。在这个结构中，被乘数、结果、加法器和Booth核心的宽度都为2N位。
图8.34 使用移位加实现Booth乘法
8.3.3 华莱士树
即使采用了Booth两位乘算法，使用移位加策略来完成一个64位的乘法操作也需要32个时钟周期，并且不支持流水操作，即第一条乘法全部完成之后才能开始计算下一条。现代处理器通常可以实现全流水、4个时钟周期延迟的定点乘法指令，其核心思想就是将各个部分积并行地加在一起，而非串行迭代累加。
以64位数据的乘法为例，共有32个部分积，如果按照二叉树方式来搭建加法结构，第一拍执行16个加法，第二拍执行8个加法，以此类推，就可以在5个时钟周期内结束运算。这个设计还支持流水式操作：当上一条乘法指令到达第二级，此时第一级的16个加法器已经空闲，可以用来服务下一条乘法指令了。
这种设计的硬件开销非常大，其中128位宽度的加法器就需要31个，而用于锁存中间结果的触发器更是接近4000个。本节将要介绍的华莱士树（Wallace Tree）结构可以大幅降低多个数相加的硬件开销和延迟。
图8.35 一位全加器示例
华莱士树由全加器搭建而成。根据8.2.1节的介绍，全加器的示例如图8.35所示。
S=~A＆~B＆C|~A＆B＆~C|A＆~B＆~C|A＆B＆C
C=A＆B|A＆C|B＆C
全加器可以将3个1位数A、B、C的加法转换为两个1位数S和C的错位加法：
A+B+C=S+（C＜＜1）
如果参与加法的数据较宽，可以通过调用多个全加器将3个数的加法转换为两个数的加法。图8.36给出了3个4位数相加的例子。
图8.36 使用全加器实现3个4位数相加
其中4位数A的二进制表示为A3A2A1A0，可以很容易得知：
{A3A2A1A0}+{B3B2B1B0}+{D3D2D1D0}={S3S2S1S0}+{C2C1C00}
公式中所有加法都为补码加法，操作宽度为4位，结果也仅保留4位的宽度，这也导致C3位没有被使用，而是在C0右侧再补一个0参与补码加法运算。
那么问题来了，如果需要相加的数有4个，又应该如何呢？很自然地想到，可以先将其中3个数相加，再调用一层全加器结构，将刚得到的结果与第4个数相加即可。不过要注意，全加器的C输出需要左移1位才能继续参与运算。如图8.37所示。
图8.37 使用全加器实现4个4位数相加
最后结果中，最高位进位C3和C′3都不会被使用。第二级的最右侧全加器需要在其中一个输入位置补0参与运算。从图8.37中可以看出，整个结构呈现重复特征，提取出圆角矩形框选中的部分，这部分称为一位华莱士树。准确地说，图中灰色部分呈现的是4个数相加的一位华莱士树结构，它除了输入的4个被加数、输出的C与S之外，还有级联的进位信号。通过M个这样的一位华莱士树，就可以实现4个M位数的相加。
可以简单地计算一下使用华莱士树进行相加的优势。根据图8.37的结构，4个数相加的华莱士树需要两层全加器，当前位的进位信号在第一层产生，并接到了下一位的第二层，这意味着Cout与Cin无关。全加器的S输出需要3级门延迟，而C输出需要2级门延迟，因此不论参与加法的数据宽度是多少位，将4个数相加转换为两个数相加最多只需要6级门延迟，最后把这两个数加起来还需要一个加法器。整套逻辑需要一个加法器的面积，再加上两倍数据宽度个全加器的面积。如果不使用华莱士树，而是先将四个数捉对相加，再把结果相加，计算的延迟就是两倍的加法器延迟，面积则是3倍的加法器面积。对于64位或者更宽的加法器，它的延迟肯定是远远超过6级门的，面积也比64个全加器要大得多。
因此使用华莱士树进行多个数相加可以明显地降低计算延迟，数据宽度越宽，其效果越明显。通过本节后续的介绍可以归纳出，使用华莱士树进行M个N位数相加，可以大致降低延迟log N倍，而每一层华莱士树包含的全加器个数为
（M′是当前层次要加的数字个数）。
回到本节最开始的问题，Booth乘法需要实现N/2个2N宽度的部分积相加，如果可以先画出N/2个数的一位华莱士树结构，通过2N次使用，就可以达到这个要求。为了描述的简洁，下面我们具体分析N=16即8个数相加情况下的一位华莱士树结构，如图8.38所示。
图8.38 8个数相加的一位华莱士树
从图8.38中可以看出，通过华莱士树可以用4级全加器即12级门的延迟把8个数转换成两个数相加。华莱士树的精髓在于：通过连线实现进位传递，从而避免了复杂的进位传递逻辑。不过需要指出的是，在华莱士树中，每一级全加器生成本地和以及向高位的进位，因此在每一级华莱士树生成的结果中，凡是由全加器的进位生成的部分连接到下一级时要连接到下一级的高位。图8.39所示的搭建方法就是没有保证这一点，所以是错误的。
图8.40的搭建方式修正了图8.39中级间进位传递逻辑的错误，但是它的搭建方式依然存在问题。为了理解问题出在哪里，我们需要从整个乘法器的设计入手。
为了构成一个16位定点补码乘法器，需要使用8个Booth编码器，外加32个8个数相加的一位华莱士树，再加上一个32位加法器。值得注意的是，根据上一节提出的Booth乘法核心逻辑，除了有8个部分积需要相加之外，还有8个“末位加1”的信号。在华莱士树中，最低位对应的华莱士树上有空闲的进位输入信号，根据图8.38的结构，共有6个进位输入，可以接上6个“末位加1”的信号。还剩下两个“末位加1”的信号，只能去最后的加法器上想办法：最后的加法器负责将华莱士树产生的2N位的C和S信号错位相加，其中C信号左移一位低位补0。据此设计，这两个“末位加1”的信号可以一个接到加法器的进位输入上，另一个接到C左移后的补位上。分析到这里，应该能够理解为什么说图8.38中的华莱士树才是合适的，因为这种搭建方法才能出现6个进位输入。
图8.39 一种错误的8个数相加的一位华莱士树
图8.40 修正后的8个数相加的一位华莱士树
最终的乘法器示意图如图8.41所示。
图8.41 16位乘法器示意图
图中间标注为switch的部分，负责收集8个Booth核心生成的8个32位数，进行类似矩阵转置的操作，重新组织为32组8个一位数相加的格式，输出给华莱士树，并将Booth核心生成的8个“末位加1”信号从switch部分右侧接出，提供给华莱士树最右侧的一位树及最后的加法器。此外图中没有画出的是，被乘数X送到8个Booth编码器时需要先扩展到32位，并按照编码器所处的位置进行不同偏移量的左移操作。