五分钟搞不定系列- 1+1=?

作者简介

甄建勇，高级架构师（某国际大厂），十年以上半导体从业经验。主要研究领域:CPU/GPU/NPU架构与微架构设计。感兴趣领域:经济学、心理学、哲学。

1. 引言1加1等于几？

这个问题很简单，一年级的小学生都会毫不犹豫的回答是：2。

可是你知道计算机是怎么计算出来的吗？

你可能会说：“用电脑上的计算器算一下”。

“可是，电脑上的计算器是怎么计算出来的呢？”

“计算器就是个软件，使用变量加法语句就能计算加法”

“变量加法语句经过编译，又会变成什么？”

你可能会说：“会变成CPU的加法指令，使用CPU的加法指令就能计算加法”。

“那CPU里面的加法指令是谁完成的呢？”

你可能会说：“CPU里面有加法器，加法器负责完成加法指令”。

“那加法器又是怎么工作的呢？”

你可能会说：“有行波加法器和超前进位加法器，他们的工作机制不同”。

“聪明！不过加法器一般能计算多bit的加法，那么1bit的加法器是怎么工作的呢？”

你可能会说：“1bit的加法器，可以通过真值表表达出来，然后根据真值表，用逻辑门就能搭出一个加法器来”。

“逻辑门一般包括与或非门，你知道这些逻辑门是由什么组成的呢？”

“这个嘛，逻辑门是由CMOS组成的。”

“那CMOS又是由什么组成的呢？”

“PN结，PN结可以表示0和1，这个我知道”。

“PN结是怎样表示0和1的呢？”

“PN结具有正向导通，反向截止的特性，用输出端的电压的高低，表示0和1”。

“为什么PN结会正向导通？”

“什么是PN结，什么是栅极（Gate），源极(Source)和漏极(Drain)？”

“为什么CMOS采用硅（Silicon）作为基础材料，而不采用不锈钢？”

“硅的原子序数是多少？又有哪些化学性质？原子的电子排列规律有哪些？”

“什么是原子轨道，精细结构？”

“什么是原子的能级？”

“如何用薛定谔方程和波函数计算原子的能级？”

“薛定谔方程是偏微分方程，如何求解偏微分方程？”

“求解偏微分方程一般采用的变分法是什么？”

“变分法在计算时，需要计算1 1”

“请问：1 1=？”

如果想知道答案，请看最上面的第一个问题。

关于以上问题，不知道你能问出哪些，又知道哪些问题的答案。如果你以上问题都能回答，请接受我的佩服之情。本文以下内容将讨论其中的一些问题。注：以下内容部分来自《计算机体系结构基础》，如有需要请参考原文。

后面的内容将按如下顺序展开：

硅->PN结->CMOS->逻辑电路->补码->加法器->乘法器->浮点数

2.硅

先说一下原子核核外电子的分层排布规律：

1、第一层不超过2个，第二层不超过8个；

2、最外层不超过8个。每层最多容纳电子数为2n^2个(n代表电子层数)，即第一层不超过2个，第二层不超过8个，第三层不超过18个；

3、最外层电子数不超过8个(只有1个电子层时，最多可容纳2个电子)。

4、最低能量原理：电子尽可能地先占有能量低的轨道，然后进入能量高的轨道，使整个原子的能量处于最低状态。

硅，英文叫Silicon，原子序数是14，根据原子的电子排布规律，可知，硅最外层电子数是4。而最外层电子为8是稳定的（比如惰性气体），所以硅原子与相邻的4个硅原子形成共价键，纯净硅中形成正四面体网格，所以纯净硅的导电性很弱。

但是，如果在纯净硅中掺杂少量3价原子（比如硼），那么这些原子挤占原有硅原子的位置后, 其最外层还缺少一个电子和相邻的硅原子形成共价键, 形成空穴。在电场的作用下, 周围的电子就会跑过来填补这个空穴, 从而留下一个新的空穴, 相当于空穴也在顺着电场方向流动, 形成正电流。这类材料被称为P(Positive) 型材料。

如果在纯净硅中掺杂少量5 价的原子(如磷), 这些原子将挤占原有硅原子的位置, 而由于这些原子的最外层有5 个电子, 除了与原有硅原子形成共价键用掉4 个电子外, 还多余一个处于游离状态的电子。在电场的作用下, 处于游离状态的电子就会逆着电场方向流动, 形成负电流。这类材料被称为N(Negative) 型材料。

3.PN结

PN结是由一个N型材料和一个P型材料紧密接触所构成的，其接触界面称为冶金结界面。

在一块完整的硅片上，用不同的掺杂工艺使其一边形成N型半导体，另一边形成P型半导体，我们称两种半导体的交界面附近的区域为PN结。

在P型半导体和N型半导体结合后，由于N型区内自由电子为多子，空穴几乎为零称为少子，而P型区内空穴为多子，自由电子为少子，在它们的交界处就出现了电子和空穴的浓度差。

由于自由电子和空穴浓度差的原因，有一些电子从N型区向P型区扩散，也有一些空穴要从P型区向N型区扩散。它们扩散的结果就使P区一边失去空穴，留下了带负电的杂质离子，N区一边失去电子，留下了带正电的杂质离子。开路中半导体中的离子不能任意移动，因此不参与导电。这些不能移动的带电粒子在P和N区交界面附近，形成了一个空间电荷区，空间电荷区的薄厚和掺杂物浓度有关。

