第一章绪论
研究的意义和目的
在IC设计领域，计算机微处理器的发展日新月异。作为整个系统的核心，微处理器的性能指标十分重要，它的发展是集成电路发展的重要因素，也成为高性能运算和信息处理的决定因素。这些微处理器强有力的运算能力来源于其内部高性能的运算处理单元。因此，为了提高微处理器的性能，其关键路径上运算部件的性能就成了基石和原动力。
在数字系统中，加、减、乘、除是最常用到的运算，无论系统的应用领域为何，都必须具备一个基本的功能单元执行数字的操作和运算。早期的CPU中只有算术逻辑运算单元(Arithmetic Logic Unit ALU )，依靠一个ALU处理所有的运算。但随着高性能处理器的发展，对高速的加法、乘法、分支预测等运算的需求日益增加，简单的ALU结构己经无法满足要求。在当前的高端处理器中，除了ALU外还设有很多专用的运算单元，而后者成为处理器中最重要的一个部分。一般而言，整数运算单元除了包括ALU用来执行基本功能以外，还设有专用的高性能加法运算电路、乘法运算电路和移位运算电路，而浮点运算单元一般包含浮点加法器、浮点乘法器以及浮点开方等运算单元。现代的处理器运算单元已经成为一个高度复杂的运算模块，而且其性能直接影响着处理器的整体性能。
在各类微处理器、数字信号处理器(DSP )及专用集成电路(ASIC)中，加法都是使用频率最高的操作，加法器因此成为大规模集成电路(VLSI)中最基础的运算部件。在ALU、数据通路、地址产生单元、浮点运算单元及协处理器等部件中加法器都是核心模块并通常处于关键路径上。加法是一切运算的基础，借助加法和其它逻辑运算可以构成任何相对复杂的运算，如乘法、除法、数字信号处理中的离散余弦变换、快速傅里叶变换等。因此，对加法器的算法及结构的研究与设计是学习运算器设计的一个理想途径，对其它运算单元及整个微处理器的设计而言也是极其重要的。
另一方面，大多数先进的数字系统，如DSP、高性能的微控制器、滤波器等都包含有硬件乘法器，以实现复杂的数学运算并进行实时的处理。高性能的乘法除了直接用于运算单元外，如今在图像、语音、加密等信号处理领域扮演着重要的角色。乘法器电路结构相对复杂、延时大、运算周期较长，往往处于系统的关键路径上。DSP中乘法累加运算的实现速度几乎完全决定着数字信号处理的速度，而微处理器中完成一次乘法运算所需要的时间也基本上决定了微处理器的工作主频。因此，设计优化乘法器的结构将大大改善整个系统的速度、面积、功耗等指标。
数字逻辑电路设计的目的在于开发出合适的算法，并最终通过硬件实现高效的应用。这包括三个方面:算法的设计、电路的逻辑结构设计和电路的实现类型。算法是相对高层次的运算，是硬件实现的基础，没有高效的算法不可能有好的硬件设计。不同的算法可以用不同的电路逻辑来实现，电路的逻辑设计和逻辑实现方法直接决定着电路的性能，并且影响着算法的电路实现的效果。电路类型涉及到具体的电路结构和实现工艺，如纯静态的CMOS、传输管逻辑(PTL,Pass-Transistor Logic)、动态CMOS逻辑等。
本文分别对定点运算部件中最重要的加法器和乘法器进行了较为深入的研究，算法和电路逻辑设计的优化是本文的目标。以速度优先、兼顾面积为原则，针对加法器，结合优化的并行前缀结构、Ling进位与改进的选择进位模块设计实现了一种新型的高性能加法器。针对乘法器，从Booth算法、部分积产生电路的设计、部分积的优化设计、压缩器的设计及整个压缩部分拓扑结构的设计等方面进行讨论，通过提高每个部分的性能来达到实现高性能乘法器的目的。
1.2国内外发展动态
加法器因其重要性，得到了大量的研究，人们已经提出了多种二进制加法的算法及实现方式，主要是从延迟、面积、功耗三方面进行考虑。加法器实现的关键在于如何处理进位信号的产生和传播，目前比较成熟的算法包括:行波进位加法器(Ripple-CarryAdders, RCA)，时间复杂度和面积复杂度均为O(n)为操作数的位宽，因为进位信号要串行穿过n个全加器单元，它是资源需求最少但延迟最大的加法器:超前进位加法器(Carry-Lookahead Adder CLA )，时间复杂度为O(log n)，面积复杂度为O(nlog n)，是速度最快的加法器，但需要大量的硬件开销;跳跃进位加法器(Carry-Skip Adder, CSKA)和选择进位加法器(Carry-Select Adder,CSLA)，时间复杂度为。面积复杂度为O(n)，是两种折衷了速度与面积的加法器。
CLA因为速度快、结构模块化，得到了最广泛的应用。人们对其做了大量研究并提出了很多变种及改进的实现方法，其中并行前缀加法器(Parallel Prefix Adder,PPA)结构简单、速度最快，成为高速加法器最理想的选择。PPA的实现是基于一种简单的前缀运算单元，通过该单元将进位链组成树型结构，其实现结构非常灵活，从比较经典的Ladner&Fischer结构、Kogge&Stone结构、Brent&kung结构，到Cheng介绍的最小深度零延迟的前缀加法算法, Sabyasachi运用3进制进位树设计的一种新型的PPA结构，人们对前缀加法器研究的热情从未减少。
2.1 数据通路........... 11-12
2.2 加法器的实现........... 12-15
2.3 乘法器的实现........... 15-19
2.4 其它运算部件........... 19-22
2.5 设计方法与设计...........22-23
2.6 小结........... 23-25
第三章 一种新型加法器........... 25-37
3.1 并行前缀加法器算法........... 25-28
3.1.1 并行前缀算法........... 25-26
3.1.2 前缀加法器的........... 26-28
3.2 优化的并行前缀........... 28-30
3.3 新型的前缀Ling选择........... 30-36
3.3.1 Ling进位........... 30-31
3.3.2 优化的前缀Ling........... 31-35
3.3.3 综合结果........... 35-36
3.4 小结........... 36-37
第四章 并行乘法器的........... 37-55
4.1 部分积生成单元...........37-44
4.1.1 Booth编码........... 38-39
4.1.2 任意k阶Booth编码...........39-41
4.1.3 部分积产生单元的........... 41-42
4.1.4 综合结果与性........... 42-44
4.2 部分积的优化........... 44-47
4.2.1 有符号数和........... 44-45
4.2.2 部分积符号位...........45-47
4.3 部分积压缩单元的........... 47-52
4.3.1 4:2压缩器的........... 47-49
4.3.2 几种4:2压缩器的........... 49-50
4.3.3 6:2压缩器与9:2........... 50-52
4.4 64位快速进位传递........... 52-54
4.5 小结........... 54-55
结论
本文对定点计算部件中的加法器与乘法器从算法和电路逻辑实现的角度进行比较深入的研究。在讨论现有算法和传统结构的基础上，针对加法器，提出了一种运用优化的并行前缀结构、Ling进位与改进的选择进位模块相结合的新型加法器。针对乘法器，对各阶段子模块的设计进行了分析，重点设计实现了6: 2与9: 2压缩器，运用9: 2压缩器家族实现了3种改进的并行乘法器和一种4周期串并结合的乘法器。综合结果表明，在速度优先、兼顾面积的原则下，设计的新型加法器和改进的乘法器同传统的结构相比都具有更好的性能。
本文的主要目的在于从研究的角度讨论定点加法器和乘法器在算法和逻辑结构上优化的设计方案，本文完成的主要工作有:
1、设计了一种新型的前缀Ling选择进位加法器，同传统的实现结构相比性能得到了明显提高。