基于改进型选择进位加法器的32位浮点乘法器设计

摘 要： 在修正型Booth算法和Wallace树结构以及选择进位加法器的基础上，提出了一种新型32位单精度浮点乘法器结构。该新型结构通过截断选择进位加法器进位链，缩短了关键路径延时。传统选择进位加法器每一级加法器的进位选择来自上级的进位输出。提出的结构可以提前计算出尾数第16位的结果，它与Wallace树输出的相关位比较就可得出来自前一位的进位情况进而快速得到进位选择。在Altera的EP2C70F896C6器件上，基于该结构实现了一个支持IEEE754 浮点标准的4级流水线浮点乘法器，时序仿真表明，该方法将传统浮点乘法器结构关键路径延时由6.4 ns减小到5.9 ns。

关键词： 修正Booth算法； Wallace树结构； 选择进位加法器； 浮点乘法器

中图分类号： TN702?34 文献标识码： A 文章编号： 1004?373X（2013）16?0133?04

浮点乘法器是数字处理器的重要组成单元，它的性能直接关系到整个数字系统的性能。所以浮点乘法器一直以来是人们研究的热点。而乘法器的设计主要是对速度、面积、功耗等因素的优化与折中。Booth 算法大大缩小了部分积数量；Wallace tree、dadda tree等压缩树结构实现部分积的并行求和提高了乘法器的速度，进位保留加法器（Carry Save Adder，CSA）则实现最终两个部分积的快速求和。文献[1]基于乘法器各级核心器件是加法器的思想，通过优化加法器减小了乘法器的延时。文献[2]设计了一种改进的基4 Booth编码和华莱士树的24位符号定点乘法器，在功耗和面积降低的同时，延时也得到了减小，做到了芯片性能和设计复杂度之间的良好折中。文献[3]提出了一种适用于FPGA结构的改进型Wallace tree架构乘法器，实现了资源和性能的合理平衡。本文提出了一种新的结构，该结构通过截断选择进位加法器进位链，缩短了最终两个部分积相加的进位传播延时。

1 传统浮点乘法器

本文中乘数、被乘数以及最终结果均采用IEEE754标准[4]的32位单精度浮点格式。

1.1 单精度浮点格式

根据IEEE 754标准，32位单精度浮点分为3个部分：符号位S（Sign），指数位E（Exponent），尾数位M（Mantissa） 其结构图如图1所示。

符号位S位宽为1，S为0表示浮点数为正，S为1则表示浮点数为正；指数位E位宽为8，其包含一个127的偏置所以原浮点数的指数为E-127；尾数M位宽为23，表示浮点数的小数部分，其隐含了为1的整数部分所以单精度浮点数表示方法为：

[F=-1S×1.M×2E-127] （1）

1.2 单精度浮点格式

传统浮点乘法器主要可以分成3个部分：符号计算、指数计算以及尾数计算[5]：

（1）符号计算。将乘数和被乘数的符号位相异或即可得到结果的符号位。

（2）指数计算。乘数与被乘数指数部分减去偏置后相加，然后根据溢出情况以及尾数的最高位对指数进行相应的调整；最后将指数加上偏置并规范化处理得到最终结果的8位指数部分。

（3）尾数部分计算。首先乘数和被乘数的尾数经修正Booth编码单元产生13个部分积，再由4?2压缩单元构成的Wallace树将这13个部分积压缩至Carry，Sum形式，接着通过CSA对其加权求和（Carry左移一位后与Sum相加）经尾数调整并规范化后得到结果的23位尾数[6]。整体结构如图2所示。

2 浮点乘法器关键部件设计

尾数运算部分所耗资源最多且延时最长，是浮点乘法器设计的关键。尾数运算包括Booth编码产生部分积、Wallace tree以及CSA三部分，下面介绍该关键部件设计。

2.1 修正Booth编码产生部分积

修正Booth算法可以用如下数学模型表示：

[P=A×B=A×i=023bi·2i =A×n=112b2n-1+b2n-2b2n+1 ] （2）

[Pn=A×b2n-1+b2n-2b2n+1?22n] （3）

每次交叠取乘数的3位来产生部分积，根据每组编码结果不同选择被乘数的倍数[7]{0， M，-M，2M，-2M}。具体操作是：先将乘数进行扩充（末尾添‘0’，首位添加符号位‘0’，为了保证扩展后的乘数位宽为奇数故在最前面再添‘0’）；接着根据交叠所取的3个位按照表1所示的真值表选取相应的被乘数倍数左移2n位并进行符号扩展得到48位的部分积。

表1 修正Booth编码真值表

2.2 Wallace 树型结构

Booth编码产生了13个48位宽的部分积，将这13个部分积相加即得到尾数相乘的结果，为了提高部分积求和速度，Wallace 树被广泛采用，它的基本单元是4?2压缩器。4?2压缩器有5个输入（A、B、C、D、Cin）和3个输出（Sum，Cout，Carry）。它的逻辑表达式如下：

[Sum=ABCDCin] （4）

[Cout=A·B+A·C+B·C] （5）

[Carry=ABC·D|Cin|D·CinCin] （6）

