Chapter 12 Arithmetic

现代处理器架构风格：

• Pipelined, single issue 流水线、单发射

• Pipelined, hardware controlled multiple issue – superscalar 流水线、硬件控制的多发射，即超标量处理器

• Pipelined, software controlled multiple issue – VLIW 流水线、软件控制的多发射，即 VLIW 超长指令字架构

• Pipelined, multiple issue from multiple process threads – multithreaded流水线、来自多个进程线程的多发射，即多线程处理器

• 数据通路是处理器的核心

• 处理器基本构建模块

1. 数据通路 Datapath

• 执行单元：加法器、乘法器、除法器、移位器等

  • 寄存器堆和流水线寄存器

  • 多路选择器、译码器

2. 控制器 Control：有限状态机：PLA、ROM、随机逻辑等

3. 互连 Interconnect：开关、仲裁器、总线

4. 存储器 Memory：Cache、TLB、DRAM、缓冲器等

• 数据通路常常组织成位片式结构（bit-sliced）。例如一个32位处理器对一个32位宽的数据字进行操作时，处理器有32个位片，每一个对一位进行操作，位片之间完全相同或结构类似。

• A、B 是加法器的输入，$C_i$$C_i$ 是进位输入，$S$$S$ 是和输出，$C_{out}$$C_{out}$ 是进位输出

• 全加器设计 I：根据公式进行“暴力式”直接实现，需要32个晶体管

• 全加器设计 II：静态互补 CMOS 全加器

• 核心思路；为了减少实现全加器的晶体管数量，希望 S 和 $C_{out}$$C_{out}$ 之间能共享部分实现电路。采用静态互补CMOS实现全加器需要28个晶体管，也消耗了较大的面积，速度也较慢，原因如下：

  • 在进位产生与和产生电路中堆叠着许多 PMOS 管。

  • $C_o$$C_o$ 信号的本征负载电容很大，包括两个扩散电容、6 个栅电容，再加上布线电容。

  • 在进位产生电路中信号传播通过两个反相级。正如前面提到的，最小化进位路径的延时是高速加法器电路设计者的首要目标。如果进位链输出上的负载（扇出）很小，那么有两个逻辑级就显得太多，因而引起额外的延时。

  • 和的产生要求一个额外的逻辑级，但这并不那么重要，因为这一项在逐位进位加法器的传播延时公式中只出现一次。

• 这一电路尽管慢，但却体现了某些聪明的设计技巧。注意，在进位产生电路第一个门的设计中 $C_i$$C_i$ 信号放在串联数较少的 PMOS 管支路上，从而使它的逻辑努力降低为 2。同时，连接到 $C_i$$C_i$ 的 NMOS 和 PMOS 管尽可能地放在靠近这个门的输出端。这直接应用了 4.2 节中讨论过的电路优化技术——关键路径上的晶体管应当尽可能放在接近门的输出端。例如在加法器的第 $k$$k$ 级，信号 $A_k$$A_k$ 和 $B_k$$B_k$ 在 $C_{i,k}(=C_{o,k-1})$$C_{i,k} (= C_{o,k-1})$ 到达之前就已经存在并已稳定了很长时间。因此，在晶体管链内部节点的电容事先已被预充电或放电。当 $C_{i,k}$$C_{i,k}$ 到达时，只有节点 X 的电容必须充(放)电。如果把 $C_{i,k}$$C_{i,k}$ 晶体管放在靠近 $V_{DD}$$V_{DD}$ 和 GND 处，则不仅需要充(放)电节点 X 的电容，而且也要充(放)电内部节点的电容。

• 定义三个只依赖于 $A$$A$、$B$$B$ 的变量来研究进位的行为

• 将 和 与 进位 表示为 $P$$P$、$G$$G$、$K(D)、C_i$$K(D)、 C_i$ 的函数

• 也可以推导出 $S(D,P),C_o(D,P)$$S(D,P),C_o(D,P)$

镜像加法器

• 分析镜像加法器的进位产生电路：

  1. 取消了进位反相门

  2. 门的 PDN 和 PUN 网络不再是对偶的，而是镜像对称的。巧妙地实现了进位传播/产生/取消功能

