计算机的算术运算

运算器#

主要关心整数运算器，设计 ALU (Arithmetic Logic Unit)。

ALU 负责执行所有的算术和逻辑操作，比如加法、减法、按位与、按位或等。

饱和运算 Saturating operations：如果结果超出范围，就取最大值或最小值。

乘法#

RISC-V 的乘法有四个核心指令：

• mul：返回低位结果（RV32I 为低 32 位，RV64I 为低 64 位）。
• mulh：返回有符号数乘法的高位。
• mulhu：返回无符号乘法的高位。
• mulhsu：第一个操作数有符号、第二个无符号，返回高位。

基本移位-累加算法#

设被乘数为 $M$、乘数为 $Q$，都是 $n$ 位补码数。硬件通常准备一个 $2n$ 位的乘积寄存器 $P$。逐位处理乘数：

1. 初始化 $P \leftarrow 0$。
2. 对 $i = 0 \dots n-1$：若 $Q_i = 1$，则将 $M$ 左移 $i$ 位后加到 $P$ 上。
3. 结果 $P$ 含 $2n$ 位，低位对应 mul，高位对应 mulh/mulhu 等。

乘法的数学形式：

$$P = M \times Q = \sum_{i=0}^{n-1} q_i \cdot M \cdot 2^i$$

示例：计算 $M = 13 = 01101_2$、$Q = 11 = 01011_2$。

• 循环 0：$Q_0 = 1$，部分积加 $M$ 得 $00000 + 01101 = 01101$。
• 循环 1：$Q_1 = 1$，加 $M \ll 1 = 11010$，结果 $100111$。
• 继续直到循环 4，最终得到 $P = 10001111_2 = 143_{10}$，符合 $13 \times 11 = 143$。

Booth 算法（补码优化）#

核心思想是压缩连串的 $1$ 为一次加减：观察乘数当前位 $Q_0$ 与“伪位” $Q_{-1}$。

每轮后对部分积 $A$、乘数 $Q$、伪位 $Q_{-1}$ 做算术右移，循环 $n$ 次。Booth 对乘数含连续 $1$ 的情形尤其高效。

Booth 示例：计算 $M = -6 = 11010_2$、$Q = 13 = 01101_2$（5 位）：

最终组合 $A:Q = 11101\,10010_2$，解析为十进制 $-78$，与 $-6 \times 13$ 一致。

阵列乘法器与壁虎乘法器#

• 阵列（array）乘法器利用规则结构把所有部分积一次性生成并通过多级加法器相加，代价是硬件面积较大。
• Wallace tree / CSA（Carry Save Adder）乘法器在部分积累加阶段采用进位保存，加速运算；末级再用快速加法器获得最终结果。
• 单精度浮点尾数含隐含位，共 $24$ 位；双精度为 $53$ 位 => 浮点乘法器至少需要 $24\times 24$ 或 $53\times 53$ 位部分积。

浮点数加法#

浮点加法遵循“对齐—运算—规格化—舍入—异常”流程：

1. 对齐指数：指数差 $d = E_A - E_B$。较小指数的尾数右移 $d$ 位并产生 GRS 位。
2. 尾数运算：若符号相同则相加，符号相反则相减。暂不处理溢出。
3. 规格化：若结果 $M$ 超过 $[1,2)$，则右移一位并使指数加一；若低于 $[1,2)$，则左移并指数减一，直至归一化。
4. 舍入：依据 GRS 位选择舍入模式（默认 RNE 最近偶数）。
5. 异常处理：检测指数上溢（产生 $\pm\infty$）或下溢（可能转为次正规或置 0），记录异常标志。

流水线实现通过分离上述阶段提升吞吐量。

浮点数寄存器#

RISC-V 有 32 个浮点数寄存器，命名为 f0 到 f31。

每个寄存器都是 64 位，若要存储 32 位浮点数，则低 32 位存储数据，高 32 位置零。

加法与减法#

基本定义#