这种4?2压缩器关键路径为4个XOR延时。而本文采用了一种改进型的4?2压缩器能将关键路径降低至3个XOR延时[8]其结构如图3所示。Wallace 树由一级一级的4?2压缩器构成[9]（本文采用3级），4?2压缩器低位输出的Cout输入到相邻高位的Cin，最低位Cin输入为‘0’；输出的Sum和Carry输入到下一级；其结构如图4所示。

2.3 选择进位加法器

速度最快的加法器是超前进位加法器（CLA），但当加数位宽增加时CLA布局布线非常复杂。选择进位加法器将一个位宽很宽的数分段采用CLA相加，并分别考虑进位为‘0’和进位为‘1’两种情况；再根据相邻低段的进位选择输出结果。这种结果在很大程度上降低了布局不线的困难，其结构如图5所示。

图5中红色线标识出了CSA的关键延时。很明显将加数分的段数越多能减少CLA部分的延时，但进位选择路线也迅速增加。本文根据不同的分段[10]设计了4种方案并在Altera公司的FPGA芯片EP2C70F896C6上进行了仿真，结果统计如图6所示，图7中从上倒下依次为方案1～4的仿真结果。

3 改进型浮点乘法器

对上述传统浮点乘法器在FPGA上实现并仿真可知关键路径为48位加法器即CSA部分，从上文对CSA的分析可知其延时为一个CLA延时加上进位延时。而本文提出一种方法可以缩短进位延时。主要思想是在Wallace树这一级（ Stage2～Stage3 ）提前算出尾数相乘结果的第16位（S_16），而Wallace树输出Carry的第15位（Carry（14））和Sum的第16位（Sum（15））相加，如果等于S_16则说明进位加法器这一段进位为‘0’否则为‘1’。避免等待来自上一级的进位，从而缩短了进位传播链，见图8。

3.1 第16位尾数（S_16）的计算

S_16由乘数和被乘数尾数的低16位决定，所以和上述乘法器类似，要先经Booth编码产生部分积。16位数相乘要产生9个部分积，但第9个部分积的前16位均为‘0’，所以计算S_16只需用到前8个部分积的低16位。随后两级4?2压缩器构成的Wallace树即可对这8个部分积压缩得到Carry和Sum，最后经CSA求和取第16位即可得到S_16。

3.2 缩短CSA的进位链

选择对图6中时延最短的方案2进行分析，得到S_16后可以根据Carry（14）以及Sum（15）求得第4段的进位C3，它们的逻辑关系如式（7）所示：

[C3=Carry14Sum15S_16] （7）

这样相当于有两条进位链同时传播，第一条进位链为C0～C2，另一条为Sum（15）～C3～C4，具体的结构如图9所示。这种结构的CSA路径延时为5.9 ns。图10为尾数部分的仿真波形图。时序分析得出该方法的关键路径延时为5.9 ns，如图11所示，所耗逻辑资源为1 918个；而传统方法为6.4 ns，所耗逻辑资源为2 113个。

4 结 语

该设计选用EP2C70F896C6芯片用VHDL语言在QuartusⅡ9.1上实现；并且在相同的条件下与传统设计方法进行了比较。结果表明，本文提出的结构通过缩短选择进位加法器进位传播链，将浮点乘法器的关键路径延时缩短了0.5 ns。

参考文献

[1] JAIN A， DASH B， PANDA A K， et al. FPGA design of a fast 32?bit floating point multiplier unit [C]// Proceedings of 2012 International Conference on Devices， Circuits and Systems （ICDCS）. [S.l.]： IEEE， 2012： 545?547.

[2] 王定，余宁梅，张玉伦，等.改进型Booth华莱士树的低功耗、高速并行乘法器的设计[J].电子器件，2007，30（1）：252?255.

[3] 王良全，黄世震.基于FPGA的WALLACE TREE乘法器设计[J].现代电子技术，2011，34（16）：113?115.

[4] IEEE. IEEE754?2008. IEEE standard for floating?point arithmetic[S]. US： IEEE， 2008.

[5] 周德金，孙锋，于宗光.32位高速浮点乘法器优化设计[J].半导体技术，2007，32（10）：871?872.

[6] SUN Kai?hong. Design and implementation of a module generator for low power multipliers [D/OL]. [2003?09?25]. www.diva?/smash/get/diva2：19271.

[7] MACSORLEY O L. High?speed arithmetic in binary computers [J]. Proceedings of the IRE， 1961， 49（1）： 61?91.

[8] OHKUBO N， SUZUKI M， SHINBO T， et al. A 4.4 ns CMOS 54×54?b multiplier using pass?transistor multiplexer [J]. IEEE Journal of Solid?State Circuits， 1995， 30（3）： 251?257.

[9] WALLACE C S. A suggestion for a fast multiplier [J]. IEEE Journal of Trans Electron Compute， 1964， 13（1）： 14?17.

[10] 周德金，孙锋，于宗光.一种32位高速浮点乘法器设计[J].电子与封装，2008，8（9）：35?38.

[11] 程卫东，朱樟明，王雷.一种基于动态阈值NMOS的1.2 V CMOS模拟乘法器[J].电子科技，2011（9）：38?41.