• 当 $D$$D$ 或者 $G$$G$ 为高时，${\bar{C}}_o$$\overline{C}_o$ 分别被置为 $V_{DD}$$V_{DD}$ 或 GND。当满足进位传播条件时，输入进位（以反相的形式）传播到 ${\bar{C}}_o$$\overline{C}_o$。

  • 该全加器单元仅需要 24 个晶体管。

  • NMOS 和 PMOS 链完全对称，由于求和与进位功能的自对偶性（self-duality），它同样能产生正确的功能。但这一结果使在进位产生电路中最多只有两个晶体管串联。

  • 连接 $C_i$$C_i$ 的晶体管放在最接近门的输出端处。

  • 只有在进位电路中的晶体管才需要优化尺寸以改善速度。在求和电路中的所有晶体管都可以采用最小尺寸。当设计该单元的版图时，最关键的问题是使节点 ${\bar{C}}_o$$\overline{C}_o$ 处的电容最小。共享扩散区可以减少堆叠（晶体管）的节点电容。

  • 在静态互补CMOS加法器中，可以独立确定反相器的尺寸来驱动下一级加法器的 $C_i$$C_i$ 输入。如果镜像加法器中的进位电路尺寸对称，则其每一个输入的逻辑努力为 2。这意味着优化尺寸以达到最小延时的最优扇出数应当为 $(4/2)=2$$(4/2)=2$。然而，这一级的输出驱动两个内部的栅电容和 6 个所连下一级加法器单元的栅电容。保持每一级晶体管尺寸相同的一个巧妙办法是把进位级的尺寸增加至大约为求和级尺寸的 3 至 4 倍。这仍保持优化扇出为 2。所得到的晶体管的尺寸标在图 11.6 中，这里假设 PMOS/NMOS 的比率为 2。

传输门加法器

• 传输门加法器的和与进位产生具有近似的延时

• 根据表达式，进位传播信号 $P$$P$ (输入 $A$$A$ 和 $B$$B$ 的 XOR)，用来选择输入进位值 $C_i$$C_i$ 的正信号或反信号作为新的和输出 $S$$S$

• 注意，这里进位产生电路直接接了 $\bar{A}$$\overline{A}$ （接 $\bar{B}$$\overline{B}$ 也行）,因为 P = 0 时说明 A 和 B 相同，能产生正确的 $C_o$$C_o$

• CPL：Complementary Pass Transistor Logic 互补传输管逻辑来实现全加器

• 速度略快；但是面积更大

逐位进位加法器

• The Ripple-Carry Adder 行波进位加法器，也叫串行进位加法器

• 串行进位加法器的延时与所加的输入信号有关，对于有些输入，完全不会发生行波进位效应，而对于另一些信号，进位必须从最低有效位（lsb）一直波动到最高有效位（msb）

• 最坏情况下的延迟与位数 N 成线性关系 $t_d=O(N)$$t_d = O(N)$，而且优化 $t_{carry}$$t_{carry}$ 比优化 $t_{sum}$$t_{sum}$ 重要的多

  $$\begin{array}{}\text{(}\text{1}\text{)}& t_{adder}=(N-1)t_{carry}+t_{sum}\end{array}$$

  其中：

  • $t_{carry}$$t_{carry}$：单级进位传播延迟；

  • $t_{sum}$$t_{sum}$：最终级和输出延迟；

  • $N$$N$：加法器位数

• 全加器的一个逻辑性质（也称为全加器的反向性质）：把一个全加器的所有输入反相，它的所有输出也反向

• 可以理解为：

  $$\begin{array}{}\text{(}\text{2}\text{)}& \bar{S}(A,B,C_i)=S(\bar{A},\bar{B},\overline{C_i})\end{array}$$

• 应用：减少不必要的反相器级数，提高全加器速度

• 利用加法器的反相特性，即把一个全加器单元的所有输入反相则它的所有输出也反相，这可以减少进位路径中反相级的数目。如上图所示，这一特性允许我们在一个进位链中消除反相器。

