采用CSA与4-2压缩器改进Wallace树型乘法器的设计

引言

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

乘法器工作的基本原理是首先生成部分积，再将这些部分积相加得到乘积。在目前的乘法器设计中，基４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压缩器也就成为了目前乘法器中较多采用的加法单元。

如前所述，（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压缩器在威廉希尔官方网站 特性方面做一下分析比较。CSA的威廉希尔官方网站 逻辑实际上就是一位全加器，其关键路径上需要经过两级异或门逻辑的延时。对于4-2压缩器，可以把它看作是两个CSA按照图3形式相连而构成。

但这种未经过优化的威廉希尔官方网站 结构很可能造成关键路径不必要的延长。上文已提到，4-2压缩器实际上是由5个权1的输入，产生2个权2的输出（Cout，C）和1个权1的输出（S）。而本文之所以称其为4-2压缩器而非5-3计数器，是基于这样一个事实：将此单元作横向排列后，加数数目可以实现的压缩比为4:2。

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

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

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

此结构中，采用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树型结构求和速度快的优点，又较好地改进了原来那种由单一加法单元构成的阵列的不足。

本文在90nm工艺下采用全定制设计方法，利用Cadence的版图工具Virtuoso对各种情况进行了比较。另外，采用经过4-2压缩器级数度量关键路径的时延，不考虑互连延时，再通过AT2标准做了进一步的比较。

结语

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