在空间电荷区形成后，由于正负电荷之间的相互作用，在空间电荷区形成了内电场，其方向是从带正电的N区指向带负电的P区。显然，这个电场的方向与载流子扩散运动的方向相反，阻止扩散。

另一方面，这个电场将使N区的少数载流子空穴向P区漂移，使P区的少数载流子电子向N区漂移，漂移运动的方向正好与扩散运动的方向相反。从N区漂移到P区的空穴补充了原来交界面上P区所失去的空穴，从P区漂移到N区的电子补充了原来交界面上N区所失去的电子，这就使空间电荷减少，内电场减弱。因此，漂移运动的结果是使空间电荷区变窄，扩散运动加强。

最后，多子的扩散和少子的漂移达到动态平衡。在P型半导体和N型半导体的结合面两侧，留下离子薄层，这个离子薄层形成的空间电荷区称为PN结。PN结的内电场方向由N区指向P区。在空间电荷区，由于缺少多子，所以也称耗尽层。

从PN结的形成原理可以看出，要想让PN结导通形成电流，必须消除其空间电荷区的内部电场的阻力。

很显然，给它加一个反方向的更大的电场，即P区接外加电源的正极，N区接负极，就可以抵消其内部自建电场，使载流子可以继续运动，从而形成线性的正向电流。而外加反向电压则相当于内建电场的阻力更大，PN结不能导通，仅有极微弱的反向电流（由少数载流子的漂移运动形成，因少子数量有限，电流饱和）。

当反向电压增大至某一数值时，因少子的数量和能量都增大，会碰撞破坏内部的共价键，使原来被束缚的电子和空穴被释放出来，不断增大电流，最终PN结将被击穿（变为导体）损坏，反向电流急剧增大。

这就是PN结的特性：单向导通、反向饱和漏电或击穿导体，二极管就是基于PN结的单向导通原理工作的；而一个PNP结构则可以形成一个三极管，里面包含了两个PN结。

4.NMOS 和PMOS 晶体管

当非4 价元素掺杂的含量较小时, 产生的电子和空穴也就比较少, 用-号表示; 当非4 价元素掺杂的含量较大时,产生的电子和空穴也就比较多, 用号表示。

因此, P- 表示掺杂浓度低的P 型材料, 里面只有少量的空穴;

N 表示掺杂浓度高的N 型材料, 里面有大量电子。

MOS 晶体管是由多层摞放在一起的导电和绝缘材料构建起来的。每个晶体管的底部叫作衬底, 是低浓度掺杂的半导体硅。

晶体管的上部接出来3 个信号端口, 分别称为源极(Source)、漏极(Drain) 和栅极(Gate)。

源极和漏极叫作有源区, 该区域内采用与衬底相反极性的高浓度掺杂。

衬底是低浓度P 型掺杂, 有源区是高浓度N 型掺杂的MOS 晶体管叫作NMOS 晶体管; 衬底是低浓度N 型掺杂, 有源区是高浓度P 型掺杂的MOS 晶体管叫作PMOS晶体管。

无论是NMOS 管还是PMOS 管, 其栅极与衬底之间都存在一层绝缘体, 叫作栅氧层,其成分通常是二氧化硅(SiO2)。不过最新的工艺又有重新采用金属栅极的。

MOS的工作原理

我们先以NMOS 晶体管为例介绍MOS 晶体管的工作原理。

如果单纯在源极、漏极之间加上电压, 两极之间是不会有电流流过的, 因为源极和漏极之间相当于有一对正反相对的PN 结。如果先在栅极上加上电压, 因为栅氧层是绝缘的, 就会在P 衬底里形成一个电场。栅极上的正电压会把P 衬底里面的电子吸引到栅氧层的底部, 形成一个很薄的沟道电子层, 相当于在源极和漏极之间架起了一座导电的桥梁。此时如果再在源极、漏极之间加上电压, 那么两极之间的电流就能流过来了。

总结下来就是：NMOS 晶体管的工作行为就是: 在栅极上加上电就通, 不加电就断。

PMOS 晶体管的工作行为与NMOS晶体管的恰好相反, 加上电就断, 不加电就通。这样我们可以简单地把MOS 晶体管当作开关。

NMOS 晶体管是栅极电压高时打开, 栅极电压低时关闭; PMOS 晶体管反过来, 栅极电压低时打开, 栅极电压高时关闭。

随着工艺的发展, MOS晶体管中栅氧层的厚度越来越薄, 使得开启所需的栅极电压不断降低。晶体管的工作电压从早期工艺的5. 0V, 降到后来的2. 5V、1. 8V, 现在都是1V 左右或更低。尽管MOS 晶体管可以表现出开关的行为, 但是单纯的PMOS 晶体管或者NMOS 晶体管都不是理想的开关。例如, NMOS 晶体管适合传输0 而不适合传输1; PMOS 晶体管恰好相反, 适合传输1 而不适合传输0。

5. 从CMOS到逻辑门

我们先了解一下非门，也就是通常说的反相器。

非门由一个P管和一个N管组成, 其中P管的源极接电源, N管的源极接地, 两管的漏极连在一起作为输出, 栅极连在一起作为输入。

