05-整数运算

ALU

算术逻辑单元：完成数据算术逻辑运算的部件
ALU会根据运算结果设置Flags，存入寄存器
Control Unit控制ALU操作和数据出入ALU的信号

门延迟

与门延迟：1级门延迟
或门延迟：1级门延迟
异或门延迟：3级门延迟

加减法

全加器

$S_i=X_i \oplus Y_i \oplus C_{i-1}$ ：6ty
$C_i=X_{i}C_{i-1}+X_{i}Y_{i}+Y_{i}C_{i-1}$ ：2ty

串行进位加法器

将全加器进行串联
延迟（每一步的起始时间取决于输入中最慢计算得到的那个）：
- $C_i=C_{i-1}+2\text{ ty} \rightarrow C_n=2n\text{ ty}$
- $S_1=S_2=6$
- $S_n=C_{i-1}+3\text{ ty} \rightarrow S_n=2n+1\text{ ty } (n\geq3)$
优点：元件少
缺点：慢，和数据的位数线性相关

全先行进位加法器 CLA

思路：预先并行计算部分输入值，提高效率
定义两个辅助函数：
- 传播： $P_i=X_i+Y_i$ （将前序结果”传递“下来）
- 生成： $G_i=X_iY_i$
此时展开加法的每一位，有：
- $C_0$
- $C_1=G_1+P_1C_0$
- $C_2=G_2+P_2G_1+P_2P_1C_0$
- $C_3=G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1C_0$
- ……
延迟
- 计算 $G_i, P_i$ ： $1\text{ ty}$
- 求出所有的 $C_i$ ： $2\text{ ty}$
  - 先并行计算所有的与： $1\text{ ty}$
  - 再并行计算所有的或： $1\text{ ty}$
- 最后通过异或求出 $S_i$ ： $3\text{ ty}$
优点：效率高
缺点：元件多

部分先行加法器

串联多个CLA
权衡效率与复杂度
延迟
- $8n$ 位加法，串联 $n$ 个8-bit的CLA
- 第一个计算出给下一个的 $C_8$ 需要： $1+2=3\text{ ty}$ ， $S_i$ 不与后续元件相关，时间忽略
- 此后每一个的 $G_i,P_i$ 都预先算好，计算出给下一个的 $C_{8i}$ 需要 $2\text{ ty}$
- 最后一个计算出 $C_{8n}$ 需要 $2\text{ ty}$ ， $S_{8n}$ 需要 $3\text{ ty}$
- 因此共需 $2n+4 \text{ ty}$
- 例如 $32$ 位就是 $12 \text{ ty}$

溢出判断

无符号数

最高位产生进位

有符号补码数

出现溢出：两个数同号，但是结果和这两个数异号
判断方法
- 比较符号： $X_n=Y_n$ ，且 $S_n \neq X_n, Y_n$ $\rightarrow \text{overflow} = \bar{S_n}X_nY_n+S_n\bar{X_n}\bar{Y_n}$
- 比较进位： $C_n\neq C_{n-1}$ $\rightarrow \text{overflow} =C_n \oplus C_n-1$

减法

加相反数
数据通路：
- 对多路选择器和ALU输入加/减的信号
- 多路选择器若为减则将输入取反输出
- ALU的加减信号连接在 $C_0$ 上（合在一起就是取反+1）

乘法

手算

$Y_i=0$ ：部分积为0，否则为 $X$
每一步部分积左移一位
求和

无符号数乘法

思路

基于手算思路
算一位求和一位，减少保存开销
相加时右移先前部分积的和而非左移部分积
若 $Y_i=0$ ，只移位

实现

Y算一位右移一位（算完就可以抛弃了），留出来的空间给不断右移的结果，二者此消彼长
Y的最低位传给控制逻辑决定是否要加
最终结果的高32位在成绩寄存器中，低32位在乘数寄存器中

补码乘法

问题：积的补码不等于补码的积
简单办法：都转成原码进行无符号计算，将结果再转换为补码（开销太大）

布斯算法

补码数的真值表示： $Y=-Y_n \cdot 2^{n-1}+Y_{n-1} \cdot 2^{n-2}+...+Y_2\cdot 2^1+Y_1 \cdot 2^0$

乘积： $X \cdot Y = X \cdot \left( -Y_n \cdot 2^{n-1}+Y_{n-1} \cdot 2^{n-2}+...+Y_2\cdot 2^1+Y_1 \cdot 2^0\right)$
- $=X \cdot \left( (Y_{n-1}-Y_n) \cdot 2^{n-1} + (Y_{n-2}-Y_{n-1}) \cdot 2^{n-2}+ ... +(Y_1 - Y_2)\cdot 2^1+(Y_0-Y_1) \cdot 2^0\right)$ （让 $Y_0=0$ ）
部分积： $P_{i+1}=2^{-1}\cdot \left(P_i+X \cdot (Y_i -Y_{i+1})\right)$
流程：
- 增加 $Y_0=0$
- 根据 $(Y_i -Y_{i-1})$ ，在和上+X/-X/不变
- 右移部分积
- 重复n次
- 在高位补充时符号扩展

