首页 计算机组成

# 串行进位加法器

# 并行进位加法器

Gi=XiYi进程生成函数G_i=X_iY_i进程生成函数
Pi=Xi+Yi进位传递函数P_i=X_i+Y_i进位传递函数

全加逻辑方程Si=Pi⊕CiCi+1=Gi+PiCi全加逻辑方程\\ S_i=P_i \oplus C_i \\ C_{i+1}=G_i+P_iC_i

# ALU

# 实现 11 条 MIPS 指令的 ALU

# 定点数、浮点数运算

# 整数加减法


Sub=0, 做加法；Sub=1, 做减法
ZF：Sum 为 0，则为 1
SF：sum 符号
OF：A 与 B' 同号但与 Sum 不同号，则为 1
CF：Cout⊕subCout\oplus sub

  • 做加法时，主要判断溢出
  • 无符号加溢出条件：CF=1
  • 带符号加溢出条件：OF=1

# 无符号数的乘法运算

# 无符号乘法运算的推导

X×Y=X×(0.y1y2…yn)=∑X×yi×2−i设P0=0P1=2−1(P0+X×yn)P2=2−1(P1+X×yn−1)Pn=2−1(Pn−1+X×y)X\times Y=X\times(0.y_1y_2\dots y_n)=\sum{X\times y_i\times 2^{-i}}\\ 设P_0=0 \\ P_1=2^{-1}(P_0+X\times y_n)\\ P_2=2^{-1}(P_1+X\times y_{n-1})\\ P_n=2^{-1}(P_{n-1}+X\times y)\\

# 示例

# 原码乘法算法

符号位异或得到，数值采用无符号乘法运算

# 两位乘法算法

00Pi+1=2−2Pi01Pi+1=2−2(Pi+X)10Pi+1=2−2(Pi+2X)11Pi+1=2−2(Pi+3X)=2−2(Pi−X)+X00 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]补=xn−1xn−2...x0[X]_补=x_{n-1}x_{n-2}...x_0，[Y]补=yn−1yn−2...y0[Y]_补=y_{n-1}y_{n-2}...y_0

则Y=−yn−12n−1+yn−22n−2+...+y020Y=-y_{n-1}2^{n-1}+y_{n-2}2^{n-2}+...+y_02^0
部分积公式: Pi=2−1(Pi−1+(yi−2−yi−1)X)P_i=2^{-1}(P_{i-1}+(y_{i-2}-y_{i-1})X)

# Booth's 算法实质

对于一个二进制数B=−Bn−12n−1+(∑i=0n−2Bi∗2i)令B−1=0展开后B=(Bn−2−Bn−1)2n−1+(Bn−3−Bn−2)2n−2+⋯+(B−1−B0)20对于一个二进制数B=-B_{n-1}2^{n-1}+(\sum_{i=0}^{n-2}B_i*2^i)\\ 令B_{-1}=0\\ 展开后B=(B_{n-2}-B_{n-1})2^{n-1}+(B_{n-3}-B_{n-2})2^{n-2}+\dots+(B_{-1}-B_0)2^0

当yi−1=yn−2,Pi=2−1Pi−1y_{i-1}=y_{n-2},P_i=2^{-1}P_{i-1}，右移一位

当yi−1yi−2=01,Pi=2−1(Pi−1+X)y_{i-1}y_{i-2}=01,P_i=2^{-1}(P_{i-1}+X)

当yi−1yi−2=10,Pi=2−1(Pi−1−X)y_{i-1}y_{i-2}=10,P_i=2^{-1}(P_{i-1}-X)

# 补码两位乘法

对于一个二进制数B=−Bn−12n−1+(∑i=0n−2Bi∗2i)令B−1=0展开后B=(−2Bn−1+Bn−2+Bn−3)2n−2+(−2Bn−3+Bn−4+Bn−5)2n−4+⋯+(−2B1+B0+B−1)20对于一个二进制数B=-B_{n-1}2^{n-1}+(\sum_{i=0}^{n-2}B_i*2^i)\\ 令B_{-1}=0\\ 展开后B=(-2B_{n-1}+B_{n-2}+B_{n-3})2^{n-2}+(-2B_{n-3}+B_{n-4}+B_{n-5})2^{n-4}+\dots+(-2B_1+B_0+B_{-1})2^0

由补码乘法部分积公式推出Pi+2=2−2(Pi+(yi−1+yi−2yi+1)X)P_{i+2}=2^{-2}(P_{i}+(y_{i-1}+y_i-2y_{i+1})X)
判断y_{i+1}y_{i}y_

# 无符号数除法

# 第一次试商为 1 的情况

  • 若是 2n 位除以 n 位的无符号整数运算，则说明将会得到多于 n+1 位的商，因而结果 “溢出”（即：无法用 n 位表示商）。
    例：1111 1111/1111 = 1 0001
  • 若是两个 n 位数相除，则第一位商为 0，且肯定不会溢出，为什么？
    最大商为：0000 1111/0001=1111
  • 若是浮点数中尾数原码小数运算，第一次试商为 1，则说明尾数部分有 “溢出”，可通过浮点数的 “右规” 消除 “溢出”。所以，在浮点数运算器中，第一次得到的商 “1” 要保留。
    例：0.11110000/0.1000=+1.1110

# 硬件实现

除数寄存器 Y: 存放除数
余数寄存器 R: 初始高 32 位被除数；结束时余数
余数 / 商寄存器 Q: 初始低 32 位被除数；结束时 32 位商
循环次数计数器 Cn:32

# 原码除法

# 恢复余数法

符号位:

被除数减去除数，够减上 1，不够减上 0，同时恢复余数

# 不恢复余数法

$R_i>0 ，商上 1，R_{i+1}=2R_i-Y R_i<0 ，商上 0，R_{i+1}=2R_i+Y$

# 整数的乘法

X*Y 的高 n 位可以用来判断溢出，规则如下：
无符号：若高 n 位全 0，则不溢出，否则溢出
带符号：若高 n 位全 0 或全 1 且等于低 n 位的最高位，则不溢出

# 整数的除法

因为整数除法，其商也是整数，所以，在不能整除时需要进行舍入，通常按照朝 0 方向舍入，即正数商取比自身小的最接近整数（Floor，地板），负数商取比自身大的最接近整数（Ceiling，天板）

不能整除时，采用朝零舍入，即截断方式
无符号数、带符号正整数（地板）：移出的低位直接丢弃
带符号负整数（天板）：加偏移量2k−12^k-1，然后再右移 k 位 ，低位截断（这里 K 是右移位数）

# 浮点数运算

# IEEE 754 标准

阶码上溢：正指数超过 127
阶码下溢：负指数超过 - 126
尾数溢出：最高有效位进位
非规格化尾数：数值部分最高位为 0

硬件陷阱:事先设定好是否要进行硬件处理，当发现异常时，硬件自动进行异常处理

# 浮点数加减法

假定 Xm 和 Ym 是 X,Y 尾数，Xe 和 Ye 为 X,Y 阶码

  1. 求Δe=Ye−Xe(假定Ye>Xe)\Delta{e}=Ye-Xe(假定Ye>Xe)
  2. XmXm 右移Δe\Delta{e} 位
  3. 尾数加减Xm2Xe−Ye±Xm2^{Xe-Ye}\pm

# 附加位

IEEE 754 规定在中间结果右边加两个附加位
Guard: significand 右边位
Round: 保护位右边位

# IEEE 754 舍入方式

  1. 就近舍入:
  • 01 舍
  • 11 入
  • 10 强迫结果为偶数
  1. 正向舍入
  2. 负向舍入
  3. 0 方向舍入