1、High performance multiplier is the important component of the digital signal processor，the key to implement the signal processing and image processing；Multiplier always has large area, long latency and complex structureIt becomes attractive how to design a fast，simple and regular multiplierIn the pa
2、st ten years，researchers have developed new Booth algorithm to improve the performance of the multiplier；Developed many formal compress trees to make the structure of the multiplier more regular；Implement the circuits using pass-transistor logic，multiplexer, dynamic method and so on；The topology of
3、multiplier, which related with physical implementation closely，also developed very rapidlyHowever，the desire for high performance computation makes the design of multiplier not come to the endBased on the work in designing a floating-point multiplier in the 16 bit floating point DSP, this dissertati
4、on gives a systematic research on the every stages of the multiplier considering delay, area and complexBased on the study of Booth algorithm，multiplier topology, and the final adder, this thesis introduces and compares kinds of multipliers，implemented a 16 bit high performance parallel multiplier,
5、the exponent and mantissa of which compute in parallel way ,modified Booth algorithm and（4：2） compress tree are used to generate and calculate the partial productsCarry select adder sums the final two partial products；Character vectors and random vectors are used to test the multiplier, the code inc
6、ludes this multiplier has passed the software/hardware test.Keywords :Floating Point Multiplier, Booth Encoder,（4：2） Compressor , （3：2） Compressor Normalize目 录. 前 言随着微电子技术的不断进步、计算机技术的不断发展，集成电路经历了小规模、中规模、大规模的发展过程，目前已经进入超大规模（VLSI）和甚大规模集成电路（ULSI）阶段。超大规模集成电路工艺在21世纪初得到了高速的发展，目前商业化半导体芯片制造技术的主流已经达到45nm的线宽并
7、正迅速向更高集成度、超小型化、高性能、高可靠性的方向发展。在早期的计算机中都不具备浮点运算硬件，而是采用IBM公司的J.Backus发明的软件，由定点运算部件完成浮点运算。然而，基于软件的实现方法速度较慢，无法满足高速浮点计算的需要。为此WKahan在Intel公司工作期间，主持设计和开发了8087芯片，于1980年实现了高速、高效的浮点运算处理器。从此，乘法器随着浮点运算的发展独立出来，现代高性能处理器中整数运算单元和浮点运算单元均设有独立的乘法器。乘法器研究上的里程碑应该从Booth AD在1951年提出的Booth编码方法和Wallace的树型压缩开始。随后出现了Booth2算法、压缩器
8、（进位保留加法）、延迟平衡树等各种算法结构。在国内乘法器的研究主要集中在各个研究所和高校并且都在稳步的发展当中。本文将从延迟、面积、结构复杂性等方面系统地研究乘法部件的各个过程，在研究乘法器Booth编码算法，乘法器部分积压缩拓扑结构和高速求和等算法的基础上，分析比较乘法器各部分的不同实现方法，设计了一个高性能的16位浮点并行乘法器。第1章 绪 论 1.1 高性能乘法器设计研究的依据和意义微处理器的发展也随着集成电路的迅猛发展而日新月异。已经有越来越多的处理器包含多个运算单元，算术运算单元已经成为处理器结构中的一个重要组成部分。作为数字处理器中重要的部分，浮点运算部件通常都是整个设计中需要重点
9、考虑的对象。浮点运算通常需要多个时钟周期才能完成，为了得到接近实际值的运算结果，某些数值计算领域如流体动力、计算物理学、气象模型等等，需要很高精度（如128位字长）的浮点运算。而高精度浮点运算的固有特性决定了它具有面积大、功耗大的特点。速度、成本和功耗成为集成电路设计中目前最受关注的几个问题。高性能数字乘法器是数字信号处理器中的重要部件，且往往位于处理器的关键路径上。数字信号处理中的图像、语音、加密等信号处理需要进行大量的卷积、相关、窗口及FFT等基本运算，需要频繁进行大数据量的乘法和加法运算。通过对大量数字信号处理算法的分析，卷积、相关、变换、级数等运算占数据处理总运算量的75。因此乘法器和
10、加法器很大程度上左右着信号处理系统的性能。根据SFOberman和MJFlynn的技术报告，浮点乘法的使用频率占浮点运算37。正因为乘法器被如此广泛地采用，高性能乘法器的研究和实现十分重要。1.2 高性能处理器中乘法器的应用现状过去十年，高性能处理器日新月异，乘法器的性能也随之不断提高。当前处理器中，800MHz的Itanium需要5个周期完成一个54位浮点乘加运算。Compaq公司的Alpha21264包含整数运算单元和浮点运算单元两个部分，其中整数运算单元专门设置了定点乘法运算器。在1 GHz的时钟主频下，018um 54位浮点乘法采用流水线结构需要4个时钟周期，64位定点乘法需要7个时钟
11、周期。除此之外，0.18um425MHz的MIPS R20000也包含定点和浮点两种乘法器，其54位浮点乘法在5个周期内完成，64位定点乘法在7个周期内完成。Sun的UItraSparc IV包含定点和浮点两种乘法器，浮点乘法在4周期内完成，64位定点乘法在9周期内完成，0.13um工艺制作的CPU工作频率1.2GHz。IBM的013 um 18 GHz的Power PC970包含有多周期的定点乘法器。HP的1GHz PA-8800利用浮点运算单元处理定点乘法，定点乘法通过一系列移位加指令实现。DSP的核心是其中的乘法累加单元，且乘法器占据了DSP的大部分硬件资源。1981年，日本NEC公司推
12、出的uPD7720是第一个具有乘法器的商用DSP芯片。1982年日本的Hitachi公司推出了浮点DSP芯片。1983年，日本的Fujitsu公司推出的MB8764其指令周期为120ns，且具有双内部总线，从而处理的吞吐量发生了一个大的飞跃。而第一个高性能的浮点DSP芯片应是AT&T公司于1984年推出的DSP32。生产32位浮点DSP的主要厂家有Analog Devices，AT&T，Motorola以及Texas Instruments等公司。1.3 国外乘法器现状理论方面：电路方面:1995年Ohkubo基于传输管逻辑实现了44ns 54位乘法器，同时提出了新的4：2压缩单元结构和进位选
13、择加法器结构。1996年Hanawa实现了43nS的54位乘法器，同一年，Makino实现了88ns54位冗余二进制编码乘法器。1997年Inoue提出了符号选择Booth解码和改进的4：2压缩单元结构，实现了41ns的54位乘法器。1998年Hagihara基于动态技术和传输管逻辑实现了27 ns的54位乘法器。同年Carlson介绍了60 ns的64位乘法器实现方法。2001年Itoh实现了一个600MHz的两级流水线的54位乘法器。2003年Cho基于标准单元库实现了一个325ns的54位乘法器，并提出了改进的进位选择加法器结构。1.4 国内乘法器现状1993年中科院声学研究所应用于18
14、位乘法器，实现工作频率38MHZ.。1997年国防科技大学完成应用于数字神经处理的16位乘法器，频率30MHZ。2001年西安微电子技术中心于敦山实现了32位定/浮点乘法器延时56/76ns。2002年西安交通大学袁寿财实现了0.25um下延时40ns。2003年中科院计算研究所周旭采用0.18um的工艺实现54位浮点乘法器384MHZ。2004年复旦大学武新宇采用0.18um的工艺实现64位乘法器延时2.82ns。2005年上海大学王田采用0.18um的工艺实现32位乘法器延时3.15ns。2007年东南大学王定采用FPGA设计24位乘法器延时18.81ns。1.5 课题设计（研究内容）从延
15、迟、面积、结构复杂性等方面系统地研究乘法部件的各个过程,在研究乘法器Booth编码算法，乘法器部分积压缩拓扑结构和高速求和等算法的基础上，分析比较乘法器各部分的不同实现方法，设计了一个高性能的16位浮点并行乘法器。1.6 研究方法首先，研究乘法器常见的算法与结构，各种不同算法的性能和适应范围。其次，确定乘法器的结构，主要是根据乘法器需要达到的性能要求来初步确定可能影响到乘法器性能的主要因素。进而，重点在算法与结构方面来优化乘法器的性能。最后，采用多种结构来进行乘法器的RTL级设计，前仿真验证其功能的正确性，后仿真验证其性能在特定工艺与电压下达到要求，并得到版图文件。第2章 浮点数的数据格式2.
16、1 数据的表示方法计算机常用的数据表示方法有：带符号数值表示法、基数反码表示法、基数补码表示法：正数的三种表示方法相同，负数的表示方法入下：（1）、带符号数值表示法： A=（smn-1mn-2m1m0）在原码的基础上增加一位符号位来表示。其中s表示数据的符号，l表示负数，0表示正数。（2）、基数的反码表示（补“1”表示法）：A=（），即在不改变符号位的基础上，将其它数据位取反。（3）、基数的补码表示（补“2”表示法）：A=（）+1），原码取反然后加1得到。2.2 浮点运算中的数据格式浮点格式数据包括三个组成部分：指数区（Exponent），符号区（Sign），分数区（Fraction），其中将
17、符号区和分数区统称为尾数区（Mantissa）。如图2-1浮点数的计算方法是，s是数据的符号位，f是分数区数据（二进制），e是指数区数据（等价到十进制），尾数区是一个规格化的二进制补码，小数点在尾数区与指数之间。X=0时，f=0，s=0，e=10000（负的最大值）。图2-1 浮点数据格式（1） 短浮点格式短浮点格式的数据由4位指数位，1位符号位和1l位分数位组成，本文采用这种数据格式，如图2-2。图2-2 短浮点数据格式（2） 单精度浮点格式单精度浮点格式由8位指数位，l位符号位与23位分数位组成，是DSP中常用的浮点数据表示格式，如图2-3。图2-3 单精度浮点数据格式（3） 扩展精度浮点
18、格式扩展精度浮点数由8位指数位，1位符号位与31位分数位组成，使DSP中输入数据的常见表示方式，如图2-4。图2-4 扩展精度浮点数据格式2.3 舍入与规格化通常把尾数最高位为非零的浮点数称为规格化浮点数，在浮点数的运算中，当出现非规格化数时，需要通过移位操作来使它变成规格化数。如果尾数采用小数表示，当出现尾数绝对值小于12时，要把尾数左移，每次移动一个单位，同时把阶码减l，直到尾数的绝对值大于12，当尾数绝对值大于1时，要把尾数右移，每次移动1位，同时阶码加1，直到尾数的绝对值小于l。浮点数要进行舍入的原因是：由于任何一种浮点数表示方式尾数字长总是有限的，因此可能发生如下两个问题，一是在把通
19、常的十进制数转化成计算机的浮点数使其有效长度可能超过给定的尾数字长，必须要舍去多余的部分；二是两个规格化的浮点数进行加减乘除，结果尾数的字长超过了给定的尾数字长，如在乘法运算时，乘积的尾数字长是给定的浮点数字长两倍，需要将一部分的数舍弃。常见的舍入方法有：（1） 恒舍法：直接舍去需要移出的位数损失一位精度实现起来比较容易。（2） 恒置法：舍去移出位后将最末的尾数位置为1，损失一位精度，实现起来比较容易。（3） 下舍上入法：类似于四舍五入法，实现起来有一定复杂性。（4） R*舍入法：对下舍上入法的一种改进，不存在累计误差的一种舍入方法，实现起来很复杂。（5） 查表法：通过ROM或者PLA中的内容
20、来修正误差，比较有前途的一种舍入方法，实现难度一般。规格化和舍入的关系是：必须要先进行规格化，然后舍入，否则舍入是没有任何意义的。2.4 定点乘法运算溢出：指的是所得到的结果的超过了定点数所能表示的上限。如图2-5图2-5 定点数溢出定点乘法运算流程第一步：判断输入的操作数，若其中之一或者全部是0时直接将结果置为0。第二步：若操作数有效，则进行乘法运算。第三步：判定运算的结果，是否有溢出，若发生溢出时，判断结果正负，若结果是正数，则将最终结果置为最大正数，否则置为最小负数。第四步：舍入以得到符合要求的数据格式。第五步：得到最终结果。图2-6 定点乘法运算流程图2.5 浮点乘法运算浮点数的乘法相
21、对定点数的乘法要复杂，可以理解为浮点数的乘法包含了尾数定点数（man）的乘法与指数定点数（exp）的加法两个运算部分。阶的上溢：指的是所得到的结果的阶超过了浮点数所能表示的上限与或下限，也就是说+或者是-都被认为是溢出的条件。阶的下溢：指的是所得到数的阶超出了最小允许值。如图2-7图2-7 浮点数溢出浮点运算流程图图2-8 浮点运算流程图操作数的尾数位进行乘法运算，输入的数据为12位输出结果为24位；操作数的指数部分进行相加运算结果为c（exp）；判定尾数情况，若为0则执行第七步操作将结果的指数位置为-128;第四步与第五步：用于对结果进行规格化处理；如果需要进行右移1位进行规格化，执行第八步
22、，尾数右移，直属加1，如果需要右移两位进行规格化，则执行第九步，尾数右移两位，指数加2；第十步，将尾数结果扩展为扩展精度浮点格式。第六步到第十一步：判断指数情况如果指数溢出，进行第十四步操作，如果尾数大于0，将指数置成最大正数，若尾数小于0，则将指数置成最小负数。如果指数下溢出，则执行第十五步，将指数置成-128，尾数为0，若指数在范围内。则进行第十六步操作，得到最终结果。第3章 乘法器基本原理与算法乘法运算可以通过硬件方法和软件方法来实现，具体实现方法根据乘法运算所需要的开销和硬件配置情况决定。在计算机发展的早期阶段，复杂的运算往往通过编写程序或者硬件微程序的方法来实现。今天，科学计算、数字
23、信号处理和图像处理等计算量很大的领域对高性能乘法运算的需求使得乘法运算必须通过全硬件方法实现。而微电子和计算机技术的快速发展和进步，令专用乘法器电路的实现成为可能，并且成本不断降低。对于高性能的乘法器设计，优秀的乘法算法与结构是其硬件实现的基础，浮点乘法中几个主要步骤是：部分积产生、部分积压缩、进位传播加法和舍入处理。除了针对浮点数的指数操作、舍入和规格化等操作以外，浮点乘法器的结构和定点乘法器没有什么区别。如何进行部分积的缩减与压缩是区分各种乘法算法的关键所在。简单的算法容易实现，但速度较慢；复杂的算法可以满足快速运算的要求，但是要占用更多的硬件资源导致芯片面积增加。因此，实际设计的时候就需
24、要根据具体的速度、面积、复杂度等要求选择一种合适的算法。本章首先介绍乘法器的基本原理以及简单的乘法器，紧接着介绍部分积缩减算法与部分积压缩算法；最后介绍各种高性能加法器。3.1 乘法器基本原理3.1.1 乘法定义考虑两个没有符号的二进制数，X与Y，长度分别M与N，可以用二进制形式来表示X与Y这里X、Y在0 1范围内，乘法器的定义如下：无论乘法是采用何种方式来实现，任何一种乘法器都可以分成部分积的产生与部分积求和两个部分。因此提高乘法器的速度可以从减少部分积的数量与缩短部分积的求和延时两个方面出发，电路设计是面积，延时，复杂度的折中，所以一般来说，简单的乘法器易于实现，延时较大，而高速乘法器将会
25、有复杂的电路结构。3.1.2 迭代乘法器从手算的经验可知执行一个乘法运算最简单的方法就是采用一个两输入的加法器，进行部分积的累加，得到最终结果。对于N位的乘数与N位的被乘数的输入，实现乘法运算需要N个加法器与2N个寄存器，乘法的移位和相加把N个部分积加在一起，部分积是通过被乘数与乘数移位后末位相与操作得到，然后将结果与存放在寄存器中的前次运算得到的结果进行相加，并将结果仍然存放在寄存器中，如此反复。这样的操作在硬件实现上就是迭代乘法器。迭代乘法器的中间结果需要用寄存器保存的。其中时钟信号可以使用系统时钟信号。迭代乘法器需要的硬件资源比较少，所以，其消耗的功耗也比较小。但是因为它是迭代的，需要分
26、时利用资源，所以总的延迟时间比较长。图3-1 迭代乘法器3.1.3 线性阵列乘法器通过研究可知迭代乘法器的速度不能满足高速运算的需求，一种改进的方法是将迭代乘法过程展开，在一个时钟周期内完成两个部分积的求和，这样在同样的时钟周期完成求和次数是迭代乘法器的两倍。将这一操作映射到硬件上就是线性阵列乘法器。它结合了三个功能：部分积产生，累加部分积与最终相加。乘法器需要消耗的资源增加了，功耗与复杂度也有一定的增加。3.1.4 并行乘法器根据上述两种乘法器结构可以看出，将迭代的结构展开，乘法器的速度会有所提升，所以，进一步将阵列乘法器的迭代进行展开就得到完全并行的乘法器结构。全阵列乘法器完成NN的乘法需
27、要NN个加法器与NN个部分积的产生单元，延迟时间为O（N），为了进一步提升乘法器的速度，将部分积求和网络连接成树型结构，采用压缩器来压缩部分积，树型结构需要的资源要比全阵列结构要少，完成NN乘法运算的时间为O（Log（N）。但是树型乘法器的连线比阵列乘法器来的复杂。图3-2 并行乘法器3.2 乘法器编码算法.2.1 阵列乘法器首先介绍简单的阵列乘法方法，这是最原始的运算方法，通过被乘数与乘数的每一位相与操作后得到的部分积只有两种情况0，M，即部分积在乘数相应位为0时为0，乘数相应位为1时就为被乘数M,运算规则如图3-3。而且控制选择这两种情况只需要通过一个与门就可以了。阵列乘法器缺点是部分积的
28、个数和乘数的位宽相同。对于16x16位的乘法过程，需要处理的点的数量为256（16x16=256），而点阵的高度与乘数的位宽相同。图3-3阵列乘法器.2.2 Booth编码ADBooth研究了有符号乘法运算中复杂的符号修正问题并提出了一种乘数编码方法。该算法通过每次在乘数中交叠取两位（）来产生部分积P，运算规则和操作过程如图3-4所示。该算法需要N拍，最多会产生N个部分积。该算法的原理与后面介绍的修正Booth算法类似，对于补码表示的两数相乘无需进行符号位修正，并且对乘数的扫描可以从乘数的任意端开始。其主要缺陷是对于N位乘数仍需要N次移位和平均N2次加法，对于16x16位的乘法过程，需要处理的
29、点的数量为256（16x16=256），而且点阵高度与乘数位宽相同。图3-4 Booth算法.2.3 修正Booth编码显然，采用Booth编码并没有提高乘法器的运算速度，1961年OLMcsorley把Booth算法中的每次交叠检验乘法的两位推广到每次交叠检验三位，即著名的BoothMacSorley算法或修正Booth算法。本文后面提到的Booth或修正Booth算法都是指的这种算法。修正Booth算法每次编码时检查3位，其中2位来自当前组，第3位来自高一组的最低位。实际上，每组的最低位被检查2次。这种改进Booth算法能保证使部分积减少一半，从而提高了运算速度并降低了硬件复杂度，该算法在1975年被LPRubinfield所证明。通俗点以k=2为例介绍Booth算法,如果这两位二进制数为00，则加0；如果为01，则加A（A为被乘数）；如果为10， 则加2A（A左移