• 无符号 $n$ 位整数的范围： $$0 \leq X_{\text{unsigned}} \leq 2^n - 1$$
• 补码（有符号）$n$ 位整数的范围： $$-2^{n-1} \leq X_{\text{two's}} \leq 2^{n-1} - 1$$
• 补码求负： $$-B = \overline{B} + 1$$ 其中 $\overline{B}$ 表示按位取反。

二进制补码复习#

• 最高位（MSB）是符号位：0 表示非负，1 表示负。
• 求负流程：写出绝对值二进制 -> 按位取反 -> 加 $1$。
• 扩展位宽时使用符号扩展（sign extension），即复制符号位保持数值不变。
• 算术右移（ASR）保持符号：右移后空出的最高位填入原符号位。

加法器结构#

Ripple-carry 加法器以“半加器 + 全加器”串联实现：

$$S_i = a_i \oplus b_i \oplus c_i, \quad c_{i+1} = (a_i \land b_i) \lor (c_i \land (a_i \oplus b_i))$$

• 进位传播延迟：$O(n)$，因此引入 CLA（Carry Lookahead）、CSA（Carry Save）等加速器件。
• 补码减法： $$A - B = A + (-B)$$ 直接用加法器完成减法。

Carry Lookahead (CLA) 通过预先计算“生成”与“传递”信号缩短延迟：

$$g_i = a_i b_i, \quad p_i = a_i \oplus b_i, \quad c_{i+1} = g_i \lor (p_i c_i)$$

展开前两级可得：

$$c_1 = g_0 \lor (p_0 c_0), \quad c_2 = g_1 \lor (p_1 g_0) \lor (p_1 p_0 c_0)$$

CSA（Carry Save Adder）适合多操作数累加（例如乘法部分积），将每一位的进位暂存到下一层，最终再以一次 CLA 合并。

溢出检测#

• 无符号：若最终进位 $c_n = 1$ 则发生溢出。
• 补码： $$\text{Overflow} = c_n \oplus c_{n-1}$$ 等价于“同号相加得到异号”或“异号相减得到异号”。

例题：$8$ 位补码加法#

• 计算 $0101\,1100_2 (92_{10}) + 0100\,0011_2 (67_{10})$：

  • $c_7 = 1$、$c_8 = 0$，故 $c_7 \oplus c_8 = 1$ => 溢出，结果非法。

• 计算 $0101\,1100_2 + 1010\,0100_2$：符号位为 $0$ 与 $1$，异号相加 => 不会溢出。

减法演练#

目标：计算 $79 - 26$。

1. 写出操作数： $$A = 79 = 0100\,1111_2, \quad B = 26 = 0001\,1010_2$$
2. 求 $-B$： $$\overline{B} = 1110\,0101_2, \quad -B = \overline{B} + 1 = 1110\,0110_2$$
3. 执行补码加法： $$A + (-B) = 0100\,1111_2 + 1110\,0110_2 = 1\,0011\,0101_2$$
4. 舍弃最高进位，得到 $0011\,0101_2 = 53_{10}$。

常见陷阱#

• 硬件只做模 $2^n$ 加法：无论有符号还是无符号，溢出需要单独检测。
• “同号相加才会溢出”“异号相减可能溢出”是判断题常考语句。
• 签扩展忘记复制符号位会导致算术右移错误。

除法#

设被除数为 $D$，除数为 $V$，均为 $n$ 位。硬件准备 $2n$ 位的余量寄存器 $R$ 与 $n$ 位的商寄存器 $Q$。

还原除法（Restoring Division）#

每一轮执行“移-减-判断”三步：

1. 左移 $R$ 与 $Q$（等价于余量左移一位并引入下一位商）。
2. 试减：$R = R - V$。
3. 若 $R \geq 0$，则 $Q_0 = 1$；否则恢复 $R = R + V$，并置 $Q_0 = 0$。

重复 $n$ 轮，得到 $n$ 位商；余量即 $R$。

非还原除法（Non-restoring）#

• 若上一轮余量为正，则下一轮继续试减；若为负，则下一轮改为试加。
• 优点：省去恢复操作，减少一次加法。
• 完成后若余量为负，需要再加一次除数修正。

示例：13 除以 3（还原法）#

初始化 $R = 0000_2$、$Q = 1101_2$（13），除数 $V = 0011_2$（3）。四轮迭代如下：

最终商 $Q = 0100_2 = 4$，余数 $R = 00001_2 = 1$，检验 $13 = 4 \,\times 3 + 1$。熟悉“移 -> 试减 -> 判定 -> 还原/记 1”的顺序是掌握硬件除法的关键；非还原法则把“负值”分支改为加除数并在最后修正余量。

有符号除法#

• 步骤：对被除数和除数取绝对值执行无符号除法；商号位为 $\text{sign}(D) \oplus \text{sign}(V)$；余数与被除数同号。
• 特例：$\text{INT\_MIN} / -1$ 会溢出（结果超出表示范围）。
• RISC-V 在除数为 $0$ 时：div 返回 $-1$，divu 返回 all 1；rem 返回被除数。

记忆点#

• 余量寄存器宽 $n+1$ 或 $n+2$ 位以容纳临时负值。
• 每轮“移-试算”的顺序是考试高频题，必须牢记。
• 结果校验：$D = Q \times V + R$，且 $0 \leq |R| < |V|$。

浮点数快速记忆（IEEE 754）#

字段布局与偏置#

• 单精度 binary32：$S$ 1 bit、$E$ 8 bits、$F$ 23 bits，偏置 $\text{bias} = 127$。
• 双精度 binary64：$S$ 1 bit、$E$ 11 bits、$F$ 52 bits，偏置 $\text{bias} = 1023$。
• 尾数有效位：binary32 含隐含位共 $24$ 位，binary64 含 $53$ 位。

数值表示#

$$V = (-1)^S \times M \times 2^{E - \text{bias}}$$

• 规格化数：$1 \leq M < 2$，形式 $1.F$。
• 次正规数：$E = 0$，指数解释为 $1 - \text{bias}$，尾数形式 $0.F$。
• 特殊编码：
  • $E = 0, F = 0$ => $\pm 0$。
  • $E = 2^{k}-1, F = 0$ => $\pm\infty$。
  • $E = 2^{k}-1, F \neq 0$ => NaN，最高小数位为 1 表示 quiet NaN。

编码示例： 将 $-5.75_{10}$ 编成 binary32。

1. 十进制转二进制：$-5.75 = -101.11_2$。
2. 规格化：$-1.0111_2 \times 2^2$ => $S = 1$、真实指数 $E_{\text{real}} = 2$。
3. 存储指数：$E = E_{\text{real}} + 127 = 129 = 1000\,0001_2$。
4. 尾数字段取小数部分 $0111$ 并补足 23 位 => $0111\,0000\ldots 0$。
5. 最终编码：1 10000001 01110000000000000000000。

二进制位示例#

• 正规数示例（binary32）：$+0.15625 = 0.00101_2$。
  1. 规格化：$1.01_2 \times 2^{-3}$，指数存储为 $-3 + 127 = 124 = 0111\,1100_2$。
  2. 尾数字段：去掉隐含 1 得 $01000000000000000000000$。
  3. 最终编码：0 01111100 01000000000000000000000。
• 次正规数示例：binary32 的最小正值 $2^{-149}$。
  1. 编码：$S = 0$；指数字段全 0；尾数字段最低位为 1，其余 0。
  2. 表示值：$0.F \times 2^{1-127} = 0.000\ldots 01_2 \times 2^{-126} = 2^{-149}$。
• 无穷与 NaN：
  • $+\infty$：0 11111111 00000000000000000000000。
  • quiet NaN：0 11111111 10000000000000000000000（最高小数位 1 表示 quiet）。
  • signaling NaN：最高小数位 0、其余非零，例如 0 11111111 01000000000000000000000。
• binary64 示例：$-42.125 = -101010.001_2$。
  1. 规格化：$-1.01010001_2 \times 2^5$，指数存储为 $5 + 1023 = 1028 = 1000\,0001\,00_2$。
  2. 尾数字段：$010100010000\ldots 0$（共 52 位）。
  3. 最终编码：1 1000000100 0101000100000000000000000000000000000000000000000000。

数值范围#

• binary32 暂存最小正规数 $2^{-126}$，最大约 $(2 - 2^{-23}) \times 2^{127}$。
• binary64 最小正规数 $2^{-1022}$，最大约 $(2 - 2^{-52}) \times 2^{1023}$。

舍入模式与 GRS 位#

• RISC-V 支持五种舍入：RNE（最近偶数）、RTZ（向 0）、RDN（向 $-\infty$）、RUP（向 $+\infty$）、RMM（最近到最大幅值）。
• GRS（Guard、Round、Sticky）位来自对齐时右移的信息，用于判断是否需要进位。

舍入模式详解（重点 RNE 向偶数）#

• GRS 位来源：
  • Guard ($G$)：当前保留尾数之后的第一位。
  • Round ($R$)：第二位。
  • Sticky ($S$)：剩余所有被丢弃位的或值；若后续有任意 1，则 $S = 1$。
• RNE 步骤：
  1. 若 $G = 0$，直接截断（无进位）。
  2. 若 $G = 1$ 且 ($R = 1$ 或 $S = 1$)，向上进位。
  3. 若仅 $G = 1$ 且 $R = S = 0$（恰好在中间值，即 $0.5$ ULP），检查当前最低保留位 $L$：
     • $L = 0$（偶数），保持不变；
     • $L = 1$（奇数），加 1 使其变偶。
• 例子：binary32 尾数保留 24 位，现有 $M_{\text{raw}} = 1.01010101010101010101011_2$。
  • $G = 1$（第 25 位），$R = 0$，$S = 0$，最低保留位 $L = 1$。
  • 条件 3 触发，进位后得到 $1.0101010101010101010110_2$，最低位变 0（偶数）。
• 与其他模式比较：
  • RTZ：直接舍弃，结果总是趋向 0。
  • RDN/RUP：根据符号选择向下或向上。
  • RMM：最近且偏向绝对值大的方向，遇到 0.5 ULP 总是进位。

异常与标志#

• 5 种 IEEE 754 异常：invalid、division-by-zero、overflow、underflow、inexact。
• RISC-V 使用 fflags 记录异常，通过 frm 设置默认舍入模式。

浮点运算流程#

• 加减：对齐指数 -> 处理尾数符号 -> 规格化 -> 舍入 -> 记录异常。
• 乘法： $$E_{\text{out}} = E_A + E_B - \text{bias}$$ $$M_{\text{out}} = M_A \times M_B$$ 若尾数 $M_{\text{out}} \in [2,4)$ 需右移并指数加一；若溢出 -> $\pm\infty$。
• 除法： $$E_{\text{out}} = E_A - E_B + \text{bias}$$ $$M_{\text{out}} = M_A / M_B$$ 通过迭代除法或牛顿迭代获得尾数，再规格化与舍入。

加法示例：计算 binary32 的 $1.5 + (-2.25)$。

1. 写成规格化形式：$1.5 = 1.1_2 \,\times 2^0$，$-2.25 = -1.001_2 \,\times 2^1$。
2. 对齐指数：右移较小指数的尾数，即 $1.1_2 \rightarrow 0.11_2$ 并指数加 1。
3. 尾数相加：$0.11_2 + (-1.001_2) = -0.111_2$。
4. 规格化：$-1.11_2 \,\times 2^0$。
5. 舍入：尾数正好符合精度 => 结果 $-0.75$。

浮点误差提示：尾数位数有限 => 每次舍入最多引入 $0.5$ ULP（单位最后位）；累积误差可能导致“不满足结合律”。

速记列表#

• 字段尺寸：binary32 是 $1/8/23$，binary64 是 $1/11/52$。
• 偏置：binary32 = 127，binary64 = 1023。
• 有效位：binary32 -> 24，binary64 -> 53。
• 五种舍入 + 五类异常必须背熟。
• 特殊值识别：$E = 0$ => $0$ 或次正规；$E = \text{all 1}$ => $\infty$ 或 NaN。

RISC‑V 指令速记#

• 乘法（M 扩展）：mul（低位），mulh（有符号高位），mulhu（无符号高位），mulhsu（混合）。
• 除法/取余（M 扩展）：div，divu，rem，remu；除数为 0 的行为依规范定义。
• 浮点（F/D 扩展）：加减乘除与转换指令；舍入模式与异常通过 CSR 控制/记录。

速记清单#

• 补码范围：无符号 $0 \to 2^n-1$，有符号 $-2^{n-1} \to 2^{n-1}-1$；溢出检测 $c_n \oplus c_{n-1}$。
• 乘法：部分积宽 $2n$；Booth 表 $(01\rightarrow +M, 10\rightarrow -M)$；CSA 在部分积累加阶段使用。
• 除法：记“移 -> 试减 -> 判定 -> 还原/记 1”；结果满足 $D = QV + R$。
• 浮点：binary32 = 1/8/23、bias 127；binary64 = 1/11/52、bias 1023；舍入模式 RNE/RTZ/RDN/RUP/RMM。
• 特殊值：$E=0, F=0$ => $\pm 0$；$E=0, F\neq0$ => 次正规；$E=\text{all 1}, F=0$ => $\pm\infty$；$E=\text{all 1}, F\neq0$ => NaN。
• RISC-V M 扩展：mul, mulh, mulhu, mulhsu, div, divu, rem, remu；浮点异常在 fflags。