运算方法与运算部件

有关「高级语言和机器指令中的运算」的内容，大部分都在其他课程（例如《计算系统基础》）中提及了，这里不再赘述。

基本运算部件

详细内容可见《计算系统基础》笔记——4. 运算方法和运算部件。

全加器

设输入为加数 $A$、被加数 $B$ 和低位进位 $C_{\mathrm{in}}$，输出为和 $F$ 和高位进位 $C_{\mathrm{out}}$。则有

$$\left\lbrace\begin{aligned} F &= A \oplus B \oplus C_{\mathrm{in}} \\ C_{\mathrm{out}} &= A \cdot B + A \cdot C_{\mathrm{in}} + B \cdot C_{\mathrm{in}} \end{aligned}\right.$$

详细内容见《计算系统基础》笔记中关于「全加器」的介绍。

《计算系统基础》笔记中用的是 $S$，这里是 $F$，下同。

「串行进位加法器」见《计算系统基础》笔记中关于「行波进位加法器」的介绍。

并行进位加法器

串行进位加法器采用串行逐级传递进位，电路延迟与位数成正比关系。因此，现代计算机采用一种先行进位（carry look ahead）方式。

定义辅助函数

$$\left\lbrace\begin{aligned} G_i &= X_i \cdot Y_i, &\text{进位生成函数}\\ P_i &= X_i + Y_i, &\text{进位传递函数} \end{aligned}\right.$$

全加逻辑方程

$$\left\lbrace\begin{aligned} F_i &= X_i \oplus Y_i \oplus C_{i-1} \\ C_{i+1} &= X_i \cdot Y_i + (X_i + Y_i) \cdot C_i = G_i + P_i \cdot C_i \end{aligned}\right.$$

通过计算 $G_i$ 和 $P_i$，可以直接计算出 $C_{i+1}$，而不需要等待 $C_i$ 传递过来。

详细内容见《计算系统基础》笔记中关于「先行进位加法器」的介绍，里面的式子解释更为详细，同时还有不同颜色的标注。

《计算系统基础》笔记中 $P_i$ 定义为 $X_i \oplus Y_i$，这没差，而且 $F_i$ 里也会用到。

带标志加法器

对于溢出标志 $\mathrm{OF}$ 有

$$\mathrm{OF} = C_n \oplus C_{n-1}$$

对于符号标志 $\mathrm{SF}$ 有

$$\mathrm{SF} = F_{n-1}$$

对于零标志 $\mathrm{ZF}$ 有

$$\mathrm{ZF} = 1 \iff F = 0$$

对于进位/借位标志 $\mathrm{CF}$ 有

$$\mathrm{CF} = C_{\mathrm{in}} \oplus C_{\mathrm{out}}$$

算术逻辑部件（Alorithmic Logic Unit, ALU）

• 进行基本算术运算与逻辑运算
• 核心电路是整数加/减运算部件
• 输出和/差及标志信息
• 有操作控制端（ALUop），用来决定 ALU 所执行的处理功能。

定点数运算

补码加减运算

好像没啥好记的？

原码加减运算*

• 用于浮点数尾数运算
• 符号位和数值部分分开处理
• 仅对数值部分进行加减运算，符号位起判断和控制作用

规则：

• 比较两数符号，对加法实行「同号求和，异号求差」，对减法实行「异号求和，同号求差」。
• 求和：数值位相加，若最高位产生进位，则结果溢出。和的符号取被加数（被减数）的符号。
• 求差：被加数（被减数）加上加数（减数）的补码。分二种情况讨论：
  1. 最高数值位产生进位，表明加法结果为正，所得数值位正确。
  2. 最高数值位没有产生进位，表明加法结果为负，得到的是数值位的补码形式，需对结果求
     补，还原为绝对值形式的数值位。
• 差的符号位：
  • 上面的 1. 情况下，符号位取被加数（被减数）的符号
  • 上面的 2. 情况下，符号位为被加数（被减数）的符号取反

无符号数的乘法运算

被乘数 $X$ 与乘数 $Y$，按手算列竖式乘法的规则，有

$$X \times Y = \sum (X \times Y_i \times 2^i)$$

采用递推减少保存各次相乘结果 $X \times Y_i$ 的开销。

设 $P_0 = 0$，有

$$\begin{aligned} P_1 &= 2(P_0 + X \times Y_n)\\ P_2 &= 2(P_1 + X \times Y_{n-1})\\ &\vdots\\ P_n &= 2(P_{n-1} + X \times Y_1) \end{aligned}$$

递推有

$$P_{i+1} = 2(P_i + X \times Y_{n-i})$$

最终 $P_n = X \times Y$。

原码乘法运算

用于浮点数尾数乘运算。数值部分使用无符号乘法运算。

原码两位乘法操作递推公式：

• $00$：$P_{i+1} = 2^{-2} P_i$
• $01$：$P_{i+1} = 2^{-2} (P_i + X)$
• $10$：$P_{i+1} = 2^{-2} (P_i + 2X)$
• $11$：$P_{i+1} = 2^{-2} (P_i + 3X) = 2^{-2} (P_i - X) + X$（即本次 $-X$，下次 $+X$）

如下表所示，其中 $T$ 触发器用来记录下次是否要执行 $+X$，开始时为 $0$。

$Y_{i-1}$	$Y_i$	$T$	$X$	操作	迭代公式
$0$	$0$	$0$	-	$0\to T$	$2^{-2} P_i$
$0$	$0$	$1$	$+X$	$0\to T$	$2^{-2} (P_i + X)$
$0$	$1$	$0$	$+X$	$0\to T$	$2^{-2} (P_i + X)$
$0$	$1$	$1$	$+2X$	$0\to T$	$2^{-2} (P_i + 2X)$
$1$	$0$	$0$	$+2X$	$0\to T$	$2^{-2} (P_i + 2X)$
$1$	$0$	$1$	$-X$	$1\to T$	$2^{-2} (P_i - X)$
$1$	$1$	$0$	$-X$	$1\to T$	$2^{-2} (P_i - X)$
$1$	$1$	$1$	-	$1\to T$	$2^{-2} P_i$

补码乘法运算

见《计算系统基础》中关于「布斯一位乘」的介绍。