基于改进的元素化的高速乘法器的设计与实现

基于改进的元素化的高速乘法器的设计与实现

1基于补码的编码原理大乘法器是现代处理器和数字信号处理器的重要部件。它是数据处理和其他实时数据处理的核心。它的性能直接影响系统处理数据的性能。由于编码算法的原因，提高大乘法器的性能主要取决于三个部分：部分积的压缩和最终部分的添加。根据补码的特点，使用4-4号压缩法减少部分积的数量，并采用改进的基于单元的新型沃敦树结构，提高部分积的压缩效率。魏立局hdl用于描述rtl级。通过综合和配置布局，实现了大乘工艺，并满足了设计要求。2编码局部积数乘法器的结构如图1所示,该乘法器用作32×32有符号/无符号的乘法运算.采用sign符号位来区分运算为有/无符号乘法运算.无符号数的范围为0～232-1,有符号数的范围为-231～231-1.乘法运算步骤分为两步:①根据算法求出部分积;②将所有部分积求和.因此减少部分积的数目和快速求出部分积的和便成为研究的热点.文中针对这两个部分,采用改进的BOOTH编码实现部分积数目的减少;部分积求和的速度则通过使用以一种改进的4-2压缩器为单元的新型Wallance树型结构来实现.利用以上两部分压缩得出两个64位部分积和结果时,最后利用一个64位超前进位加法器将前面两个结果相加得出最终的结果.3基于四博茨算法和编码逻辑的设计基4Booth算法能够将部分积数目减至乘数位数的一半,大大提高了乘法器的速度;同时结构较为规整、连线简单,易于VLSI版图实现.3.13无符号、无符号相乘首先设A为被乘数,B为乘数,且均为32位无符号数,P表示乘积.则有A×B为Ρ=A×(31∑i=0bi2i)=A×[16∑n=0(b2n-1+b2n-2b2n+1)4n]=16∑n=0A(b2n-1+b2n-2b2n+1)22n(1)P=A×(∑i=031bi2i)=A×[∑n=016(b2n−1+b2n−2b2n+1)4n]=∑n=016A(b2n−1+b2n−2b2n+1)22n(1)式(1)中的各项式为部分积,用PP表示,于是有ΡΡn=31∑i=0ai2i(b2n-1+b2n-2b2n+1)22n(2)n=0,1,⋯,16PPn=∑i=031ai2i(b2n−1+b2n−2b2n+1)22n(2)n=0,1,⋯,16为了符合基4Booth算法的要求,令式(1)、式(2)中b33=b32=b-1=0,这样从式(1)可以看出无符号32位数相乘一共有17个部分积.其实对于有符号数,只要对乘数进行符号扩展,令b33=b32=b31,令b-1=0,这样有符号、无符号数相乘就统一起来了.统一后的部分积PP16为ΡΡ16={0有符号乘法A⋅b31⋅232无符号乘法3.2mbe-编码逻辑由式(1)知道基4Booth编码一次检测乘数临近的3位,根据检测的三位的结果产生对被乘数不同的操作.文献中提出了三种不同的基4Booth编码方式,其中MBE-Ⅰ就是最常用的只产生“1”与“2”两种倍数的控制信号以及一个正负控制信号的三条控制线的编码方式,这种方式使用的门电路比MBE-Ⅲ不少多少,延迟却接近MBE-Ⅲ方式的2倍.因此这里采用的MBE-Ⅲ编码方式编码及控制信号如表1所示.传统的基4Booth编码逻辑表示和部分积产生逻辑分别如图2(a)、图2(b),从表1中可以得出4个控制信号的逻辑表达式和部分积产生的逻辑设计分别如图3(a)、图3(b)所示.对比图3和图2,可以发现,在关键路径上图3少了一个△NOR门延迟时间.4积专的积附加方法当产生部分积PPn之后,将它们相加就可得到乘法结果.部分积相加的方法有多种,采用不同的压缩器组成的不同加法结构直接影响乘法器的速度和版图规则性.所以较好的乘法器总是从压缩器单元和压缩结构两方面着手来取得速度与面积、规则的最佳组合.4.1传统压缩器组成结构分析4-2压缩器又称为(5,3)计数器,是一个5输入、3输出的加法部件.这5个输入的权是相同的(权重为20),其中4个是部分积,这里记作i1、i2、i3和i4,另一个输入为进位信号记作cin.3个输出中一个与输入的权值相同为伪和sum,另两个分别为进位信号carry和cout(权值都为21).传统的4-2压缩器由两个串行连接的全加器组成(如图4(a)所示).但这样的压缩器延迟门较多.对传统的基于全加器组成的压缩单元进行分析,得出其布尔表达式如下:S=a1⊕a2⊕a3⊕a4⊕cin(3)Carry=(a1⊕a2⊕a3)·a4+(a1⊕a2⊕a3)·cin+a4·cin(4)Cout=a1·a2+a1·a3+a2·a3(5)对式(4)、式(5)两个表达式进行等价的逻辑转换可以得到以下两个布尔表达式:Carry=(a1⊕a2⊕a3+a4)⋅cin+¯(a1⊕a2⊕a3+a4)⋅a4(6)Cout=(a1⊕a2)⋅a3+¯(a1⊕a2)⋅a1(7)从式(6)、式(7)两式可以看到,逻辑电路可由异或门和2选1的选择器组成,可以构成如图4(b)中所示的逻辑结构.这种结构减少了信号传播的逻辑门数量,并且具有较小的负载电容.这种结构具有高速、低功耗的优点,相比传统结构优势明显,更适合于版图实现.4.2符号位扩展的部分积根据基4Booth算法要求,操作数要进行符号扩展.乘数的扩展是在低位补一个0,高位补两个符号位,得到一个35位的补码数据;被乘数的扩展是在高位补两个符号位,形成34位的补码数据.由前文可知,对于产生的17个部分积,每个均为34位.如果直接将这些部分积相加则必须将每个部分积的高位部分以符号位的值扩展到加法阵列的最高位(这里为66).扩展结果如图5(a)所示.图5(a)中S为每一个部分积的符号扩展位(即PPn),可以从图中看出扩展后CSA阵列很大,需要逻辑资源会很大.为了得出符号不必扩展的方法,先假设所有的部分积都是负的,那么对于32位的乘法,图5(a)中所扩展的符号位都为“1”.这样,这些所有符号扩展的“1”的和为S-sum=16∑i=0(233-22i)mod233=16∑i=0(-22i)=-(232+230+L22+20)=-1010⋯10101=(1010⋯1011)补(8)将这S和可以作为一个定值加入部分积中,符号位扩展“1”就可用S-sum=(1010…1011)2来表示,最低位的权值是234.如此表示,图5(a)左上角的S就全为“0”,不用扩展了,每一个CSA阵列的部分积长度一致了,如果一个部分积实际是非负的,则该部分积的符号位应为“0”,为了消除前面假定它是负数带来的影响,只需将该部分积的符号位加“1”.这样图5(a)结构就变为图5(b)中的结构.另外,部分积产生逻辑仅完成了部分积的取反,要得到部分积求补,还需给末位加“1”.这时对末位附加2位,其中高一位为“0”,低位是前一个部分积作为进位信号送来的求补的末位加“1”.这样,加上符号位扩展的数据,总的部分积就变成了18个,这些部分积中除符号位扩展的部分积为34位外其他的17个均为37位(包括符号修正的1位、末位附加的2位).4.3不同结构的对比采用不同的加法阵列结构直接影响乘法器完成一次乘法所需要的时间.重复阵列(IternativeArray,IA)和Wallace树是最为典型的两种加法阵列结构.IA结构规则性好,易于版图实现,但速度最慢;Wallace树型结构是理论上速度最快的加法阵列结构,但传统的Wallace树电路互联较为复杂,版图实现困难.为了解决这个问题,人们总是想在速度与规则性上取得较好的平衡而提出了如ZM树和OS树等结构.这些结构基本上都是将IA分为几段,以每段作为子树,子树内部采用IA结构,而子树间采用树型连接.几种结构的比较见表2.对于32位有/无符号乘法器,由4.2节可知一共有18个部分积,如果采用4-2压缩器作为唯一的压缩单元,则18不能被4所整除,其中两个部分积必然要在第一级4-2压缩后额外处理.只要仅单纯采用4-2压缩器作为压缩单元,采用OS树则会破坏树的对称性;采用传统Wallace树则规则性很差布局困难;采用文献的结构则增加了关键路径的延时却仍不能解决布局对称问题.基于此,文献提出了一种CSA(3-2压缩器)和4-2压缩器相结合对18个部分积进行压缩的Wallace树型结构,如图6所示.该结构设计平衡性很好,使得各级的中间结果能够同时被处理,各路径时延取得平衡,相比仅采用4-2压缩器的结构,节省了等待时间.同时,两级的CSA取代两级的4-2压缩器,还减少了关键路径的延时.再者,从图6和表2中可以看出,该结构对称性和规则性很好,AT2较其他结构提高明显,易于版图实现.因此文中采用文献的这种结构.5功能仿真和时序优化本乘法器采用VerilogHDL语言采用自顶向下的方式进行了RTL级描述,主要为操作数预处理、基4Booth编码和部分积求和的改进Wallace阵列结构三部分.使用Mentor公司的Modelsim进行功能仿真,使用Synopsys公司的DesignCompiler和SMIC的0.18μm标准单元库进行逻辑综合和优化,得到该工艺下的门级网表;然后再利用门级网表加上标准时延文件(.sdf)进行时序仿真;最后对正确的门级网表采用Candence公司的布局布线工具SiliconEnsemble布出最终物理版图.结果