一种改进的Wallace树型乘法器的设计

在微处理器芯片中，乘法器是进行数字信号处理的核心，同时也是微处理器中进行数据处理的关键部件。乘法器完成一次操作的周期基本上决定了微处理器的主频。乘法器的速度和面积优化对于整个CPU的性能来说是非常重要的。为了加快乘法器的执行速度，减少乘法器的面积，有必要对乘法器的算法、结构及电路的具体实现做深入的研究。

基４Booth算法与乘法器的一般结构

乘法器工作的基本原理是首先生成部分积，再将这些部分积相加得到乘积。在目前的乘法器设计中，基４Booth算法是部分积生成过程中普遍采用的算法。对于N位有符号数乘法A×B来说，常规的乘法运算会产生N个部分积。如果对乘数B进行基４Booth编码，每次需考虑3位：相邻高位、本位和相邻低位，编码后产生部分积的个数可以减少到[(N+1)/2] （[X]取值为不大于X的整数），确定运算量0、±1A、±2A。对于2A的实现，只需要将A左移一位。因此，对于符号数乘法而言，基4 Booth算法既方便又快捷。而对于无符号数来说，只需对其高位作0扩展，而其他处理方法相同。虽然扩展后可能导致部分积的个数比有符号数乘法多1，但是这种算法很好地保证了硬件上的一致性，有利于实现。对于32位乘法来说，结合指令集的设计，通常情况下需要相加的部分积不超过18个。

对部分积相加，可以采用不同的加法器阵列结构。而不同的阵列结构将直接影响完成一次乘法所需要的时间，因此，加法器阵列结构是决定乘法器性能的重要因素。重复阵列（Iterative Array，简称IA）和Wallace树型结构是最为典型的两种加法器阵列结构。IA结构规整，易于版图实现，但速度最慢且面积大；理论上，Wallace树型结构是进行乘法操作最快的加法器阵列结构，但传统的Wallace树型结构电路互连复杂，版图实现困难。为了解决这个问题，人们推出了一些连接关系较为简单的树型结构，例如ZM树和OS树。它们都是将IA树分为几段，每段称之为子树，子树内部连接采用IA结构，而子树间采用树型连接，以此来降低连接复杂度，但是这种方法降低了部分积相加的速度。

在对树型结构进行改进的同时，设计者们也尝试了对加法阵列中基本加法单元的改进。Wallace最早提出的方案中，是以CSA（进位保留加法器）作为基本单元构建加法阵列的。其基本方法是：通过CSA部件，以3∶2的压缩比对部分积进行逐级压缩，直到最后只产生两个输出为止，再通过进位传递加法器对产生的这两个伪和与局部进位相加得出真正的结果。此后，Dadda提出了一种新的加法单元，称为“（j，k）计数器”，它有j个输入和k个输出，其中j≦2k。经过研究和实践，人们发现4-2压缩器（实际上是5-3计数器）具有较好的平衡性和对称性，用其作为基本加法单元构成的乘法器在总体性能上具有一定的优势，因此4-2压缩器也就成为了目前乘法器中较多采用的加法单元。

图1中列举了乘法器中几种加法器阵列的结构，它们都采用4-2压缩器作为基本加法单元来完成对18个部分积的加和。图中每个矩形代表一组4-2压缩器，带箭头的线段表示部分积与中间结果。

（a）IA阵列（b）Wallace树
（c）一阶OS树　（d）参考文献中的树型结构



图1 对18个部分积相加所采用的加法阵列结构

如前所述，图1（a）中的IA阵列，结构最为规整，但很明显，其延时级数大大多于其他结构。（b）是Wallace树结构，由于采用4-2压缩器作为唯一的加法单元，而18不能被4整除，因此在对18个部分积的求和过程中，必然要对其中的两个部分积做额外处理。Wallace树采取的方法是：先将16个部分积通过三级4-2压缩器后产生两个结果，然后与剩下的两个部分积一起再进行一级4-2压缩。（c）中的一阶OS树结构也采用了类似的方法，只是在处理的先后顺序上有所改变。这两种结构，都破坏了树的对称性，造成路径的不等长，因此浪费了硬件资源，且增加了布局布线的复杂度。（d）是参考文献中提出的一种经过改进的树型结构，其求和过程是：将18个部分积分为3组，先对每组中的6个部分积求和，各产生两个中间结果，再把这6个中间结果相加。由于对每组中的6个部分积求和，可以采用相同结构的两组4-2压缩器，这样就很好地降低了布局布线的复杂度。其缺点在于：用4-2压缩器对6个中间结果进行相加的过程中，仍不能避免路径不平衡的问题，因此，还是使关键路径的延时有不必要的增加。

CSA和4-2压缩器的电路结构和时延分析

既然CSA和4-2压缩器是加法阵列中主要采用的基本单元，那么，就有必要对CSA和4-2压缩器在电路特性方面做一下分析比较。如图2所示，CSA的电路逻辑实际上就是一位全加器，其关键路径上需要经过两级异或门逻辑的延时。对于4-2压缩器，可以把它看作是两个CSA按照图3形式相连而构成。



图2 CSA电路结构



图3 由两个CSA连接而成的4-2压缩器电路结构

通过图3所示的连接方式能够很容易地实现4-2压缩器。但这种未经过优化的电路结构很可能造成关键路径不必要的延长。上文已提到，4-2压缩器实际上是由5个权1的输入，产生2个权2的输出（Cout，C）和1个权1的输出（S）。而本文之所以称其为4-2压缩器而非5-3计数器，是基于这样一个事实：将此单元作横向排列后，加数数目可以实现的压缩比为4:2。基于真值表，可以设计出较为理想的4-2电路结构，如图4所示，其中采用了基于2选1多路选择器的异或门电路结构代替传统的异或门。



图4 基于多路选择器的4-2压缩器电路结构

此外，通过平衡路径，该结构使横向进位链不对关键路径的延迟造成影响，也就是说产生C和S信号所需的时间不决定于Cin信号，电路关键路径为3个异或门的延迟。在90nm工艺条件下，采用Mentor公司的eldoD仿真工具得到的实际电路延迟仿真数据如表1所示。由此可见，一级4-2压缩器的最大延时约为一级CSA最大延迟的1.5倍，但完成了两级CSA所做的相加工作。

表1 4-2压缩器和CSA时延仿真数据

信号延时　P1　 P2　 P3　 P4　信号延时　 A　B　C
S （ps）187.76　201.30　194.99　192.77Sum（ps）134.46　138.11　94.492
C （ps）185.79　183.98　187.5 195.14Carry（ps）118.97　111.98　100.73

（a）4-2压缩器时延仿真数据 　（b）CSA时延仿真数据