如果输入为0 (接地), 则P 管导通, N 管关闭, P 管的电阻为很小，N 管的电阻无穷大, 输出端的电压就是电源电压Vdd。反之, 当输入为1 的时候, N 管导通, P 管关闭, N 管的电阻为很小, P 管的电阻无穷大, 输出端与电源断开, 与地导通, 输出端电压为0。

以上就是反相器CMOS 电路的工作原理。

从反相器的工作原理可以看出CMOS 电路的基本特征, 其关键就在“C” (Complementary,互补) 上, 即由上下两个互补的部分组成电路。

了解了非门的原理，或门和与门也就清楚了，读者可以分析一下以下这个电路，看看实现了个什么功能。

与或非门类似于红绿蓝三原色一样，简单的三个颜色就可以组成五彩缤纷的世界，同样，有了与或非门，我们就可以搭建出功能丰富的电路。

6.从逻辑门到触发器

在真正开始搭建复杂的电路之前，我们先需要了解一点布尔代数的基础知识。

常用的布尔代数运算定律有:

•恒等律: A 0=A, A & 1=A;

• 0/1 律: A 1=1, A & 0=0;

•互补律: A ( ~A)= 1, A & ( ~A)= 0;

•交换律: A B =B A, A & B =B & A;

•结合律: A (B C)= (A B) C, A & (B & C)= (A& B) & C;

•分配律: A &(B C)= (A & B) (A & C), A (B& C)= (A B) & (A C);

•德摩根(DeMorgan) 定律: ~(A & B)= (~A) (~B), ~(A B)= (~A) & (~B)。

上述定律虽然很简单, 但使用起来变化无穷。

根据电路是否具有数据存储功能, 可将数字逻辑电路分为组合逻辑电路和时序逻辑电路两类。

组合逻辑电路，其实就是上面我们提到的与或非门。

R	S	Q	Q_n
0	0	NC	NC
0	1	1	0
1	0	0	1
1	1	Q	Q_n

RS锁存器真值表

时序电路多由锁存器构成

首先介绍RS 锁存器。RS 锁存器包含置位端S(Set) 和复位端R(Reset)两个输入端口, R 为0、S 为1 时置输出为1, R 为1、S 为0 时输出为0。

在图中, 下面与非门的输出接到上面与非门的一个输入, 同样上面与非门的输出接到下面与非门的一个输入, 通过两个成蝶形连接的与非门构成RS 锁存器。

RS 锁存器与组合逻辑的不同在于, 当(R, S) 的值从(0, 1) 或(1, 0) 变成(1, 1) 时能够保持输出值的状态不变, 从而实现数据的存储。

组合的输出只跟输入相关; 但是RS 锁存器的输入变了, 它的输出还能保持原来的值。

在RS 锁存器前面连接上两个与非门, 再用时钟C(Clock) 控制D 输入就构成了如下图所示的电路。

当C =0 时, R 和S 都为1, RS 锁存器处于保持状态, 也就是说当时钟处于低电平时, 无论输入D 怎样变化, 输出都保持原来的值。

当C = 1 时, 输出Q 与输入D 值相同, 相当于直通。这就是D 锁存器(D Latch) 的原理, 通过时钟C 的电平进行控制, 高电平输入,低电平保持。

两个D 锁存器以图中所示的方式串接起来就构成了一个D 触发器(D Flip-Flop)。

当C =0 时, 第一个D 锁存器直通, 第二个D 锁存器保持;

当C =1 时, 第一个D 锁存器保持, 第二个D 锁存器直通; C 从0 变为1 时, D 的值被锁存起来。

这就是D 触发器的基本原理, 它是通过时钟的边沿进行数据的锁存。

实际情况下, 由于器件中电流的速度是有限的, 并且电容充放电需要时间, 所以电路存在延迟。为了保证D 触发器正常工作, 需要满足一定的延迟要求。

例如为了把D 的值通过时钟边沿锁存起来, 要求在时钟变化之前的某一段时间内D 的值不能改变, 这个时间叫作建立时间(Setup Time)。另外, 在时钟跳变后的一段时间内, D 的值也不能变, 这个时间就是保持时间(Hold Time)。

建立时间和保持时间可以是负数。

此外D 触发器还有一个重要的时间参数叫作Clock-to-Q 时间, 也就是时钟边沿到来后Q 端数据更新为新值的时间。D 触发器整个的访问延迟是建立时间加上Clock-to-Q 时间。

在用CMOS 电路实现D 触发器时, 我们也可以利用CMOS 的逻辑门搭建出RS 锁存器, 进而搭建出D 锁存器, 并最终得到D 触发器。但是考虑到构建D 触发器时真正需要的是开关电路和互锁电路,所以这种构建D 触发器的方式消耗的资源过多。

下图中给出现代计算机中常用的一种D触发器电路结构。

该电路的左边(虚线框内部) 可以视作一个去除了输出缓冲器的D 锁存器, 该锁存器存储的值体现在其内部N1 点的状态。

当CLK = 0, CLK = 1 时, 传输门G1 开启、G2 关闭, D 点的值经由反相器I1 和传输门G1 传递进来, 并通过反相器I2 和三态反相器T1 反馈至N1 点, 使该点到达一个稳定状态。

