考研笔记

基本运算部件

补码把减法消掉之后，整台机器的定点运算只剩下一件事要做：加法。本节讲的就是这个加法器长什么样，以及它为什么慢、怎么变快。

一条主线贯穿全节：加法的瓶颈从来不是求和，而是进位。 求和是每一位各算各的，天然并行；进位却是从最低位一路串到最高位，天然串行。几乎所有加法器的设计都在和这条进位链搏斗。

机制

半加器与全加器

半加器只加两个位，不接受来自低位的进位：它不够用——除最低位外，每一位都要接受低位送来的进位。全加器接受三个输入 、、：

进位表达式的这个写法很关键，它把进位的来源拆成了两类：

  • ：两位都是 1，这一位自己就产生了进位，与低位无关；
  • ：两位恰有一个 1，自己不产生进位，但会把低位来的进位原样传出去。

这两类分别记作进位生成进位传递于是全加器的进位统一写成这一个式子是本节后半段的全部基础。

串行进位加法器：慢在哪里

把 个全加器首尾相接，低位的 直接接到高位的 ，就得到串行进位加法器（也叫行波进位加法器，carry-ripple adder）。

flowchart RL
    C0(("C₀")):::c
    FA0["FA₀"]:::fa
    FA1["FA₁"]:::fa
    FA2["FA₂"]:::fa
    FAn["FAₙ₋₁"]:::fa
    Cn(("Cₙ")):::c

    C0 --> FA0
    FA0 -->|"C₁"| FA1
    FA1 -->|"C₂"| FA2
    FA2 -.->|"…"| FAn
    FAn --> Cn

    classDef fa fill:#dbeafe,stroke:#2563eb,color:#1e3a5f
    classDef c fill:#fee2e2,stroke:#dc2626,color:#7f1d1d

问题一目了然：最高位的和必须等最低位的进位一路传上来才能确定。 每级全加器产生进位需要 2 级门延迟（一级与、一级或）， 位就是 级门延迟，延迟与位数成正比。

32 位加法器要等 64 级门延迟，这直接决定了 CPU 的时钟周期下限——运算部件的速度会反过来卡住主频，第 5 章讲数据通路时会再次遇到。

先行进位加法器：把串行改成并行

既然瓶颈是进位链，就设法让每一位的进位不依赖前一位的进位，而直接依赖最初的输入。

把 逐层代入展开：

每个 现在都只是 、 和 的两级逻辑（与-或）。 、 又都只由 、 一级门算出，且四位可以同时算。

于是 在同一时刻产生，与位号无关。这就是先行进位加法器（CLA，carry-look-ahead adder），也叫并行进位加法器。

代价写在式子里： 的表达式有 5 项、最长一项 5 个输入。位数越高，门的扇入越大。所以实际做法是每 4 位一组做完全先行，组与组之间再想办法：

结构组内组间特点
单级先行进位并行串行简单，延迟随组数线性增长
多级先行进位并行并行（再用一层 CLA）延迟随位数对数增长，扇入可控

组间也并行时，需要成组的生成与传递函数 、：一整组”自己产生了进位”或”把进位整组传出去”，形式与单位完全一样，只是层级更高。这是一种递归结构。

加减统一电路

有了加法器，减法不需要任何新部件。由 求相反数的补码：补补。

于是引入一根控制线 ：

  • 每一位的 先经过一个异或门：。 时原样通过， 时逐位取反。
  • 同时接到加法器的最低位进位 。

时，加法器算的就是 补。

"" 是靠 免费得到的——这是补码设计中最漂亮的一处：取反由 个异或门完成，加一由一根本来就存在的进位输入完成，减法的额外硬件成本只有 个异或门。

ALU 的边界：它做什么，不做什么

ALU（算术逻辑单元）是运算部件的封装：两个数据输入、一组控制信号 、一个结果输出，外加若干标志位输出。

ALU 内部通常包含说明
加减法器上面的加减统一电路，是核心
逻辑运算阵列与、或、非、异或，每位独立，无进位链
比较通常靠”做减法看标志位”实现，不单设部件
移位可有可无，见下

ALU 之外通常另有：乘法器 / 除法器（见 2.2.4，代价高，常独立成部件甚至独立流水线）、浮点运算单元（FPU）。

的位数决定了 ALU 能做多少种运算，它由控制器产生——第 5 章的控制器要做的事之一，就是把指令的操作码翻译成 。

关联对照：移位器是否属于 ALU，没有统一答案

移位既可以作为 ALU 的一种功能（由 选择），也可以做成 ALU 之外的独立移位器 / 移位寄存器（由单独的 控制）。两种做法都真实存在，教材和实验板的画法不一致是正常的。 做数据通路题时的判据只有一条：看图上有没有单独的移位部件。有，就由它做；没有，就由 ALU 做。展开见 2.2.2。

边界

半加器 vs 全加器

判据是”接不接受低位进位”，不是”能不能算两个数”。

位加法器需要 1 个半加器（最低位，若 恒为 0）+ 个全加器；但实际机器为了支持减法（）和多字长运算（ 接上一次的进位），最低位也用全加器。

串行 vs 并行：快在哪、贵在哪

串行进位先行进位
进位延迟与位数成正比（ 级门）组内恒定（约 2 级门）
门数少，规整多，随组宽指数增长
扇入小大，限制了组不能太宽
典型组宽——4 位

先行进位不是”取消了进位链”，而是”把进位链换成了扇入更大的组合逻辑”——用面积换时间。这个取舍在第 5 章讲流水线时会以另一种形式再次出现。

进位 不等于溢出

加法器输出的最高位进位 是无符号运算的溢出信号（CF）；有符号运算是否溢出，要看 （OF），是另一根线。

同一个加法器同时输出这两根线，硬件不知道该看哪一根——这一点在 2.2.3 展开，它是 2.1.3 那张”五处区分”表的第一行。

运算部件不保存状态

ALU 是纯组合逻辑：输入变，输出立刻跟着变，它自己不记住任何东西。数据要靠寄存器保存（第 5 章的数据通路），标志位要靠标志寄存器锁存。

由此可知 ALU 不能单独完成”累加”这类操作——必须有寄存器把上一次结果送回输入端，这条回路是数据通路题的必考结构。

对照速查

概念一句话
进位生成：这一位自己就产生进位
进位传递：把低位的进位传出去
全加器进位的统一形式
串行进位延迟
先行进位（组内 4 位）组内进位同时产生
加减统一 逐位异或 Sub +

考点

  • 全加器进位式 ，能写出 、 的含义
  • 串行进位延迟与位数成正比，是加法器速度的瓶颈
  • 先行进位把进位改写成只依赖 、 和 ，组内同时产生
  • 先行进位的代价是门数和扇入，故实际按 4 位分组
  • 加减统一电路只需 个异或门，“加一”由 提供
  • ALU 是组合逻辑，不保存状态；乘除法器通常在 ALU 之外
  • 移位器可在 ALU 内也可在 ALU 外，做题看图
  • 是 CF，不是 OF

链接

反向链接