• 这里的 FA 的进位路径中没有反相器，从而减少关键路径上的逻辑级数，降低延迟

• 第 0 级：输入正常的 $A_0$$A_0$、$B_0$$B_0$ 和 $C_{i,0}$$C_{i,0}$，因为节省了输出级的反相器，输出的是反相的进位，即 $\overline{C_{o,0}}$$\overline{C_{o,0}}$，课本上和上图标注其实有点问题，注意，第 1 级输入的圈意思不是再次对$\overline{C_{o,0}}$$\overline{C_{o,0}}$ 取反，而是代表 “在逻辑设计上期望接收一个反相信号” 。

• 第 1 级：输入 $\overline{C_{o,0}}$$\overline{C_{o,0}}$、$\overline{A_1}$$\overline{A_1}$ 和 $\overline{B_1}$$\overline{B_1}$，本来应该输出$\overline{C_{o,1}}$$\overline{C_{o,1}}$ （但是这里 FA 的进位路径中没有反相器），因此输出 $C_{o,1}$$C_{o,1}$

• 最简单的设计方式：将多个全加器级联

  • 关键路径从 $C_{in}$$C_{in}$ 到 $C_{out}$$C_{out}$（也可能是 $C_{in}$$C_{in}$ 到 $S_4$$S_4$ )

  • 因此全加器设计时应重点优化进位延迟。

• 关键路径会经过“Majority Gate”（注意，这里的“多数门”是指进位逻辑本质上是一个Majority 函数）

  • “多数门”由“少数门”加反相器构成。

  • 可以去掉反相器，并使用反相全加器。

曼彻斯特进位链加法器

• 简化传输门型加法器中的进位电路：如果进位传播信号 ( $A_i\oplus B_i$$A_i \oplus B_i$) 为真，则 $C_i$$C_i$ 被传送至输出 $C_o$$C_o$。如果传播条件不满足，则输出或者由信号 $D_i$$D_i$ 下拉或者由 ${\bar{G}}_i$$\overline{G}_i$ 上拉。

• 动态实现甚至可以使电路更加简单。由于动态电路中的晶体管是单方向工作的，所以可以只用 NMOS 传输管来代替传输门。预充电输出使电路不再需要进位取消信号（对于进位链，传播的是进位信号的反信号时的情形）。

• 在预充电阶段 ( $\varphi =0$$\phi=0$)，传输管进位链中的所有中间节点都被预充电至 $V_{DD}$$V_{DD}$。在求值阶段，当有输入进位 ${\bar{C}}_{k-1}=0$$\overline{C}_{k-1}=0$ 且传播信号 $P_k$$P_k$ 为高电平时，或者当第 $k$$k$ 级的进位产生信号 ($G_k$$G_k$) 为高电平时，节点 $\overline{C_k}$$\overline{C_k}$ 放电。

进位旁路加法器（or进位跳跃加法器）

• 假设 $A_k$$A_k$ 和 $B_k$$B_k$ ( $k=0,\cdots ,3$$k=0, \cdots, 3$) 的值使所有的进位传播信号 $P_k$$P_k$ ( $k=0,\cdots ,3$$k=0, \cdots, 3$) 为高电平。在这一状况下，一个进位输入 $C_{i,0}=1$$C_{i,0}=1$ 传播通过整个加法器链并使进位输出 $C_{o,3}=1$$C_{o,3}=1$。换言之：

如果 ( $P_0{P}_1{P}_2{P}_3=1$$P_0P_1P_2P_3=1$)，则 $C_{o,3}=C_{i,0}$$C_{o,3}=C_{i,0}$，否则发生进位消除或进位产生

• 因此，当 $BP=P_0{P}_1{P}_2{P}_3=1$$BP=P_0P_1P_2P_3=1$ 时，设计进位输入通过旁路晶体管 $M_b$$M_b$ 立即送至下一个模块，因而称之为进位旁路加法器 (carry-bypass adder) 或进位跳越加法器 (carry-skip adder)。如果 $P_0{P}_1{P}_2{P}_3\ne 1$$P_0P_1P_2P_3\neq1$，则通过正常路径得到进位输出。