当CLK = 1, CLK = 0 时, 传输门G1 关闭、G2 开启, D 点值的变化不再影响到内部N1 点, 同时N1 点的状态经由传输门G2, 并通过反相器I3 和三态反相器T2 反馈至N2 点, 使N2 点处于稳定状态, 并将该值传递至输出端Q。

CMOS的延迟

真实世界中, PMOS 晶体管和NMOS 晶体管即便是在导通状态下源极和漏极之间也是有电阻的, 栅极和地之间也存在寄生电容。

因此CMOS 电路工作时输入和输出之间存在延迟, 该延迟主要由电路中晶体管的RC 参数来决定。

下图是一个CMOS 反相器的示意图。其输出端有一个对地电容, 主要由本身P 管和N管漏极的寄生电容、下一级电路的栅电容以及连线电容组成。

反相器输出端从0 到1 变化时,需要通过P 管的电阻对该电容充电;

从1 到0 变化时, 该电容的电荷需要通过N 管的电阻放电到地端。

图中示意了输出电容的充放电过程, 其中左图代表充电过程, 右图代表放电过程。

因此, 该反相器输出从0 到1 变化时的延迟由P 管打开时的电阻和输出电容决定;

从1 到0 变化时的延迟由N 管打开时的电阻和输出电容决定。

从中可以看出, 反相器从输入到输出的变化是有延迟的, 而且反相器的输出不是理想的矩形, 而是存在一定的斜率。

对于深亚微米及纳米工艺,晶体管的负载延迟不再与负载呈线性关系。在工艺厂家给出的单元延迟模型中, 通常通过一个二维表来描述每个单元的延迟, 其中一维是输入信号的斜率, 另外一维是输出负载。即一个单元的延迟是由输入信号的斜率和输出负载两个值通过查表得到的。

了解了逻辑门的实现之后，在设计加法器前需要储备一点关于补码的知识。

7.原码与补码器

(1) 原码

数的原码表示采用“符号-数值”的表示方式, ,最高位是符号位, 0 表示正数, 1 表示负数; 其余位表示数值的绝对值。

原码表示有两大优点:

1) 与人们日常记录正负数的习惯接近, 与真实数值之间的对应关系直观, 利于与真实数

值相互转换。

2) 原码实现乘除运算比较简便直接。

但是原码表示亦存在两个缺点:

1) 存在两个0, 即一个 0, 一个-0。这不仅有悖于人们的习惯, 也给使用带来不便。

2) 原码的加减运算规则复杂, 这对于逻辑实现的影响很大。在进行原码加减运算时, 需

要首先判断是否为异号相加或同号相减的情况, 如果是的话则必须先根据两个数的绝对值的大小关系来决定结果的正负号, 再用绝对值大的数减去绝对值小的数。

权衡上述利弊, 现代计算机中基本不使用原码来表示整数。原码仅在表示浮点数的尾数部分时采用。

(2) 补码

现代计算机中基本都是采用补码来表示整数。它最大的好处就是可以用加法来完成减法运算, 实现加减运算的统一。

这恰好解决了原码表示所存在的最大问题。

在补码表示中, 其最高位同原码一样也作为符号位, 0 表示正数, 1 表示负数。

补码表示和原码表示的差异在于其数值的计算方法。

求一个数的补码是个取模运算。这里举一个最为常见的模运算系统的例子———时钟。这个模系统的模数为12。

假定现在时钟指向6 点, 需要将它拨向10 点, 那么你有两种拨法,

一种是顺时针向前拨4 个小时, 另一种是逆时针向后拨8 个小时。

这种相同的效果用数学的语言来说即4≡-8(mod12)。

基于模运算系统的概念, 对于具有1 位符号位和n-1 位数值位的n 位二进制整数的补码来说, 其补码的定义是:

[X] 补= 2n X(mod 2n ), - 2n -1 ≤ X < 2n -1

利用补码基于模运算的这个特点, 可以把减法转换成加法来做。

原码和补码之间的转换方法:

最高位为0 时, 原码与补码相同;

最高位为1 时, 原码的最高位不变, 其余位按位取反后末位加1。

加法溢出的判断方法是: 如果A 和B 的最高位一样, 但是A B 结果的最高位与A 和B 的最高位不一样, 表示溢出, 即两个正数相加得到负数, 或两个负数相加得到正数。

减法溢出的判断方法类似, 即负数减正数结果是正数, 或正数减负数结果是负数, 这就表示溢出。

知道了补码之后，我们就可以开始着手设计加法器了，不过一口吃不成胖子，我们先从最简单的1bit的加法器开始。

8.加法器

一位全加器

一位全加器是构成加法器的基本单元。

一位全加器实现两位本地二进制数以及低位的进位位相加, 求得本地和以及向高位的进位。

它有3个1 位二进制数输入A、B 和Cin, 其中A 和B分别为本地的加数和被加数, Cin 为低位来的进位。

它有2个1 位二进制数输出S 和Cout, 其中S 是本地和, Cout 是向高位的进位。

A	B	Cin	S	Cout
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

1bit全加器真值表

根据真值表, 可以写出全加器的逻辑表达式如下:

S = (~ A & ~ B & Cin) | (~ A & B& ~ Cin) | (A & ~ B & ~ Cin) | (A & B & Cin)