除法

处理极端情况

被除数

除数

结果

非0

“除数为0”异常

“除法错”异常

非0

进一步运算

手算除法

在被除数左侧补0（符号位），将除数的最高位与被除数的次高位对齐
被除数是否够减除数
- 若够减，减去，商写入1
- 若不够减，商写入0
右移除数，重复上述步骤

无符号数除法

$2n$ bits的寄存器共享被除数（余数）和商，每做一位的运算，商和余数都左移一位

补码除法

本节中“减法”“够减”按以下定义拓展到补码的情况：

“减”：将余数（被除数）往0的方向靠近=>（被除数与除数）同减异加
“加”：减的逆运算，（被除数与除数）同加异减
“够减”：余数（被除数）往0的方向靠近时不会越过0=>“减”之前的余数和“减”完的余数同号

前面加n位符号扩展被除数，储存在余数&商寄存器中
判断“够减”
- 若“够减”：“减”，商为1
- 若“不够”：商为0
若除数和被除数异号，将商替换为相反数
余数存在余数寄存器中

恢复余数除法

按照上面思路来，“不够减”时“加”回去，即“恢复余数”
弊端：恢复余数成本高

不恢复余数除法

思路：无论够不够减都继续，后一轮执行时根据商的结果进行加/减
- 若上一位“够减”：“减”
- 若上一位“不够减”：“加”（移位后，上一次多减的 $Y$ 相当于要补 $2Y$ ，此时加 $Y$ 等效于恢复余数除法中的 $-Y$

[!NOTE]
由于不恢复余数会减过头（使得余数变号），“减”、“够减”每次的意义都有可能改变，因此直接用加、减表示，实际上“减”、“够减”的定义依然是使用的

实现
- 前面加n位符号扩展被除数，储存在余数&商寄存器中
- 计算余数：
  - 第一次：被除数“减”除数
  - 此后比较余数和除数符号：相同减，不同加
- 商：
  - 新的余数和除数符号相同：为1
  - 不同：为0
- 修正商：若除数和被除数异号，商+1
- 修正除数：若被除数和余数异号，让余数加减除数，使之与被减数同号

注意事项

加法器实现的是模 2n 无符号整数加法运算，因为
- $a-b=a_补-b_补 \mod 2n$
- $a+b=a_补+b_补 \mod 2n$
- 所以n位有符号整数加减运算都可在 n 位加法器中实现

最后更新于3个月前

05-整数运算

ALU

算术逻辑单元：完成数据算术逻辑运算的部件
ALU会根据运算结果设置Flags，存入寄存器
Control Unit控制ALU操作和数据出入ALU的信号

门延迟

与门延迟：1级门延迟
或门延迟：1级门延迟
异或门延迟：3级门延迟

加减法

全加器

$S_i=X_i \oplus Y_i \oplus C_{i-1}$ ：6ty
$C_i=X_{i}C_{i-1}+X_{i}Y_{i}+Y_{i}C_{i-1}$ ：2ty

串行进位加法器

将全加器进行串联
延迟（每一步的起始时间取决于输入中最慢计算得到的那个）：
- $C_i=C_{i-1}+2\text{ ty} \rightarrow C_n=2n\text{ ty}$
- $S_1=S_2=6$
- $S_n=C_{i-1}+3\text{ ty} \rightarrow S_n=2n+1\text{ ty } (n\geq3)$
优点：元件少
缺点：慢，和数据的位数线性相关

全先行进位加法器 CLA

思路：预先并行计算部分输入值，提高效率
定义两个辅助函数：
- 传播： $P_i=X_i+Y_i$ （将前序结果”传递“下来）
- 生成： $G_i=X_iY_i$
此时展开加法的每一位，有：
- $C_0$
- $C_1=G_1+P_1C_0$
- $C_2=G_2+P_2G_1+P_2P_1C_0$
- $C_3=G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1C_0$
- ……
延迟
- 计算 $G_i, P_i$ ： $1\text{ ty}$
- 求出所有的 $C_i$ ： $2\text{ ty}$
  - 先并行计算所有的与： $1\text{ ty}$
  - 再并行计算所有的或： $1\text{ ty}$
- 最后通过异或求出 $S_i$ ： $3\text{ ty}$
优点：效率高
缺点：元件多

部分先行加法器

串联多个CLA
权衡效率与复杂度
延迟
- $8n$ 位加法，串联 $n$ 个8-bit的CLA
- 第一个计算出给下一个的 $C_8$ 需要： $1+2=3\text{ ty}$ ， $S_i$ 不与后续元件相关，时间忽略
- 此后每一个的 $G_i,P_i$ 都预先算好，计算出给下一个的 $C_{8i}$ 需要 $2\text{ ty}$
- 最后一个计算出 $C_{8n}$ 需要 $2\text{ ty}$ ， $S_{8n}$ 需要 $3\text{ ty}$
- 因此共需 $2n+4 \text{ ty}$
- 例如 $32$ 位就是 $12 \text{ ty}$