• 关键路径：最坏情况下进位产生于第 0 位的位置，逐位通过第一个模块，跃过 $(N/M-2)$$(N/M-2)$ 个旁路级，并且被吸收在最后一位的位置上而不产生输出进位。

• 每一旁路模块的最优化位数是由工艺参数来决定的，如旁路选择多路开关的额外延时、在进位链中的缓冲要求以及通过逐位进位和通过旁路的延时的比值。

• 上述公式是性能下限（延时上限），关于中间路径的旁路问题：可以理解为，为了让一条进位路径变得最长，它就必须走旁路；如果它不走旁路，也就意味着这条路径在中间就被“截断”了。

  • 例如， $P_4{P}_5{P}_6{P}_7=1$$P_4 P_5 P_6 P_7 = 1$，加法器会强制进位传播切换到旁路通道。

  • $P_4{P}_5{P}_6{P}_7\ne 1$$P_4 P_5 P_6 P_7 \neq 1$，则有以下两种情况：

  • 1. 消除（Delete）：至少有一个比特的 $A=0,B=0$$A=0, B=0$。之前的进位信号走到这一位直接被消除，进位输出 0。路径到此结束。

    2. 产生（Generate）：至少有一个比特的 $A=1,B=1$$A=1, B=1$。之前的进位信号走到这一位没用了，这一位自己产生了一个全新的进位 1 往后传。

• 尽管 进位旁路加法器的延时 与位数 $N$$N$ 仍然是线性关系，但 旁路加法器 延时增加的斜率比在 逐位进位加法器 中要平缓。这一差别对于较大的加法器是很明显的。注意，逐位进位加法器实际上在 $N$$N$ 值较小时比较快，因为旁路结构中的多路开关带来额外开销。

进位选择加法器

• 在进位选择加法器中，预先考虑进位输入两种可能的值，并提前计算出针对这两种可能性的结果。一旦输入进位的确切值已知，正确的结果就可以通过一个简单的多路开关级很容易地选出。

• 核心是利用硬件冗余（两套进位链）思想

• 注意 0-Carry和 1-Carry 是并行计算的。

• $t_{setup}$$t_{setup}$：加法器中所有的 16 位同时计算产生（Generate, G）和传播（Propagate, P）信号。

• $M\cdot t_{carry}$$M \cdot t_{carry}$：四块把各自的"0" carry 和 "1" carry 同时计算完成

• $(N/M)\cdot t_{mux}$$(N/M) \cdot t_{mux}$：根据真实进位 $C_{in}$$C_{in}$ 逐级通过 mux

• 观察得到，最后一级的进位链的结果在多路开关信号到达之前很久就已经稳定下来，平方根进位选择加法器，选择让这两个路径的延时相等。

平方根进位选择加法器

• 平方根进位选择加法器中：逐渐增加后续各级的位数来实现每一级的两个进位链信号以及来自前一级模块的多路开关信号到达时间相等。

• 实际上，这一加法器逐级加长的简单方法使加法器结构具有亚线性延时特性。这可以通过以下分析来说明：假设一个 $N$$N$ 位加法器含有 $P$$P$ 级，第一级相加 $M$$M$ 位。后续各级依次增加一位。于是下述关系成立：

• 如果 $M\ll N$$M\ll N$（例如， $M=2$$M=2$， $N=64$$N=64$），则第一项起主要作用，则 $P\approx \sqrt{2N}$$P\approx\sqrt{2N}$

• 所以，对于大的加法器 ( $N\gg M$$N\gg M$) 延时与 $\sqrt{N}$$\sqrt{N}$ 成正比，即 $t_{add}=O(\sqrt{N})$$t_{add}=O(\sqrt{N})$。

• 可以看到，平方根进位选择加法器中，当 $N$$N$ 值很大时，$t_{add}$$t_{add}$ 几乎变为常数。

全 1/0 检测器

• (a) 树形结构 (Tree Structure)

• (b)不对称结构 (Asymmetric Structure) —— 应对信号到达时间的差异。最晚到达的 $A_7$$A_7$ 至输出只有一个门的延时。思想：最晚到达的信号（$A_7$$A_7$）放在最靠近最终输出端的位置。