Cout = (A & B) | (A & Cin) | (B &Cin)

上述表达式还可以简单解释为: 当输入的三个数中有奇数个1 时, 本地和为1; 当输入的三个数中有两个1 时, 向高位的进位为1。

用非门和与非门搭建的一位全加器的逻辑电路图，如果我们不严格区分非门和与非门, 以及不同数目输入与非门之间的延迟差异,则可近似认为每个一位全加器需要2 或3 级的门延迟。

行波进位加法器

构建N 位带进位加法器的最简单的方法是将N 个一位全加器逐个串接起来。

其中输入A =a31…a0 和B =b31…b0 分别是加数和被加数, Cin是最低位的进位; 输出为和S =s31…s0 以及最高位向上的进位Cout。

所谓“行波”, 是指每一级的一位全加器将来自低位的一位全加器的进位输出Cout 作为本级的进位输入Cin, 如波浪一般层层递进下去。

这种串行的进位传递方式与人们日常演算十进制加法时采用的进位方式原理一样, 非常直观。

但是, 这种加法器的电路中每一位的数据相加都必须等待低位的进位产生之后才能完成, 即进位在各级之间是顺序传递的。

回顾一下上文关于一位全加器的延迟的大致估算, 可知一位全加器输入到S 的最长延迟是3 级门、输入到Cout 的最长延迟是2 级门。

因此,32 位行波进位加法器中, 从最低位的输入A0、B0、Cin 到最高位的进位输出Cout 存在一条进位链, 其总延迟为2×32=64 级门; 从最低位的输入A0、B0、Cin 到最高位的进位输入Cin 的延迟为2×31=62 级门, 所以从最低位的输入A0、B0、Cin 到最高位的加和S31 的总延迟为62 3= 65级门。

从这个例子可以看出, 虽然行波进位加法器直观简单, 但是其延迟随着加法位数N 的增加而线性增长, N 越大时, 行波进位加法器的延迟将越发显著。

先行进位加法器

为了改进行波进位加法器延迟随位数增加增长过快的缺点, 人们提出了先行进位加法器的电路结构。其主要思想是先并行地计算每一位的进位, 由于每一位的进位已经提前算出, 这样计算每一个的结果只需要将本地和与进位相加即可。下面详细介绍先行进位(或者说并行进位) 加法器的设计原理。

(1) 并行进位逻辑

假设两个N 位数A 和B 相加。

定义第i 位的进位输入为ci , 进位输出为ci 1, 且将加法器的输入Cin 记作c0 以方便后面描述的统一。每一位进位输出ci 1 的计算为:

ci 1 = (ai & bi) | (ai & ci) | (bi& ci) = (ai & bi) | (ai | bi ) & ci

设gi =ai & bi , pi =ai bi , 则ci 1 的计算可以表达为:

ci 1 = gi | (pi & ci)

从上式可以看出, 当gi =1 时, 在ci 1 必定产生一个进位, 与ci 无关; 当pi = 1 时, 如果ci有一个进位输入, 则该进位可以被传播至ci 1。我们称gi 为第i 位的进位生成因子, pi 为第i 位的进位传递因子。

下面以4 位加法器的进位传递为例, 根据公式ci 1 =gi pi & ci 逐级展开可得到:

c1 = g0 | (p0 & c0)

c2 = g1 | p1 & g0 | p1 & p0 & c0

c3 = g2 | p2 & g1 | p2 & p1 & g0 | p2& p1 & p0 & c0

c4 = g3 | p3 & g2 | p3 & p2 & g1 | p3& p2 & p1 & g0 | p3 & p2 & p1 & p0 & c0

扩展之后, 每一位的进位输出ci 1 可以由仅使用本地信号生成的g 和p 直接得到, 不用依赖前一位的进位输入ci 。下图给出了4 位先行进位的逻辑电路图及其示意图。从中可以看出, 采用先行进位逻辑, 产生第4 位的进位输出只需要2 级门延迟, 而之前介绍的行波进位逻辑则需要8 级门延迟, 先行进位逻辑的延迟显著地优于行波进位逻辑。

当然, 这里为了电路逻辑的简洁以及计算的简便, 我们使用了四输入、五输入的与非门, 这些与非门的延迟比行波进位逻辑中采用的二输入、三输入的与非门的延迟要长, 但我们不再做进一步细致的区分, 均视作相同延迟。

实际实现时很少采用五输入的与非门, 其N 管网络上串接五个NMOS 管, 电阻值较大, 电路速度慢。

4bit先行进位逻辑

(2) 块内并行、块间串行逻辑

理论上可以把上述并行进位方法扩展成更多位的情况, 但那需要很多输入的逻辑门, 在实现上是不现实的。实现更多位的加法器时通常采用分块的进位方法, 将加法器分为若干个相同位数的块, 块内通过先行进位的方法计算进位, 块间通过行波进位的方法传递进位。下图给出了16 位加法器中采用该方式构建的进位逻辑。由于块内并行产生进位只需要2 级门延迟,因此从pi 和gi 产生c16 最多只需要8 级门延迟, 而非行波进位逻辑的32 级门延迟。

(3) 块内并行、块间并行逻辑

