32位乘法器性能比较
对基于阵列乘法器、修正布斯算法(MBA)乘法器、华莱士(WT)乘法器和MBA-WT混合乘法器的四种架构的32位乘法器性能进行了比较，在选择乘法器时,应根据实际应用,从面积、速度、功耗等角度权衡考虑。
乘法是数字信号处理中重要的基本运算。
在图像、语音、加密等数字信号处理领域,乘法器扮演着重要的角色,并在很大程度上左右着系统性能。
随着实时信号处理的提出和集成电路工艺水平的进步,人们开始致力于高速乘法器设计。
最初,阵列乘法采用移位与求和算法,部分乘积项(Partial Product, PP)数目决定了求和运算的次数,直接影响乘法器的速度。
修正布斯算法(Modified Booth Algorithm, MBA)对乘数重新编码,以压缩PP。
华莱士树(Wallace Tree, WT)结构改变求和方式,将求和级数从O(N)降为O(logN),提高了运算速度,但是WT存在结构不规整,布线困难的缺点。
用4:2压缩器(4: 2 compressor)代替全加器(FA)可以解决这一问题。
将MBA算法和WT结构的优点相结合,形成了MBA-WT乘法器。
以下1～4节将分别介绍阵列乘法器、MBA乘法器、WT乘法器、MBA?WT乘法器。
最后对四种乘法器的性能进行比较,并总结全文。
1 阵列乘法器
阵列乘法器基于移位与求和算法。
被乘数与乘数中的某一位相乘,产生一组PP,将该组PP移位,使LSB与乘数对应位对齐;求出全部PP,并相应移位;对所有PP求和,得到乘积。
因此,加法阵列结构非常重要。
CRA (Carry Ripple Adder)存在进位问题,运算速度慢。
CSA (Carry Save Adder)将本级进位传至下级,求和速度快,且速度与字长无关。
阵列乘法器中,CSA 把PP阵列缩减至Sum和Carry两项,再用高速加法器求和得积。
阵列乘法器结构规范,利于布局布线。
因为乘数和被乘数可正、可负,所以一般用二进制补码表示,以简化加、减运算。
补码运算需要符号扩展,符号扩展宽度与加法器结构有关。
对于CRA,加数和被加数符号扩展至本级和的最高位;对于CSA,扩展至两数最高位对齐。
符号扩展增加了符号位扇出,使电容负载不平衡,影响电路整体速度;需要冗余的加法器,扩大了版图面积。
符号扩展问题可用以下算法解决［1］。
假设P1=A、P2=B,求A+B: ①将A符号位扩展一位,对扩展位取反;②将B符号位取反;③在B符号位左边添1;④求和。
假设两个6位部分积A、B相加,需扩展一位符号位,如图1(a)所示;采用新算法后,计算式如图1(b)所示;相应6×6乘法
器电路如图1(c)所示。
2 MBA乘法器
求和是乘法运算中最耗时步骤。
缩减PP数目是提高乘法运算速度的方法之一。
阵列乘法中PP数目与乘数位数相等。
MBA算法通过对乘数重新编码,压缩PP数目,以提高运算速度。
压缩率取决于编码方法,如果采用三位编码,可压缩一半PP。
考虑到编码电路的引入,乘法器速度的提高是有限的。
基于MBA的乘法器架构如图2所示。
MBA算法描述如下:假设A为被乘数、B为乘数,均采用二进制补码表示:
按式(3),对乘数B重新编码,编码后B可用式(4)表示。
(n为偶数;若n为奇数,则B符号扩展一位)
如式(5)所示,A×B运算所需加?法次数减少了一半。
注意,求和时,Ki+1A相对于KiA需左移两位。
3 WT乘法器
树型结构可以减少求和级数,是提高乘法运算速度的另一方法。
1961年,Wallace提出的WT结构是其中最著名的一种。
它对于16位以上的乘法运算尤其适用。
WT 结构,将全部PP按列分组,每列对应一组加法器,各列同时相加,前列进位传至后列,生成新PP阵列;同法,化简新阵列,直至只剩两行PP;最后用高速加法器求和得积。
WT结构优点在于只需做O(logN)次加法,因而运算速度快。
6×6 WT 乘法器如图3所示。
在WT结构基础上,通过对PP划分的优化,可以进一步减少求和级数［2］。
注意到FA不同输入端到同一输出端的路径延时不同,不同端口在时序上应区别对待。
例如,两个FA的两种级联方式:
最长路径+最长路径、最长路径+最短路径。
后者关键路径小于前者,有利于提高速度。
在利用FA构建WT时,可以采用一种算法［3］使WT的最长路径最短。
缺乏规整性,布线困难,是WT结构最大的不足。
引线的延长导致寄生电容增加,妨碍了电路速度的进一步提高。
针对这一问题,Weinberger提出了基于4∶2缩减器的乘法器架构,其最大优点在于电路简单,连线规则。
4∶2缩减器可由FA构成,见图4(a);也可进行逻辑优化,见图4(b)。
4 MBA-WT混合乘法器
高速乘法器可同时采用MBA算法和WT结构,如图5所示。
首先,MBA算法把乘法运算N×M的PP压缩1／2;然后,WT 结构将PP按列分组,并行约减,直至PP阵列只剩余两行;最后由高速加法器求和得积。
因为WT结构中所有PP同时相加,所以符号位要扩展至M+N位。
这将花费大量硬件资源,并且严重影响运算速度。
符号扩展问题可由以下方法解决［4］。
假设部分积均为负数,可以预求所有扩展符号位之和
如果某一部分积为正数,再进行修正:将部分积的符号位s由0变成1就可以抵消预测的影响。
此方法较好的解决了符号扩展问题,提高了运算速度,并且硬件开销很小。
5 性能比较及总结
A. J. Al-Kbalili和N. Zaman利用FPGA,分别综合了基于以上四种架构的32×32乘法器,并比较了乘法器在面积、延时和功耗方面的性能参数,如表1所示［5］。
阵列乘法器面积小、功耗小,运算速度慢;WT乘法器和MBA-WT乘法器运算速度快,但功耗较大,WT乘法器面积最大,MBA-WT乘法器面积略大于阵列乘法器;MBA乘法器各项参数介于前三种乘法器之间。
不同乘法器架构在性能上都存在优点和缺点。
选择乘法器时,必须根据应用场合的要求,在面积、延时和功耗等方面综合考虑。
参考文献
[1] Salomon O, Green J M, and Klar H, General Algorithms for a Simplified Addition of 2’s Complement Numbers. IEEE JSSC, July 1995;30(7):839-844
[2] Robinson M E, Swartzlander E. A Reduction Scheme to Optimize the Wallace Multiplier In:Proc ICCD'98, 1998;122-127
[3] Oklobdzija V G. A Method for Speed Optimized Partial Product Reduction and Generation of Fast Parallel Multipliers Using an Algorithmic Approach. IEEE Trans Comp, Match 1996;45(3):294-305
[4] Ardekani J F. M×N Booth Encoded Multiplier Generator Using OptimizedWallace Trees . IEEE Trans VLSI systems, Jun 1993;1(2):120-125
[5] Al?Khalili A J. 32?bit Constant(k) Coefficient Multiplier In:Proc EE Tech, 2001。