• (c) 伪 NMOS 结构 (Pseudo-NMOS) ——用功耗换取面积

• 相等比较器检查每一位是否相等（同或门 + 与门）

• 数值比较器（magnitude comparator）决定两个二进制数中哪个较大。为了比较两个无符号数 $A$$A$ 和 $B$$B$，可以计算 $B-A=B+\bar{A}+1$$B - A = B + \overline{A} + 1$。如果产生进位输出（ $C=1$$C = 1$ ），那么 $A\le B$$A \le B$；否则 $A > B$。

• 一个零检测器可以用来指明这两个数是否相等。当且仅当 4 个加法结果全为 0 时，输出 $Z=1$$Z = 1$。

• 图 11.45 为一个 4 位的无符号数比较器，它由一个串行进位加法器及 2 的补码构成。两个数值的相对大小可以由进位输出 ($C$$C$) 和检零信号 ($Z$$Z$，即 zero) 根据表 11.4 决定。对于较宽（位数较多）的输入，可以采用任何较快的加法器结构。

• 上图中，A 转化成补码，最低位的加法器进位输入（$C_{in}$$C_{in}$）接高电平（1）

• 二进制计数器和线性反馈移位寄存器。

• 一个 $N$$N$ 位二进制计数器会按照二进制顺序依次经历：$2^N$$2^N$ 个输出状态。

• 一个 $N$$N$ 位线性反馈移位寄存器会按照伪随机顺序经历最多： $2^N-1$$2^N-1$ 个输出状态。

• 左图：同步计数器 ｜右图：带复位、加载和使能功能的同步加 / 减计数器

  • 一般的同步双向（递增/递减）计数器（synchronous up/down counter）显示在图 11.49(a)中，它的每位位置上采用可复位的寄存器及全加器，它的周期时间受串行进位延时的限制。当只需要递增计数器（up counter）（也称为增量器，即 incrementer）时，全加器可以简化为半加器，如图 11.49(b)所示。

  • 当增加一个输入多路开关时可以使计数器装入初始值。另外，还常常在每个寄存器上增加一个时钟使能端以实现有条件计数。终止计数（TC）输出信号表明计数器已上溢或下溢。

• 考虑两个没有符号的二进制数 $X$$X$ 和 $Y$$Y$，分别为 $M$$M$ 位宽和 $N$$N$ 位宽。为了说明乘法运算，可以用二进制形式来表示 $X$$X$ 和 $Y$$Y$：

• 二进制乘法

  $$\begin{array}{}\text{(}\text{10}\text{)}& Z=\left(\sum _{i=0}^{M-1}{X}_i{2}^i\right)\left(\sum _{j=0}^{N-1}{Y}_j{2}^j\right)\end{array}$$

  展开后：

  $$\begin{array}{}\text{(}\text{11}\text{)}& Z=\sum _{i=0}^{M-1}\sum _{j=0}^{N-1}{X}_i{Y}_j{2}^{i+j}\end{array}$$

• 乘法可以看作重复加法：对于 $M$$M$ 和 $N$$N$ 位宽的输入，乘法采用一个 $N$$N$ 位加法器时需要 $M$$M$ 个周期。这个乘法的移位和相加算法把 $M$$M$ 个部分积（partial product）加在一起。每一个部分积是通过将被乘数与乘数的一位相乘（这本质上是一个“与”操作），然后将结果移位到这个乘数位的位置得到的。

部分积的产生

• 部分积是被乘数 $X$$X$ 和一个乘数位 $Y_j$$Y_j$ 进行逻辑 AND 操作的结果。部分积阵列中的每一行或者是被乘数的一个副本或者全部是 0。

• 仔细地优化部分积的产生能够显著减少延时和面积。注意，大多数情况下部分积阵列中有许多行全部是 0，它们对运算结果没有任何影响，因而在进行相加时是一种浪费。当一个乘数全部由 1 构成时，所有部分积都存在，而在乘数全部为零时则一个部分积也没有

• Booth 重编码

