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

摘要：对Booth算法产生的部分积重新合理分组，采用CSA和4-2压缩器的混合电路结构，对传统的Wallace树型乘法器进行改进，提出一种高速的树型乘法器。该结构与传统Wallace树型乘法器相比，具有更小的延时，更规整的布局和更规则的布线，使其易于VLSI实现。
关键词：Booth算法；Wallace树；CSA；4-2压缩器；树型乘法器

引言
    在微处理器芯片中，乘法器是进行数字信号处理的核心，同时也是微处理器中进行数据处理的关键部件。乘法器完成一次操作的周期基本上决定了微处理器的主频。乘法器的速度和面积优化对于整个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）参考文献[5]中的树型结构

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

    如前所述，图1（a）中的IA阵列，结构最为规整，但很明显，其延时级数大大多于其他结构。（b）是Wallace树结构，由于采用4-2压缩器作为唯一的加法单元，而18不能被4整除，因此在对18个部分积的求和过程中，必然要对其中的两个部分积做额外处理。Wallace树采取的方法是：先将16个部分积通过三级4-2压缩器后产生两个结果，然后与剩下的两个部分积一起再进行一级4-2压缩。（c）中的一阶OS树结构也采用了类似的方法，只是在处理的先后顺序上有所改变。这两种结构，都破坏了树的对称性，造成路径的不等长，因此浪费了硬件资源，且增加了布局布线的复杂度。（d）是参考文献[5]中提出的一种经过改进的树型结构，其求和过程是：将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.77  Sum（ps） 134.46 138.11 94.492
C  （ps） 185.79 183.98 187.5 195.14  Carry（ps） 118.97 111.98 100.73
（a）4-2压缩器时延仿真数据      （b）CSA时延仿真数据

改进的Wallace树型乘法器结构及性能比较

    对于32位乘法来说，符号数相乘时，基4 Booth编码形成16个编码项，并由此产生16个部分积；无符号数相乘时，编码项与部分积各多出一个。此外，在目前CPU指令集的设计中，乘加/减（C±A×B）指令已被广泛采用。所以，在一次乘法运算中，加法阵列中需要相加的部分积最多达到18个。而部分积个数对阵列结构的设计有着重大的影响，进而也就影响了布局布线的复杂度以及阵列的延迟级数。这一点在上文对图1中各个阵列结构的分析中，可以得到很好的证明。

    为了解决图1中各结构在对部分积求和过程中存在的树型结构对称性不好、规整性差、布局布线复杂度高，以及关键路径延时不必要增加等问题，本文基于传统的Wallace树型结构，对其做出了改进，提出如图5所示的树型阵列结构。
 

图5  CSA与4-2压缩器相结合的树型阵列结构

    此结构中，采用CSA和4-2压缩器共同作为基本加法单元，对18个部分积进行压缩。其具体过程为：先采用CSA对18个部分积做第一次压缩，产生12个中间结果，再采用4-2压缩器进行第二次压缩，然后再分别采用CSA和4-2压缩器对第二次压缩产生的6个中间结果和随后产生的4个中间结果做压缩，得到最终的两个伪和，送入进位传播加法器得到最终结果。该结构通过在第一次和第三次压缩中采用CSA，使得最初的18个部分积和用4-2压缩器进行第二次压缩产生的6个中间结果能够同时得到处理，使各条路径在时延上达到平衡，相比于只采用4-2压缩器作为基本加法单元的阵列，这就节省了不必要的等待时间。与此同时，用两级CSA取代两级4-2压缩器，也使得关键路径的延时有了明显的缩短，对高速集成电路设计有着很高的实用价值。

    此外，由图5可以看出，此结构具有较好的对称性和规整性，宏模块数量少，有利于布局布线。同时，对于目前指令集设计中常用的乘法指令，该结构对硬件的利用率也是相当高的。概括地说，该结构保持了传统Wallace树型结构求和速度快的优点，又较好地改进了原来那种由单一加法单元构成的阵列的不足。
 
    为了比较该结构与图1所示各结构阵列的面积，本文在90nm工艺下采用全定制设计方法，利用Cadence的版图工具Virtuoso对各种情况进行了比较。另外，采用经过4-2压缩器级数度量关键路径的时延，不考虑互连延时，再通过AT2标准做了进一步的比较，结果如表2所示。(其中由表1数据可得，1级CSA延时≈0.7级4-2压缩器延时。

表2 各种结构的比较

阵列结构 面积A（μm2） 延时T（4-2级数） AT2 用Wallace树归一化
IA阵列 0.0362 8 2.3168 3.3
Wallace树 0.0437 4 0.6992 1
一阶OS树 0.0402 4 0.6432 0.92
参考文献[5]结构 0.0414 4 0.6624 0.95
本文提出结构 0.0418 3.4 0.4832 0.69

结语
    采用CSA与4-2压缩器相结合的电路，在对部分积的求和过程中对硬件达到了最为高效的利用。同时，这种结构既发挥了CSA版图面积小的优点，又体现了4-2压缩器压缩比高、速度快的长处，因此，与其他结构相比，本文提出的改进结构在面积和速度上都达到了相对理想的效果。虽然其在布局布线上有一定的复杂度，但与传统的Wallace树相比，已取得了颇为可观的改进。目前，该结构乘法器的版图设计工作已基本完成，并被用于正在进行的64位高性能嵌入式CPU设计的项目中，预计于2007年3月进行流片。

参考文献
1 Bwick G. Fast multiplication：algorithms and implementation[D]. Stanford University, 1994
2 Poornaiah, D. Algorithm for designing efficient VLSI concurrent add-multiply and add-multiply-add cells for DSP applications[J]. Electronic Letters, 2000, 36(5)：399-400
3 Jessani R M, Putrino M. Comparison of Single- and Dual-Pass Multiply-Add Fused Floating - Point Units[J]. IEEE Trans Comput, 1998, 47（9）：927-937
4 Sousa L, Chaves R.. A universal architecture for designing ef