为了进一步提升加法器的速度, 可以在块间也采用先行进位的方法, 即块内并行、块间也并行的进位实现方式。与前面类似, 对于块内进位, 定义其进位生成因子为g 和进位传递因子为p, 对于块间的进位传递, 定义其进位生成因子为G 和进位传递因子为P, 则其表达式如下:

P = p3 & p2 & p1 & p0

G = g3 | p3 & g2 | p3 & p2 & g1 | p3& p2 & p1 & g0

上面的表达式可以解释为, 当G 为1 时表示本块有进位输出生成, 当P 为1 时表示当本块有进位输入时该进位可以传播至该块的进位输出。图中给出了包含块间进位生成因子和进位传递因子的4 位先行进位的逻辑电路及其示意图。

含有块间进位生成因子和进位传递因子的4 位先行进位逻辑

定义上述的块间进位生成因子和进位传递因子是因为这种逻辑设计具有很好的层次扩展性, 即以层次化的方式构建进位传递逻辑, 把下一级的P 和G 输出作为上一级的pi 和gi 输入。

下面给出了一个采用两层并行进位结构的16 位先行进位逻辑, 采用了5 块4 位先行进位逻辑。其计算步骤是:

1) 下层的4 块4 位先行进位逻辑根据各块所对应的pi 和gi 生成各自的块间进位生成因子G 和块间进位传递因子P;

2) 上层的4 位先行进位逻辑把下层的先行进位逻辑生成的P 和G 作为本层的pi 和gi 输入, 生成块间的进位c4、c8 和c12;

3) 下层的每块4 位先行进位逻辑分别把c0 以及上层计算出的c4、c8 和c12 作为各自块的进位输入c0, 再结合本地的pi 和gi 分别计算出本块内部所需要的每一位进位。

可以看出, 从pi 和gi 生成下层各块的P、G 需要2 级门延迟, 上层根据自身pi 和gi 输入生成进位输出c1 ~c3 需要2 级门延迟, 下层各块从c0 输入至生成进位输出c1 ~c3 也需要2 级门延迟。所以整体来看, 从pi 和gi 生成进位c1 ~ c16 最长的路径也只需要6 级门延迟, 这比前面介绍的块内并行但块间串行的电路结构更快。而且进一步分析可知, 块间并行的电路结构中,最大的与非门的扇入为4, 而前面分析块间串行电路结构延迟时, 那个电路中最大的与非门的扇入为5。

这种块间并行的电路结构在设计更多位的加法器时, 只需要进一步进行层次化级联就可以。例如, 仍采用4 位先行进位逻辑作为基本块, 通过3 层的树状级联就可以得到64 位加法器的进位生成逻辑, 其从pi 和gi 输入到所有进位输出的最长路径的延迟为10 级门。采用块内并行且块间并行的先行进位逻辑所构建的加法器, 其延迟随着加法位数的增加以对数的方式增长, 因而被广泛采用。

9.减法运算实现

在前面我们提到, 计算机中定点数都是用补码表示的。补码表示的一个显著优点就是补码的减法可以通过补码加法来实现, 即补码运算具有如下性质:

[A] 补- [B] 补= [A - B] 补= [A] 补 [ - B] 补

而[-B]补可以通过将[B]补“按位取反, 末位加1”的法则进行计算。

所以, 只需要将被减数直接接到加法器的A 输入, 减数按位取反后接到加法器的B 输入, 同时将加法器的进位输入Cin 置为1, 就可以用加法器完成[A]补-[B]补的计算了。

10.乘法器

对于定点乘法器而言, 最简单的实现方式就是通过硬件来模拟软件的迭代操作, 这种乘法实现方式被称为移位加。

以两个8 位数的乘法为例, 乘法器的输入包括一个8 位的乘数和一个8 位的被乘数, 输出则是16 位的乘法结果。通过触发器将这3 个数存储下来, 并执行以下步骤:

1) 最初时, 将乘法结果设置为0。

2) 在每个时钟周期, 判断乘数的最低位。如果值为1, 则将被乘数加到乘法结果; 如果值为0, 则不进行加法操作。此后将乘数右移1 位, 将被乘数左移1 位, 将参与运算的3 个数锁存, 进入下一个时钟周期。

3) 执行8 次操作, 得到正确的乘法结果。

实现上述移位加算法需要的硬件很简单, 组合逻辑延迟也较小, 缺点是完成一条乘法需要很多个时钟周期, 对于64 位的乘法而言就需要64 拍。但是, 上述算法是将操作数视为一个无符号二进制数来设计的, 如果计算的输入是补码形式, 那么就需要先根据输入的正负情况判断出结果的符号位, 随后将输入转换为其绝对值后进行上述迭代运算, 最后再根据结果符号位转换回补码形式。

很显然这样操作略显复杂, 有没有直接根据补码形式进行运算的方法呢?

计算机中的定点数都是按照补码形式来存储的,并且具有[X]补 [Y]补=[X Y]补的特性。那么, 应该如何计算[X×Y]补呢? 是否可以简单地将[X]补与[Y]补相乘得到呢?

还是以8 位乘法为例。假定有8 位定点数Y, [Y]补的二进制格式写作y7y6y5y4y3y2y1y0, 根据补码定义, Y 的值等于:

Y = - y7 × 2^7 y6 × 2^6 y5 × 2^5 … y1 × 2^1 y0 × 2^0