• 一种用于减少乘法阶段数量的编码方案。

• 每次完成两位乘法，因此所需阶段数量约减少一半。

• 每一级比简单乘法器稍微复杂一些，但加 / 减法器几乎可以做到和普通加法器一样小、一样快。

部分积的累加

• 上图是一个无符号数 4 *4 位阵列乘法器的组成。它的硬件结构与图 11.28 中的手工乘法之间在拓扑结构上一一对应。产生 $N$$N$ 个部分积需要有 $N\times M$$N \times M$ 个两位的 AND 门。乘法器的大部分面积都用于把 $N$$N$ 个部分积相加，这需要有 $N-1$$N-1$ 个 $M$$M$ 位的加法器。使部分积正确对位的移位通过简单布线来完成，而不需要任何逻辑电路。整个结构可以很容易地压缩成一个矩形，使它的版图非常紧凑。

• 乘数 $Y$$Y$ ，被乘数 $X$$X$

• 上图中阵列乘法器的部分和加法器用逐位进位结构实现。为了优化性能，首先需要识别关键的时序路径。这一任务并不简单。事实上，可以看到这里有许多长度几乎一致的路径。

• 关键路径 2的传播延时的近似表达式为

• $t_{and}$$t_{and}$： 所有部分积同时产生，第一步需要经过与门，耗时 $1\times t_{and}$$1 \times t_{and}$。

• $(M-1)t_{carry}$$(M-1)t_{carry}$： 信号从第一行的最右侧（最低位）产生进位，一路向左传递，直到第一行的最左侧。因为一行有 $M$$M$ 个比特位，所以需要经过 $M-1$$M-1$ 个进位传递（Carry）。

• 注意：不能直接通过最左侧的进位线往下掉，因为只会累加 $t_{carry}$$t_{carry}$

• 为了寻找最慢的路径，信号选择从第一行最左侧加法器的 Sum（求和端） 掉入第二行，耗时 $1\times t_{sum}$$1 \times t_{sum}$。掉入第二行后，它又立刻顺着第二行的 Carry（进位端） 向左横移一格，耗时 $1\times t_{carry}$$1 \times t_{carry}$。就这样以“下落一格 (Sum)，左移一格 (Carry)”，像走楼梯一样穿过中间的行。因为总共有 $N$$N$ 行，去掉第一行和最后一行，中间这种“Z字形”下落一共会发生 $N-2$$N-2$ 次。因此，这一段累加了 $(N-2)t_{sum}+(N-2)t_{carry}$$(N-2)t_{sum} + (N-2)t_{carry}$。

• 信号到达最底层最左侧，再累加一个 $1\times t_{sum}$$1 \times t_{sum}$，输出最后的乘积位。

• 由于在这里所有的关键路径都具有同样的长度，所以从设计的角度来看，只加速它们其中的一条（例如，通过用一个进位选择加法器这样的较快的加法器来代替一个加法器）并没有太大的意义。因此，必须同时考虑所有的关键路径。要使 $t_{mult}$$t_{mult}$ 最小，要求同时使 $t_{carry}$$t_{carry}$ 和 $t_{sum}$$t_{sum}$ 也最小。这时，如果使 $t_{carry}$$t_{carry}$ 等于 $t_{sum}$$t_{sum}$ 就可能有益。这与前面讨论过的对加法器单元的要求不同，在加法器设计中最重要的是使 $t_{carry}$$t_{carry}$ 最小。

• 由于阵列乘法器中有许多几乎相同的关键路径，通过调整晶体管的尺寸来提高这一结构的性能效果非常有限。但若注意到，当使进位输出位如图 11.32 所示向下沿对角线通过而不只是向左通过时乘法的结果并不改变，就可以得到一个更有效的实现。我们加入一个额外的加法器来产生最终的结果，这个加法器称为向量合并（vector-merging）加法器。由此所得到的乘法器称为进位保留乘法器${}^{[Wallace64]}$$^{[Wallace64]}$，因为进位位并不立即相加，而是“保留”给下一级加法器。在最后一级 进位与“和”在一个快速的进位传播（如超前进位的）加法器中合并。虽然这一结构略微增加了一些面积（多了一个加法器），但它具有在最坏情形下关键路径最短并且是唯一确定的优点，如图 11.32 所示，并可描述为

