计算机组织结构(二) 定点运算

📚 文档目录
合集-数的二进制表示-定点运算-BCD 码-浮点数四则运算-内置存储器-Cache-外存-纠错-RAID-内存管理-总线-指令集: 特征- 指令集:寻址方式和指令格式

1. 移位运算

1.算数移位

符号位不变, 左移相当于乘以 2, 右移相当于除以 2(左侧全补符号位).

2. 逻辑移位

无符号数的移位, 右移时永远在高位填 0.

2. 加法运算

1. 全加器

$𝑆𝑖=𝑋𝑖⊕𝑌𝑖⊕𝐶{𝑖−1}$
$𝐶𝑖=𝑋𝑖𝐶{𝑖−1}+𝑌𝑖𝐶{𝑖−1}+𝑋𝑖𝑌_𝑖$

2. Serial Carry Adder

缺点: 速度慢.
延时(OR AND 1ty, XOR 3ty)
- Cn: 2n ty
- Sn: 2n+1 ty

3. Carry Look Ahead Adder

注意：这里的+均为“或”

$\begin{aligned} 𝐶_𝑖&=𝑋_𝑖𝐶_{𝑖−1}+𝑌_𝑖𝐶_{𝑖−1}+𝑋_𝑖𝑌_i\\ \\ C_1&=𝑋_1𝑌_1+(𝑋_1+𝑌_1)𝐶_0\\ 𝐶_2&=𝑋_2𝑌_2+(𝑋_2+𝑌_2)𝑋_1𝑌_1+(𝑋_2+𝑌_2)(𝑋_1+𝑌_1)𝐶_0\\ 𝐶_3&=𝑋_3𝑌_3+𝑋_3+𝑌_3𝑋_2𝑌_2+𝑋_3+𝑌_3𝑋_2+𝑌_2𝑋_1𝑌_1 +(𝑋_3+𝑌_3)(𝑋_2+𝑌_2)(𝑋_1+𝑌_1)𝐶_0\\ C_4 &=... \end{aligned}$

可见,$Ci$ 仅与最初的X Y和 $C0$有关.
令$𝑃𝑖=𝑋𝑖+𝑌𝑖, 𝐺𝑖=𝑋𝑖𝑌_i$
则:

$\begin{aligned} \\ 𝐶_1&=𝐺_1+𝑃_1𝐶_0\\ 𝐶_2&=𝐺_2+𝑃_2𝐺_1+𝑃_2𝑃_1𝐶_0\\ 𝐶_3&=𝐺_3+𝑃_3𝐺_2+𝑃_3𝑃_2𝐺_1+𝑃_3𝑃_2𝑃_1𝐶_0\\ 𝐶_4&=... \end{aligned}$

总结得:$C{i+1} = G{i+1}+P_{i+1}C_i$, 超前进位加法器采用的是将低一位的逻辑代数代入高一位, 依此类推最终每一个进位输出仅考虑 $C_0, X_i, Y_i$几个信号, 于是所有的进位都能同时计算.

缺点:复杂
延时: 1 ty+ 2ty + 3 ty = 6 ty

4. Partial Carry Look Ahead Adder

结合两者

5. 溢出判断

$Cn\oplus C{n-1} =1$, 即符号位进位与最高有效位进位不同时,发生溢出.
$𝑋𝑛 𝑌𝑛 \overline{𝑆𝑛}+\overline{𝑋𝑛𝑌𝑛}𝑆𝑛=1$,则溢出,与上面等价.

3. 减法运算

减法运算大致与加法相同,只需要将减数取反加一然后按加法算即可, 注意加一的操作是令 $C_0 = 1$.

4. 乘法运算

1. 无符号整数乘法

通过加法和移位实现,与竖式乘法极其类似,但是计算机很难像人类那样一次性把各位乘的结果一次性相加,因此采用部分积的方式:
例:$0111\times0110$

部分积	乘数	得到当前行的操作
0000	0110	部分积+乘数末位$\times 0111$
0000	0011	右移
0111	0011	部分积+乘数末位$\times 0111$
0011	1001	右移
1010	1001	部分积+乘数末位$\times 0111$
0101	0100	右移
0101	0100	部分积+乘数末位$\times 0111$
0010	1010	右移

乘数末位决定被乘数是否加到部分积,然后部分积和乘数均右移,部分积低位保存到乘数高位.
被乘数只与部分积高位相加

原理:

$\begin{aligned} XY &= XY_nY_{n-1}...Y_2Y_1\\&=X(Y_n\times2^{n-1}+Y_n\times2^{n-2}+...+Y_2\times2^1+Y_1\times2^0)\\&=2^n(XY_n\times2^{-1}+XY_{n-1}\times2^{-2}+...+XY_1\times2^{-n})\\ &=2^nP_{n},其中P_{n} = 2^{-1}\times(XY_{n}+P_{n-1}),n\gt1.\end{aligned}$

2. 补码整数乘法

根据上面无符号整数的原理, 可以将二进制补码整数相乘变形如下:

$\begin{aligned}XY& = XY_nY_{n-1}...Y_2Y_1\\&=X(-Y_n\times2^{n-1}+Y_n\times2^{n-2}+...+Y_2\times2^1+Y_1\times2^0)\\&=2^nX((Y_{n-1}-Y_n)\times2^{-1}+(Y_{n-2}-Y_{n-1})\times2^{-2}+...+(Y_0-Y_1)\times2^{-n})\\& =2^nP_{n},其中Y_0=0,P_{n} = 2^{-1}\times(X(Y_{n-1}-Y_{n})+P_{n-1}),n\gt1.\end{aligned}$

形式上还原了,只是每次乘的不是乘数的末位数, 且注意是算数右移,需要补符号位,
例: $-7\times-6 = 42,即 1001\times1010=00101010$

部分积	乘数	得到当前行的操作
0000	10100	部分积+$(Y_0-Y_1)\times 1001$
0000	01010	右移
0111	01010	部分积+$(Y_1-Y_2)\times 1001$
0011	10101	右移
1100	10101	部分积+$(Y_2-Y_3)\times 1001$
1110	01010	右移
0101	01010	部分积+$(Y_3-Y_4)\times 1001$
0010	10101	右移

5. 除法运算

1. unsigned

1.人的计算:除数右移, 2n位

竖式计算:

余数	除数	商
00000111	00110000	0000
00000111	00011000	0000
00000111	00011000	0000
00000111	00001100	0000
00000111	00001100	0000
00000111	00000110	0000
00000001	00000110	0001
00000001	00000011	0001
00000001	00000011	0010

计算机的计算: 余数左移, n位

余数	商	除数
0000	0111	0011
0000	111	0011
0000	1110	0011
0001	110	0011
0001	1100	0011
0011	100	0011
0000	1001	0011
0001	001	0011
0001	0010	0011

2. 带有符号的除法

如何判断余数(的绝对值)是否大于除数(的绝对值)?
- 同号则减, 异号则加. 与结果符号相同的那个数绝对值大

remainder sign	Divisor sign	Subtraction		Addition
remainder sign	Divisor sign	0	1	0	1
0	0	Enough	Not enough	----	----
0	1	----	----	Enough	Not enough
1	0	----	----	Not enough	Enough
1	1	Not enough	Enough	----	----

恢复余数法 在下面的步骤中,余数和除数的和是存储在余数寄存器里面的,判断完成后,还要恢复原来的余数(即减去余数).之前的不带符号位除法也都是恢复余数法,只是没有表示出来.

余数	商	除数	得到本步操作
1111	1001	0011	-
1111	001	0011	左移
1111	0010	0011	1111+0011 =0010,not enough
1110	010	0011	左移
1110	0100	0011	1110+0011=0001, not enough
1100	100	0011	左移
1111	1001	0011	1100+0011=1111, enough
1111	001	0011	左移
1111	0010	0011	1111+0011=0010,not enough

最后,结果取 0010 的补码整数 1110 为最终结果.

缺点:Problem: recover remainder is high cost
解决方案:使用不恢复余数法(加减相消法)

加减相消法.
- 规则
  - 将被除数符号拓展 n 位后存储在余数和商寄存器.
  - 如果被除数与除数符号相同, 作减法; 若符号位不同, 作加法.
    - 若新的余数与除数符号相同, 上商 1; 否则上商 0.
  - 新的余数(指左移前的余数)与除数符号位相同, 则 $R{i+1}= 2R_i-Y$, 即余数=余数<<1-除数;否则$R{i+1}= 2R_i+Y$
- 商的修正:
  - 商左移一位. 若被除数和除数异号(即商为负), 商加一
  - 若余数与被除数符号不同:
    - 若被除数和除数同号,余数加除数
    - 若被除数和除数异号,余数减除数
  - 注意：若做完如上修正后，余数为除数相反数，需要将余数置为0，同时商减一
- 示例: