一种具有动态加速浮点乘法运算功能的变基maeh算法

一种具有动态加速浮点乘法运算功能的变基maeh算法

随着数字信号处理器（pd）的发展，浮点运算器的应用越来越广泛。乘法器是浮点运算电路的关键部件,对其整体性能影响很大。自从20世纪50年代初文献提出Booth乘法器后,基于改进的Booth算法[2,.3]的乘法器设计就不断有人提出。很多设计采用高基的Booth算法,以求收到较好的加速效果。但高基Booth算法在带来较少的部分积累加次数的同时,也由于部分积不能完全直接通过移位生成而给累加器的设计带来了很多问题,最直接的一个问题就是一个2输入的累加器不能在生成部分积的同时完成累加。因此,这些设计所作的工作都集中在加法电路的优化上。许多加法器结构都是应乘法器设计要求而生,如CPA(carry-propagateadder)、CSA(carry-saveadder)和Wallacetree等。在此基础上对上述加法器结构进行改进,以解决设计中延迟过大、布局布线时资源利用率低等问题,使乘法器性能达到最优。而对于在有限的累加器资源下,如何通过采用合适的算法来使乘法器加速的讨论则未见到。任何基的Booth乘法器对乘法运算的加速都是硬性的,均未考虑到数据的特点。实际上,在有限的硬件(主要是加法器)资源条件下,通过对乘数的各位组成结构进行分析,也可减少部分积,收到动态加速的效果。本文设计的乘法器是利用乘数的特点灵活调整Booth编码的基数,所有的部分积都通过移位形成,对加法器要求低,关键路径的延迟大大减小。同时这种变基Booth编码的思想具有一般性的指导意义,可以用在其他的乘法器中,与具体的设计特点结合,得到更优的结果。1浮点乘数法算例硬件电路进行二进制乘法的运算原理同手算十进制乘法的原理本质上是一样的,都是逐位将乘数与被乘数相乘,产生部分积累加起来。可以统一表示为Ρ=n-1∑i=0Y×ai×mi(1)P=∑i=0n−1Y×ai×mi(1)其中,Y表示被乘数;ai等于0或1,表示乘数的第i位值;n为乘数的位数,i从0～n-1的每一项Y×ai×mi都称为部分积;m表示进制数,当m为2时,是硬件电路二进制乘法的基本计算原理,m为10时,则是手算十进制乘法的运算原理。计算实现过程可表示为Ρ0≤0Ρi+1≤Ρi+ai×Y≪i(2)Ρ≤ΡnP0≤0Pi+1≤Pi+ai×Y≪i(2)P≤Pn其中,Pi表示第i次迭代的累加和;“≪”表示左移操作,其他参数的定义同前。需要指出的是,通常对于浮点乘法运算来说,并不需要保留乘积的所有有效数字,一般只保留与被乘数相同的位数的有效数字。因此,在实现乘法运算时会随时舍弃低位的运算结果,其实现过程同理可表示为Ρ0≤0Ρi+1≤Ρi≫1+ai×Y(3)Ρ≤ΡnP0≤0Pi+1≤Pi≫1+ai×Y(3)P≤Pn从中可以看出,数字电路实现乘法运算的基本方法就是移位——累加。由此可见,减少迭代次数对于加快乘法运算的速度具有决定性的意义。有2种途径:①增强累加器的能力,同时完成多个部分积的累加,这是乘法阵列的根本思想。②减少需要累加的部分积的数目,典型的代表是Booth重编码方法,本文讨论的内容属于后者。1.1将补数与被乘数的编码生成部分积从(3)式表达的基本实现方法来看,乘数的每一位都产生部分积,数目很多。实际上当ai为0时,并不需要累加,则累加器需要完成的累加次数,即实际要生成的累加项的数目与乘数中值为1的位数相同。这样,如果能将乘数中值为1的位数减少,就可以减少所需要完成的累加次数。类似与手算乘法中分配律的使用,但乘数本身乘法运算复杂,而它却近似于某个大的整值数(如几百、几千等)时,可以用这个大的整值数与被乘数的积减去其对应这个整值数的补数与被乘数的乘积来进行计算。把这种思想引入到二进制乘法中,若乘数中的1≫0时,可以对其补数生成部分积。对整个乘数而言,出现这种情况的可能性很少,因此直接对整个乘数采用这种方法来减少部分积不切实际。一般是对乘数进行分组,通过分组可以消除整个乘数一起考虑时给乘数中0、1数目对比带来的统计效果,而使得局部0、1数目差别较大;而且分组可以使处理变得简单。将乘数进行分组,每组生成一个部分积。最基本的是4基Booth算法,每2位一组,8基Booth和16基Booth分别是每3位、每4位生成一个部分积,8基Booth以上称为高基Booth算法。对于每组生成部分积时,采用编码的方法,选择利用补数或原数来生成累加项较少的部分积(有时为了整体编码的简化,在不影响累加器复杂度的前提下,也可能选择累加项较多的部分积生成方法),以被乘数的倍数表示。运算乘积可表示为Ρ=[(n-1)/r]∑i=0Di×2r×i(4)P=∑i=0[(n−1)/r]Di×2r×i(4)其中,Di为第i组的部分积;2r为Booth的基值;n为乘数位宽。根据前面给出Booth算法减少累加项的原理可知:当每组位数多于2位时,存在原数和补数都含有2个(或更多)1的情况,即高基Booth算法的部分积不能完全通过移位直接生成,有时需要加法运算,这给乘法器中的加法器设计在面积和时序上都带来较大负担。1.2变基法定共享算法传统高基布斯的问题是:由改进Booth算法在生成部分积时对减少部分积的2种途径考虑的顺序所导致的。改进Booth算法首先考虑将乘数分组,在分组确定的基础上考虑如何减少累加项。它只是固定地将每几位乘数组合一起,没有考虑这种组合是否有利于部分积的直接生成。从上述讨论可知,分组不单是为了使处理简化,还有一个更重要的目的是使局部范围的0、1数目对比出现较大差别。而固定位数的分组方式没有考虑乘数中0或1分布的集中度问题,显然在这方面收效甚微。而从前面描述的补数的原理可以看出,分组位宽固定的要求并不必要。如果能在首先考虑减少累加项的基础上进行分组,再将乘数分割组合时能灵活变动,使乘数中0或1较集中的一段分为一组,而不是将固定位数的乘数组合在一起,就可以在不给累加器带来时序负担的前提下,较好地减少部分积生成数目。变基Booth算法的核心思想就是打破分组位数固定的限制,在考虑简化部分积生成的前提下确定每一组的宽度,根据乘数的当前特征灵活分组。不同的分组宽度,对应Booth算法的不同基值,因此称为变基Booth算法。确定分组宽度的原则是使生成部分积只需对被乘数作移位操作,而不需加法器的参与。其分组准则描述如下:准则1分组从最低位开始,顺次截取一定位数的乘数为一组,记为T=akak-1,…,a0。准则2若将T看成补码表示的带符号数,应有-2≤T≤1。准则3k≥1,若ak不是整个乘数的最高位,应有ak+1⊕ak=1。准则1是由乘法的运算规则决定的。值得一提的是,分组也可以从高位开始,需要从高位向低位乘的算法来配合。从高位向低位进行乘法累加的缺点是:增加了硬件资源消耗,而且导致关键路径长度增加;优点是,通过适当控制,可以使许多乘数低位为全零的数据运算提前多个周期完成,在某些特定场合可以使用。而本文讨论的是通用的浮点乘法计算,因此不在这一方面展开。准则2是保证部分积直接生成的关键,当-2≤T≤1时,可保证T中1的数目不会多于1个。若单独考察分组数据,当T=±2k时,均满足原码中只有一个1的条件,但考虑到相邻一组产生的进位时,只有T为-2、-1、0和1这4种情况满足要求。准则3则是由部分积最少的要求决定的,即力求每组的位宽在满足部分积移位生成要求的同时达到最大。这里需要指出的是,在实际设计中,为了控制逻辑的实现简洁,一般要有个位宽上限且位宽上限越大,控制逻辑越复杂。根据分组准则可知,乘数分组时每组的位宽最小为2位,最大的可能值为位宽上限。不同传统Booth算法,变基Booth的运算乘积可表达为Ρ=m∑i=1Di×2i-1∑j=0ri(5)P=∑i=1mDi×2∑j=0i−1ri(5)其中,Di为第i组的部分积;ri为第i组的位宽,r0=0,显然有:m∑i=1ri=n‚n∑i=1mri=n‚n为乘数位宽。通过剖析变基Booth乘法的运算原理并给出分组准则后,变基Booth乘法器的设计实现思路就非常清晰了。2编码值的确定和变形从变基Booth乘法的运算原理公式可以看出,设计实现的关键有4个部分:当前组位宽的确定、部分积的获得、累加的完成,以及累加和、乘数的移位。变基Booth乘法器的算法结构图,如图1所示。其中,Booth算法基值改变主要是通过分组控制逻辑来实现,依据前面给出的准则,结合乘数的特点来确定当前组的位宽。为了简化分组控制逻辑,本设计中设定位宽上限为8位。对于尾数宽度小于64位的乘法器来说,8位的位宽上限是比较合理的。对于部分积生成,由准则2可知,有-3<T<2,加上前一组的进位考虑,只需将每组的最低2位结合前一组的进位来译码就可以了,译码复杂度与4基Booth相当。变基Booth译码,见表1所列。从表1看出,它同4基Booth的编码表相同。这是因为分组时所控制的编码值T的范围同4基Booth完全一样,这也是变基Booth可以在不增加累加器复杂度的同时收到加速乘法效果的根本所在。这样,所有的部分积分布在-2Y～2Y之间,通过简单的移位就可以获得。设计实现中另一个关键在于累加和与乘数都需要进行可变位数的移位(这是由于分组位宽的不固定导致的),因此需要设计一个可以进行位数选择的移位单元,本文通过设计移位通道解决了这一问题,该移位通道可以实现0～8位右移操作。需要指出的是,为了节省资源,该移位通道用定制的方法来实现,在RTL仿真时使用开关级语句描述。另外,考虑节省面积,累加和与乘数移位复用移位通道,乘数移位与累加和移位分别占用时钟周期的高电平和低电平部分,累加和移位结果由时钟上升沿触发锁存,乘数移位结果由时钟下降沿触发锁存。由于用于累加的加法器都是通道设计,不含锁存机制,因此需要对当前组的控制字进行锁存。加法器不是本文的设计重点,实际上本文提出的变基Booth算法的目标就是减轻加法器的负担,任何通用的2输入加法器都适用于本设计,因此在综合设计时没有对这部分做过多优化。3不同工艺库的特性对比基于变基Booth算法的乘法器具有动态加速的功能,对于不同的操作数,加速效果不同。运用随机模拟的办法,从10万次、100万次…10亿次,对32位尾数宽度浮点乘法运算的周期数进行统计,当模拟到1000万次以后,平均周期数保持为10.832443,这一效果略优于传统8基Booth算法的加速效果。而本设计在面积和速度上都优于8基Booth乘法器。表2所列是本设计同采用CSA加法电路优化过的8基Booth乘法器在基于Tsmc0.25μm工艺库综合后的性能比较。在