• 当把图 11.32 的进位保留乘法器映射到硅片上时，还必须考虑其他一些拓扑问题。为了便于把乘法器集成到芯片的其余部分，建议使这一模块的外形近似于矩形。有利于自动化生成。

• 基于进位保存加法器的阵列乘法器

• CSA Array：进位保存加法器阵列

  CPA：进位传播加法器

矩形阵列

• 将阵列压缩，使其适应矩形版图规划。

Wallace 树乘法器

• 部分和加法器也可以安排成树形，这可以同时减少关键路径和所需的加法器单元数目。考虑四个部分积的一个简单例子，每一个部分积都是四位宽，如图 11.34(a) 所示。可以看到在阵列中只有第三列必须加四位，所以可以减少这一操作所需的加法器数目。其他所有的列则稍微简单些。

• 这显示在图 11.34(b) 中，图中原来的部分积矩阵重新安排成树形以直观地说明它的不同深度。困难在于如何用最小的深度和最少数量的加法元件来实现整个矩阵。

• 可以“覆盖”该矩阵的第一类运算器是全加器 (FA)，它有三个输入并产生两个输出：位于同一列的“和”与位于相邻一列的“进位”。因此全加器又称 3-2 压缩器。它用包含三个位的圈表示。另一类运算器是半加器 (HA)，它在一列中取两个输入位并产生两个输出。半加器用一个包含两个位的圈表示。

  • 全加器 (FA / 3:2 Compressor)： 它的输入是 3 个相同权重的 bit（同一列的 3 个点），输出是 1 个 Sum（留在这一列）和 1 个 Carry（进位到左边一列）。物理意义：把同一列的 3 个点，变成了 2 个点（一个在原列，一个在左列）。

  • 半加器 (HA / 2:2 Compressor)： 输入是同一列的 2 个点，输出同样是 1 个 Sum 和 1 个 Carry。物理意义：把同一列的 2 个点，变成了 2 个点（一个原列，一个左列）。

• 为了得到面积最小的实现，我们从树结构最密的部分开始，反复地用全加器和半加器来“覆盖”树。第一步，在第 4 列和第 3 列引入半加器，如图 11.34(b) 所示。缩减后的树如图 11.34(c) 所示。第二轮的缩减产生了一个深度为 2 的树，如图 11.34(d) 所示。这两步缩减过程只用了三个全加器和三个半加器，而图 11.32 中的进位保留乘法器则需要 6 个全加器和 6 个半加器！最后一级由一个简单的两输入加法器构成，可以采用任何类型的加法器。

• 以上介绍的结构称为 Wallace 树形乘法器${}^{[Wallace64]}$$^{[Wallace64]}$，它的实现如图 11.35 所示。该树形乘法器明显节省了较大乘法器所需要的硬件，同时也减少了传播延时。事实上可以看到，通过这个树的传播延时等于 $O({\log }_{3/2}(N))$$O(\log_{3/2}(N))$。虽然 Wallace 乘法器在乘数位数较多时比进位保留结构快得多，但它的缺点是非常不规则，这使后面高质量的版图设计任务变复杂。这一不规则性甚至在图 11.35 的四位乘法器的实现中就可以看出。

• 完成乘法的最后一步是在最终加法器中合并结果。这一“向量合并”操作的性能至关重要。加法器类型的选择取决于累加阵列的结构。如果加法器的所有输入位同时到达，则最好选择一个超前进位加法器，因为它产生最小可能的延时。当一个流水线级正好放在最终相加的前面时就是这种情况。流水线是高性能乘法器经常采用的技术。在非流水线乘法器中，由于乘法器树逻辑深度不同，最终加法器输入到达的时间非常不一致。这时，采用其他加法器结构，如进位选择加法器，常常能达到与超前进位加法器类似的性能指标，而硬件的成本却低得多${}^{[Oklobdzija01]}$$^{[Oklobdzija01]}$。