由此推出:

[X × Y] 补= [X × ( - y7 × 2^7 y6 × 2^6 … y1 × 2^1 y0 × 2^0)] 补

= [X × - y7 × 2^7 X × y6 × 2^6 … X × y1 × 2^1 X × y0 × 2^0] 补

根据补码加法具有的特性, 有:

[X × Y] 补= [X × - y7 × 2^7] 补 [X × y6 × 2^6] 补 … [X × y0 × 2^0] 补

需要注意, 这个公式中位于方括号外的加法操作为补码加法, 而之前两个公式中位于方括号内部的加法为算术加法。由于yi 只能取值为0 或者1, 再根据补码减法的规则, 继续推导公式, 有:

[X × Y] 补= - y7 × [X × 2^7] 补 y6 × [X × 2^6] 补 … y0 × [X × 2^0] 补

公式中最开头的减号是补码减法操作。为了继续运算, 需要引入一个定理:

[X × 2^n ] 补= [X] 补× 2^n

该定理的证明可以较容易地根据补码的定义得出, 留作本章的课后习题。据此定理, 补码乘法的公式可以继续推导如下:

[X × Y] 补= - [X] 补× (y7 × 2^7) [X] 补× (y6 × 2^6) … [X] 补× (y0 × 2^0)

= [X] 补× ( -y7 × 2^7 y6 × 2^6 … y0 × 2^0)

最后得到的公式与移位加算法的原理很类似, 但是存在两个重要区别:

第一, 本公式中的加法、减法均为补码运算;

第二, 最后一次被累加的部分积需要使用补码减法来操作。

这就意味着[X]补× [Y]补不等于[X×Y]补。

注意在补码加法运算中, 需要进行8 位的符号位扩展, 并仅保留8 位结果。

11.Booth乘法器

Booth 乘法器由英国的Booth 夫妇提出。按照上面提到的补码乘法算法, 需要特地挑出第N 个部分积, 并使用补码减法操作, 这就需要实现一个额外的状态机来控制, 增加了硬件设计复杂度。因此他们对补码乘法公式进行变换, 试图找到更适合于硬件实现的算法。

其中的取值方式，如表所示。

表部分积编码表


0	0	0	0
0	0	1	X
0	1	0	X
0	1	1	2X
1	0	0	-2X
1	0	1	-X
1	1	0	-X
1	1	1	-0

这样每次交叠检验3位，每个部分积对应2bit数，使部分积减少一半，从而降低了硬件开销，并提高了运算速度。对于补码表示的二进制数，进行符号扩展并不会影响计算结果，这样我们就可以实现有符号数和无符号数乘法器的逻辑共享。

注意算法开始时, 要隐含地在乘数最右侧补一个0。

接下来将介绍这个算法的电路实现方式。

Booth 乘法的核心是部分积的生成, 共需要生成N /2 个部分积。每个部分积与[X]补相关,总共有-X、-2X、 X、 2X 和0 五种可能, 而其中减去[X]补的操作, 可以视作加上按位取反的[X]补再末位加1。为了硬件实现方便, 将这个末位加1 的操作提取出来, 假设[X]补为被乘数, 以及部分积P:

当部分积的选择为2X 时, 可以视作X 输入左移1 位, 此时pi 就与xi -1 相等。如果部分积的选择是-X 或者-2X, 则此处对xi 或者xi -1 取反, 并设置最后的末位进位c 为1。

根据上述规则, 经过卡诺图分析, 可以得出P的每一位的逻辑表达式:

其中信号在部分积选择为 X 时为1, 其他情况为0; 另外三个S 信号含义类似。画出pi 的逻辑图, 如下图所示。

下文将使用上面的小示意图来代表的生成逻辑。生成逻辑中需要使用部分积选择信号, 因此还需要考虑如何根据、和三个信号生成图中用到的4 个选择信号。

根据部分积编码表, 很容易通过卡诺图化简得到:

将两部分组合起来, 形成每个Booth部分积的逻辑图, 并得到如图所示的示意图。

这个逻辑就是两位Booth 乘法的核心逻辑。调用该逻辑, 并通过移位加策略实现两位Booth补码乘的结构,如图。

乘法操作开始时, 乘数右侧需要补1 位的0,而结果需要预置为全0。在每个时钟周期的计算结束后, 乘数算术右移2位, 而被乘数左移2位, 直到乘数为全0时, 乘法结束。对于N位数的补码乘法, 操作可以在N/2 个时钟周期内完成, 并有可能提前结束。在这个结构中, 被乘数、结果、加法器和Booth 核心的宽度都为2N 位。

12.华莱士树

即使采用了Booth两位乘算法, 使用移位加策略来完成一个64 位的乘法操作也需要32 个时钟周期,并且不支持流水操作, 即第一条乘法全部完成之后才能开始计算下一条。现代处理器通常可以实现全流水、4 个时钟周期延迟的定点乘法指令, 其核心思想就是将各个部分积并行地加在一起, 而非串行迭代累加。以64 位数据的乘法为例, 共有32个部分积, 如果按照二叉树方式来搭建加法结构, 第一拍执行16个加法, 第二拍执行8个加法, 以此类推,就可以在5 个时钟周期内结束运算。这个设计还支持流水式操作: 当上一条乘法指令到达第二级, 此时第一级的16个加法器已经空闲, 可以用来服务下一条乘法指令了。这种设计的硬件开销非常大, 其中128位宽度的加法器就需要31 个,而用于锁存中间结果的触发器更是接近4000 个。