溢出判断

无符号数

最高位产生进位

有符号补码数

出现溢出：两个数同号，但是结果和这两个数异号
判断方法
- 比较符号： $X_n=Y_n$ ，且 $S_n \neq X_n, Y_n$ $\rightarrow \text{overflow} = \bar{S_n}X_nY_n+S_n\bar{X_n}\bar{Y_n}$
- 比较进位： $C_n\neq C_{n-1}$ $\rightarrow \text{overflow} =C_n \oplus C_n-1$

减法

加相反数
数据通路：
- 对多路选择器和ALU输入加/减的信号
- 多路选择器若为减则将输入取反输出
- ALU的加减信号连接在 $C_0$ 上（合在一起就是取反+1）

乘法

手算

$Y_i=0$ ：部分积为0，否则为 $X$
每一步部分积左移一位
求和

无符号数乘法

思路

基于手算思路
算一位求和一位，减少保存开销
相加时右移先前部分积的和而非左移部分积
若 $Y_i=0$ ，只移位

实现

Y算一位右移一位（算完就可以抛弃了），留出来的空间给不断右移的结果，二者此消彼长
Y的最低位传给控制逻辑决定是否要加
最终结果的高32位在成绩寄存器中，低32位在乘数寄存器中

补码乘法

问题：积的补码不等于补码的积
简单办法：都转成原码进行无符号计算，将结果再转换为补码（开销太大）

布斯算法

补码数的真值表示： $Y=-Y_n \cdot 2^{n-1}+Y_{n-1} \cdot 2^{n-2}+...+Y_2\cdot 2^1+Y_1 \cdot 2^0$

乘积： $X \cdot Y = X \cdot \left( -Y_n \cdot 2^{n-1}+Y_{n-1} \cdot 2^{n-2}+...+Y_2\cdot 2^1+Y_1 \cdot 2^0\right)$
- $=X \cdot \left( (Y_{n-1}-Y_n) \cdot 2^{n-1} + (Y_{n-2}-Y_{n-1}) \cdot 2^{n-2}+ ... +(Y_1 - Y_2)\cdot 2^1+(Y_0-Y_1) \cdot 2^0\right)$ （让 $Y_0=0$ ）
部分积： $P_{i+1}=2^{-1}\cdot \left(P_i+X \cdot (Y_i -Y_{i+1})\right)$
流程：
- 增加 $Y_0=0$
- 根据 $(Y_i -Y_{i-1})$ ，在和上+X/-X/不变
- 右移部分积
- 重复n次
- 在高位补充时符号扩展

除法

处理极端情况

被除数

除数

结果

非0

“除数为0”异常

“除法错”异常

非0

进一步运算

手算除法

在被除数左侧补0（符号位），将除数的最高位与被除数的次高位对齐
被除数是否够减除数
- 若够减，减去，商写入1
- 若不够减，商写入0
右移除数，重复上述步骤

无符号数除法

$2n$ bits的寄存器共享被除数（余数）和商，每做一位的运算，商和余数都左移一位

补码除法

本节中“减法”“够减”按以下定义拓展到补码的情况：

“减”：将余数（被除数）往0的方向靠近=>（被除数与除数）同减异加
“加”：减的逆运算，（被除数与除数）同加异减
“够减”：余数（被除数）往0的方向靠近时不会越过0=>“减”之前的余数和“减”完的余数同号

前面加n位符号扩展被除数，储存在余数&商寄存器中
判断“够减”
- 若“够减”：“减”，商为1
- 若“不够”：商为0
若除数和被除数异号，将商替换为相反数
余数存在余数寄存器中

恢复余数除法

按照上面思路来，“不够减”时“加”回去，即“恢复余数”
弊端：恢复余数成本高

不恢复余数除法

思路：无论够不够减都继续，后一轮执行时根据商的结果进行加/减
- 若上一位“够减”：“减”
- 若上一位“不够减”：“加”（移位后，上一次多减的 $Y$ 相当于要补 $2Y$ ，此时加 $Y$ 等效于恢复余数除法中的 $-Y$

[!NOTE]
由于不恢复余数会减过头（使得余数变号），“减”、“够减”每次的意义都有可能改变，因此直接用加、减表示，实际上“减”、“够减”的定义依然是使用的

实现
- 前面加n位符号扩展被除数，储存在余数&商寄存器中
- 计算余数：
  - 第一次：被除数“减”除数
  - 此后比较余数和除数符号：相同减，不同加
- 商：
  - 新的余数和除数符号相同：为1
  - 不同：为0
- 修正商：若除数和被除数异号，商+1
- 修正除数：若被除数和余数异号，让余数加减除数，使之与被减数同号

注意事项

加法器实现的是模 2n 无符号整数加法运算，因为
- $a-b=a_补-b_补 \mod 2n$
- $a+b=a_补+b_补 \mod 2n$
- 所以n位有符号整数加减运算都可在 n 位加法器中实现

最后更新于3个月前