• 上图是一个简单的一位左右移位器。根据不同的控制信号，输入字或者左移或者右移，或者维持不变。多位移位器可以通过串联许多这样的单元来实现。

• 当移位的位数较多时，这一方法很快变得太复杂、不实用和速度极慢，因此应当采用更为结构化的方法。

• 上一页介绍的可编程二进制移位器的具体工作模式：

  • nop = 1 ，$A_i$$A_i$ 直接传给 $B_i$$B_i$，$A_{i-1}$$A_{i-1}$ 直接传给 $B_{i-1}$$B_{i-1}$。

  • rgt = 1 ，$A_i$$A_i$ 传给 $B_{i-1}$$B_{i-1}$。

  • left = 1 ，$A_{i-1}$$A_{i-1}$ 传给 $B_i$$B_{i}$。

• 桶形移位器：它由一个晶体管阵列构成，其行数等于数据的字长，而列数则等于最大的移位宽度。在本例中，二者均为 4。控制线沿对角线布置通过该阵列。

• 优点是信号最多只需通过一个传输门。传播延时在理论上是常数，与移位的位数或移位器的规模无关。但在实际中并不是这样，因为缓冲器输入端的电容随最大移位宽度线性地增加。

• 这一电路的一个重要特点是它的版图尺寸并不是像其他运算电路那样由有源晶体管来决定，而是由通过该单元的布线数目来决定。更具体地说，移位单元的尺寸由金属线的节距来确定。

• 选择移位器时另一个重要的考虑是移位值必须表示为何种形式。从图 11.37 的电路图中可以看到，桶形移位器的每个移位都需要一条控制线。例如，一个四位的移位器需要四条控制信号。为了移三位，信号 $S{h}_3:S{h}_0$$Sh_3:Sh_0$ 的值应为 1000。只有一个信号是高电平。在处理器中，通常把需要移位的值以更为简洁的二进制形式编码。例如，这里的编码控制字只需要两个控制信号，对于移动三位控制信号表示为 11。为了把后一个表示方法转化为前者（即只有一位为高电平），需要增加一个译码器模块。

• $S{h}_0=1$$Sh_0 = 1$：不移位，激活贯穿阵列主对角线的晶体管，信号全部沿水平方向通过， $B_3{B}_2{B}_1{B}_0=A_3{A}_2{A}_1{A}_0$$B_3 B_2 B_1 B_0 = A_3 A_2 A_1 A_0$。

• $S{h}_1=1$$Sh_1 = 1$：右移一位

• $S{h}_2=1$$Sh_2 = 1$：右移两位

• $S{h}_3=1$$Sh_3 = 1$：右移三位

• 桶形移位器把整个移位器实现为传输管的单个阵列，而对数移位器则采用分级的方法。总的移位值被分解成几个 2 的指数值。一个具有最大移位宽度 $M$$M$ 的移位器包括 ${\log }_{2}M$$\log_2 M$ 级，它的第 $i$$i$ 级或者把数据移动 $2^i$$2^i$ 位或者原样传送数据。图 11.38 是一个最大移位值为 7 位的移位器的例子。例如，要移动 5 位，第一级设置在移位模式，第二级为通过模式，而最后一级又是移位模式。注意，这个移位器的控制字已经编码，所以不需要单独的译码器。

• 对数移位器的速度以对数方式取决于移位宽度，因为一个 $M$$M$ 位的移位器需要 ${\log }_{2}M$$\log_2 M$ 级。同时，对于较大的移位值，传输管的串联连接会减慢移位器的速度。因此，如在第 6 章中所讨论的，有必要仔细插入中间缓冲器。

• 一般来说我们的结论是，桶形移位器适用于较小的移位器，而对于较大的移位值，采用对数移位器在面积和速度方面都更为有效。而且对数移位器很容易参数化，便于自动生成设计。

• 最大移位宽度为右移7位的对数移位器（只显示了 4 个最低有效位）

• 最右边应该是 $Sh4$$Sh4$ ，不是 $Sh3$$Sh3$

• 除法器、计数器、译码器、多路选择器

  ALU，算术逻辑单元