下面将要介绍的华莱士树(Wallace Tree) 结构可以大幅降低多个数相加的硬件开销和延迟。

华莱士树由全加器搭建而成。

S = ~ A & ~ B & C | ~ A & B & ~C | A & ~ B & ~ C | A & B & C

C = A & B | A & C | B & C

全加器可以将3个1 位数A、B、C的加法转换为两个1 位数S和C 的错位加法:

A B C = S (C < < 1)

如果参与加法的数据较宽, 可以通过调用多个全加器将3 个数的加法转换为两个数的加法。其中4 位数A的二进制表示为A3A2A1A0, 可以很容易得知:

{A3A2A1A0} {B3B2B1B0} {D3D2D1D0} ={S3S2S1S0} {C2C1C00}

公式中所有加法都为补码加法, 操作宽度为4位, 结果也仅保留4位的宽度, 这也导致C3位没有被使用, 而是在C0右侧再补一个0 参与补码加法运算。

那么问题来了,如果需要相加的数有4 个,又应该如何呢? 很自然地想到,可以先将其中3 个数相加,再调用一层全加器结构, 将刚得到的结果与第4 个数相加即可。不过要注意, 全加器的C输出需要左移1 位才能继续参与运算。如下图所示。

最后结果中,最高位进位C3 和C′3 都不会被使用。第二级的最右侧全加器需要在其中一个输入位置补0 参与运算。从图中可以看出, 整个结构呈现重复特征, 提取出圆角矩形框选中的部分, 这部分称为一位华莱士树。准确地说, 图中灰色部分呈现的是4 个数相加的一位华莱士树结构, 它除了输入的4个被加数、输出的C 与S之外, 还有级联的进位信号。通过M个这样的一位华莱士树, 就可以实现4个M 位数的相加。

可以简单地计算一下使用华莱士树进行相加的优势。根据上图的结构, 4 个数相加的华莱士树需要两层全加器, 当前位的进位信号在第一层产生, 并接到了下一位的第二层, 这意味着Cout与Cin 无关。全加器的S 输出需要3级门延迟, 而C输出需要2 级门延迟,因此不论参与加法的数据宽度是多少位, 将4个数相加转换为两个数相加最多只需要6 级门延迟,最后把这两个数加起来还需要一个加法器。整套逻辑需要一个加法器的面积, 再加上两倍数据宽度个全加器的面积。如果不使用华莱士树, 而是先将四个数捉对相加, 再把结果相加,计算的延迟就是两倍的加法器延迟, 面积则是3倍的加法器面积。对于64 位或者更宽的加法器, 它的延迟肯定是远远超过6 级门的,面积也比64 个全加器要大得多。

因此使用华莱士树进行多个数相加可以明显地降低计算延迟, 数据宽度越宽,其效果越明显。可以归纳出, 使用华莱士树进行M 个N位数相加, 可以大致降低延迟log N 倍,而每一层华莱士树包含的全加器个数为M′/ 3 (M′是当前层次要加的数字个数)。

回到最开始的问题, Booth 乘法需要实现N/2 个2N 宽度的部分积相加, 如果可以先画出N /2 个数的一位华莱士树结构, 通过2N次使用, 就可以达到这个要求。

通过华莱士树可以用4 级全加器即12级门的延迟把8 个数转换成两个数相加。

华莱士树的精髓在于: 通过连线实现进位传递, 从而避免了复杂的进位传递逻辑。

不过需要指出的是, 在华莱士树中,每一级全加器生成本地和以及向高位的进位, 因此在每一级华莱士树生成的结果中, 凡是由全加器的进位生成的部分连接到下一级时要连接到下一级的高位。

为了构成一个16位定点补码乘法器, 需要使用8个Booth 编码器,外加32 个8个数相加的一位华莱士树, 再加上一个32位加法器。

值得注意的是,根据上一节提出的Booth 乘法核心逻辑,除了有8 个部分积需要相加之外, 还有8个“末位加1”的信号。

在华莱士树中,最低位对应的华莱士树上有空闲的进位输入信号, 共有6 个进位输入,可以接上6 个“末位加1”的信号。

还剩下两个“末位加1”的信号, 只能去最后的加法器上想办法: 最后的加法器负责将华莱士树产生的2N 位的C和S 信号错位相加,其中C 信号左移一位低位补0。

据此设计,这两个“末位加1”的信号可以一个接到加法器的进位输入上, 另一个接到C左移后的补位上。

最终的乘法器示意图如下图所示。

图中间标注为switch的部分, 负责收集8个Booth 核心生成的8个32 位数,进行类似矩阵转置的操作, 重新组织为32组8 个一位数相加的格式, 输出给华莱士树, 并将Booth核心生成的8 个“末位加1”信号从switch部分右侧接出, 提供给华莱士树最右侧的一位树及最后的加法器。此外图中没有画出的是, 被乘数X送到8 个Booth编码器时需要先扩展到32 位,并按照编码器所处的位置进行不同偏移量的左移操作。