第五讲 整数运算
算术逻辑单元 ALU
算术逻辑单元(ALU) 是计算机实际完成数据算术逻辑运算的部件
- 数据由寄存器(Registers) 提交给ALU，运算结果也存于寄存器
- ALU可能根据运算结果设置一些标志(Flags)，标志值也保存在处理器内的寄存器中
- 控制器(Control unit) 提供控制ALU操作和数据传入送出ALU的信号
全加器
第i位的结果 Si = Xi ⊕ Yi ⊕ Ci-1
第i位的进位 Ci = XiCi-1 + YiCi-1 + XiYi
门延迟
与门: 1 ty
或门: 1 ty
异或门: 3ty
所以算第i位进位: 2ty延迟
算第i位结果: 6ty延迟
串行进位加法器
Cn延迟: 2n ty
Sn延迟: (2n + 1)ty 当n>=3时
2n-2算出Cn-1, 再进行一次异或 +3
为什么n>=3, 因为当 n<3 时, Xi ⊕ Yi 消耗3ty, 此时Cn-1 还没算好
缺点: 慢
全先行进位加法器
利用Ci的递推式, 超前进位, 把每一步的Ci都计算出来
定义两个辅助函数
- Pi = Xi + Yi
- Gi = XiYi
C1 = G1 + P1C0
C2 = 𝐺2+𝑃2𝐺1+𝑃2𝑃1𝐶0
C3 = 𝐺3+𝑃3𝐺2+𝑃3𝑃2𝐺1 +𝑃3𝑃2𝑃1𝐶0
…
每一个Pi都可以一起计算, 1ty
每一个Gi也都可以一起计算, 1ty
甚至Pi和Gi是可以同时一起计算的只要1ty, 全部的Pi, Gi都计算好
再经过2ty, 把所有的Ci计算好
最开始就计算每一个Xi ⊕ Yi, 经过3ty后都计算好
最后再异或Ci
总共经过 1+2+3=6ty
缺点: 复杂
部分先行进位加法器
采用多个CLA并将其串联，取得计算时间和硬件复杂度之间的权衡
3ty + 2ty + 2ty + 5ty = 12ty
乘法
原码的乘法
手工演算乘法
- 若𝑌𝑖 =0，部分积为0；否则，部分积为X
- 每一步的部分积相比之前左移一位
- 对所有部分积求和
补码的乘法
手工演算乘法: 把补码转为原码, 再根据正负号将结果转化为补码
计算机演算: 布斯算法
除法
手工演算除法
- 在被除数的左侧补充0（符号位），将除数的最高位与被除数的次高位对齐
- 从被除数中减去除数，若够减，则上商为1；若不够减，则上商为0
- 右移除数，重复上述步骤