《计算机原理与系统结构》学习系列——计算机的算数运算（上）

系列文章目录

---

目录

• ALU
• 行波进位加法器
• 超前进位加法器
• 整数运算
• 加减法
• 乘法
• 无符号数相乘
• N位乘法数的工作流程
• N位乘法器改进：硬件资源
• 更快速的乘法 
• MIPS中的乘法
• 除法 
•  32位除法器流程
• 除法器改进 
•  更快速的除法
•  MIPS中的除法
• 总结

---

ALU

 ALU功能：对a，b（0，1）完成

• 算数运算
• 逻辑运算

行波进位加法器

上图为一位ALU，32个一位ALU组合成为32位ALU。低位的进位输出指向高位的进位输入，最低位的进位输入用于控制减法，这种直接连接1位进位的加法器称为行波进位加法器

超前进位加法器

进位速度制约了加法的速度，32位ALU的行波进位方式在每次进位时都要通过与门、或门各一次，共产生64个门延迟

使用超前进位加法器，通过将进位分成4位一组，抽象成每组进位，实现加法器的并行执行

具体原理比较复杂，结论：要执行n位加减法，求出n是4的几次方并向上取整，在乘二加1，就是超前进位的门延迟

---

整数运算

加减法

例子：5+6

三个输入：A，B，CarryIn

两个输出：Sum，CarryOut

CarryIn(i+1) = CarryOut(i)

减法就是加上数的负值

例子：7-6=7+（-6）

如果结果超出表示范围就会发生溢出

• 两个正数相加，结果为负，发生溢出
• 两个负数相加，结果为正，发生溢出
• 正数和负数相加，永远不会溢出
• 其他情况，都未发生溢出

行波加法器中加减法

Cn 与 Cn-1 进行异或逻辑操作，以判断是否有溢出

5+6：

 5-6：

---

乘法

无符号数相乘

例子：A=1101  B=1011 

乘积的位数是乘数和被乘数之和 

N位乘法数的工作流程

用4位乘法做例子

迭代	步骤	乘数	被乘数	积product
0	初始值	001①	0000 0010	0000 0000
1	1:1→积=积+被乘数	0011	0000 0010	0000 0010
	2：左移被乘数	0011	0000 0100	0000 0010
	3：右移乘数	000①	0000 0100	0000 0010
2	1:1→积=积+被乘数	0001	0000 0100	0000 0110
	2：左移被乘数	0001	0000 1000	0000 0110
	3：右移乘数	000 0	0000 1000	0000 0110
3	1: 无操作	0000	0000 1000	0000 0110
	2：左移被乘数	0000	0001 0000	0000 0110
	3：右移乘数	000 0	0001 0000	0000 0110
4	1：无操作	0000	0001 0000	0000 0110
	2：左移被乘数	0000	0010 0000	0000 0110
	3：右移乘数	0000	0010 0000	0000 0110

时间效率 

N位乘法器改进：硬件资源

注意到每进行一次迭代，乘积从32增长到64，乘数位从32减少到0，合起来永远是64，可以拼接成为一个64位乘积/乘数寄存器，让积相对于被乘数右移（而不是乘数相对于积左移），ALU从64位缩减到32位，改进后硬件规模减小，每一步仅占一时钟周期

更快速的乘法 

速的乘法运算主要的思想是为乘数的每一位提供一个 32 位的加法器： 一个用来输入被乘数和 一乘数位相与的结果 ，另一个是上一个加法器的输出
 一种直接 的方法是将每个右边的加法器的输出作为左边加法器的输入，形成一个 高 32 的加法器栈 。一种替换的方法是将 32 个加法器组织成一个并行树

MIPS中的乘法

IPS 提供了 一对单独的 32 位寄存器来容纳 64 位的积，称为 Hi 和 Lo 。 为了产生正确的有符号积和无符号积， MIPS 提供了两条指令：乘法 (mult) 和无符号乘法 (multu) 。 为了取得 32 位的整数积，程序员需要使用 mflo 指令 (move from lo) 。 MIPS 汇编器为乘法生成了 一条伪指令，它使用了 三个通用寄存器，用 mflo 和 mf肛指令将积送入指定的寄存器 。

---

除法 

• 除数判0 
• 除法步骤
  • 除数≤被除数
    • 商添加1，执行减法
  • 否则
    • 商添加0，从被除数中提取下一位
• 恢复余除法：直接执行减法，结果小于0后再把除数加回去

 32位除法器流程

在任何情况下，整数除法都要满足被除数=除数×商+余数

计算-7/2时，可以商-3余1，也可以商-4余1

为了避免这种差异，规定余数和被除数同号，即商-3余-1 

硬件

被除数一开始存在64位余数寄存器中，除数从64位除数寄存器的高32位逐次右移到低32位，每次迭代，向32位商寄存器的最低位添加0或1 ，执行33次迭代

 例子：7/2

除法器改进 

注意到每轮迭代，余数（一开始是可以看作被除数）位数从64减少到32，商的位数从0增加到32合起来总是64位，可以拼接成一个64位余数/商寄存器，最后余数就是整个除法的余数

 更快速的除法

与乘法相同，摩尔定律同样适用千除法 。 我们使用许多加法器来加速乘法，但这一招对除法却不管用 。 因为除法算法每次迭代前需要知道减法结果的符号，而乘法却可以立刻生成 32个部分积

有一些技术可以每步生成不仅一个商位 。 如被称为 SRT 的除法算法，通过查找表的方法来尝试猜测每步儿个商位，其中查找表基于被除数和余数的高位部分来进行 。 它依赖后面的步骤来修正错误的猜测 。 如今典型值是 4 位 。 算法的关键是猜测要减的值 。 对于二进制算法，只有一种选择 。 可用余数的 6 位和除数的 4 位来索引查找表，从而决定每步的猜测 

这个快速算法的正确性取决于查找表中的值是否合适

 MIPS中的除法

为了处理有符号整数和无符号整数， MIPS 采用两条指令：除 (div) 和无符号除 (di 一 vu) 。 MIPS 汇编器允许除指令使用三个寄存器，且采用 mflo 和 mfhi 指令将运算结果放入指 定的通用寄存器

---

总结