计算机组成指北（三）

第五章输入输出系统

相对来说不是那么重要的一章，只需理解概念就可

输入输出系统知道概念，I/O处理机知道干嘛就行。主要要知道三种控制方式：程序查询方式、中断方式、dma方式

CPU除了要和存储器交换信息外，还需要和外部设备进行通信。这一章我们来介绍计算机的输入输出系统。

I/O系统发展概况

I/O系统发展经历了四个阶段：

分散连接。早期主机和I/O设备分散直连，I/O的控制由CPU来负责，因此整个I/O期间I/O和CPU需要一直保持联络，由于速率的不对等，因此一个I/O周期中CPU大部分时间处于是停等状态。
接口模块和DMA阶段。为了提高效率，出现了I/O接口和DMA控制器。I/O设备通过I/O接口连入I/O总线，DMA控制器专门负责I/O的控制，从而解放出CPU，使得CPU在I/O周期间不必停等。CPU和I/O之间是并行的。此方式中I/O的控制均交给DMA控制器来完成（指令交给控制器来负责），但是控制器不具备数据的处理功能（如读数、写数），因此数据的处理功能仍然要走CPU。
通道。一种简单的处理器，比起DMA多了数据处理功能，使得I/O的控制、数据处理完全从CPU中剥离出来，为CPU减负。一个通道可以连接多个I/O设备，即一条通道供多个I/O设备“行走”。
I/O处理机。通道技术的升级版，直接采用和主机CPU结构相同的小型CPU来完全负责I/O的控制和数据处理。

I/O设备与主机信息传送的控制方式

分为程序查询方式，中断方式，DMA方式三种。

程序查询方式

结构图如下：

数据先到CPU寄存器，再转存到主存当中。这种方式CPU会一直反复查询I/O设备的状态，仿佛在原地踏步，将CPU和I/O设备处于串行的工作状态，因此工作效率不高。

中断方式

结构图如下：

执行第K条指令时，如果外部设备准备好，将向CPU提出一个中断请求，此时再开始向CPU传送数据，而CPU无须终止原程序的执行，没有“踏步”现象，提高了工作效率。但是这需要额外增加相应的电路，并在软件中编制中断服务的程序。

DMA方式

虽然用程序中断方式消除了“踏步”现象，但是CPU接到响应请求后，必须停止现行程序而转入中断服务，这也是对CPU资源的消耗。因此，我们采用直接存储器存取/DMA的方式，让I/O设备通过总线直接与主存交换信息，这样就进一步节省了CPU的资源。

DMA要使用总线，所以有周期挪用。

DMA发出请求，占用总线存取周期，用于I/O和主存间数据传输。

第六章计算机的运算方法

全程高能，必考且重要且晦涩

我们已经了解了计算机如何与外界进行通信，以及外部的运行原理。现在，让我们把目光看向计算机中最重要也是最精巧的组成部分：中央处理器CPU（Central Process Unit）。CPU主要由四个部分组成：

ALU，算数逻辑单元。负责执行所有的算术运算和逻辑运算。
寄存器。一组快速的存储位置，用于临时存储指令、数据和地址等信息。寄存器直接与ALU交互，比主存储器快得多。
中断系统。允许外部设备或软件中断当前的程序执行流程，以响应紧急事件或需求。
CU，控制单元。负责解释指令并生成控制信号，以协调CPU内部各部件的操作和其他系统组件。

本章中，我们着力学习计算机的ALU部分。

这里主要复习计算机的内部运算和算术逻辑单元的实现，至于基础的机器数表示方法则不过多介绍，可以参考我在数字逻辑是做的笔记：数字逻辑小结（一）—— 数制基础 | Adam8en の 8log

这里只简单的介绍原码、反码、补码、移码的概念

原码：一个二进制数，包括一个符号位和数值位。符号位等于0为正数，等于1为负数。
反码：正数的反码是它本身，负数的反码是除符号位外全部取反。
补码：正数的补码是它本身，负数的补码是它的反码末位+1。
移码：n为整数的位数，[x]_移=2ⁿ+x；与补码的区别只有符号位相反。

数的定点表示

在定点机中，定点表示有两种方式：小数定点机和整数定点机。

在小数定点机中，小数点位于数符和数值部分之间，表示纯小数。
在整数定点机中，小数点位于数值部分末尾，表示纯整数。

当机器处理的数不是一个纯小数或者纯整数时，必须要乘以一个“比例因子”，不然会产生溢出。

数的浮点表示

浮点数的一般表现形式为： $N=S\times r^j$ 。

其中 $S$ 为尾数， $j$ 为阶码， $r$ 为基数；r可以取2、4、6、8、16等（一般取2）。

比如N=11.0101=1.10101×2¹=0.110101×2¹⁰（二进制）。在计算机中 $S$ 是小数， $j$ 是整数，均可正可负。

表示形式

计算机中一般使用如下结构来表示一个浮点数：

S_f代表浮点数的符号
n反映浮点数的精度
m反映浮点数的表示范围
j_f和m共同表示小数点的实际位置

表示范围

这个不强求记忆，看看图理解就好了

规格化形式

规格化数，即要求尾数的最高位为1。

故N=11.0101的规格化数的表现形式为0.110101×2¹⁰。

规格化数中，原码不论正负数第一数位都为1，而补码符号位和第一数位不同。

左规：尾数左移一位，阶码减 1，直到数符和第一数位不同为止。
右规：当尾数溢出（ >1）时，需右规；尾数右移一位，阶码加 1。

例题：将 $+\frac{19}{128}\\$ 写成二进制定点数、浮点数及在定点机和浮点机中的机器数形式。其中数值部分均取 10 位，数符取 1 位，浮点数阶码取 5 位（含1位阶符）。

二进制形式：0.0010011

定点表示：0.0010011000

浮点化规格表示：0.1001100000×2^-10

定点机：[x]_原 = [x]_补 = [x]_反 = 0.0010011000

浮点机：[x]_原 = 1, 0010; 0. 1001100000

[x]_补 = 1, 1110; 0. 1001100000

[x]_反 = 1, 1101; 0. 1001100000

定点运算

重要⚠️！复习提纲上没有涉及浮点数的四则运算，所以这就是Boss了。

移位运算

算数移位规则·符号位不变
真值	码制	添补代码
正数	原码、补码、反码	0
负数	原码	0
	补码	左移添0
	补码	右移添1
	反码	1

通过移位来进行加减法运算。

移位又分算术移位和逻辑移位，算术移位上述表格已经给出规则，适用于有符号数的运算。对于无符号数的运算，通常使用逻辑移位。

逻辑左移：低位添0，高位移丢
逻辑右移：高位添0，低位移丢

加减法运算

补码加减法运算公式有：

加法：
- 整数：[A]_补 + [B]_补= [A+B]_补（mod 2ⁿ⁺¹）
- 小数：[A]_补 + [B]_补= [A+B]_补（mod ²）
减法：

即加上相反数的加法运算A-B=A+(-B)
- 整数：[A – B]_补= [A+(–B )]_补= [A]_补 + [ – B]_补(mod 2ⁿ⁺¹)
- 小数：[A – B]_补= [A+(–B )]_补= [A]_补 + [ – B]_补(mod 2)

即加上两数的补码，连同符号位一起相加，符号位产生的进位自然丢掉。

溢出判断

溢出有分两种情况：一位符号位的溢出与两位符号位的溢出

先讨论一位符号位的：

参加操作的两个数（减法时即为被减数和“求补”以后的减数）符号相同，其结果的符号与原操作数的符号不同时，即为溢出。

再来看两位符号位的溢出：

即把符号位写两遍，然后进行运算。如果双符号位最终不同，就为溢出。

乘法运算

原码一位乘

观察下图，我们可以总结规律：

概括一下定点原码一位乘的步骤：先在0上加一个被乘数，右移一位；再在部分积上逆序乘数加，同时被乘数继续右移一位。

乘法运算可用加和移位实现。当n = 4时，加 4 次，移 4 次。由乘数的末位决定被乘数是否与原部分积相加，然后右移1位形成新的部分积，同时乘数右移1位（末位移丢），空出高位存放部分积的低位。然后再将被乘数只与部分积的高位相加。

如果对象是小数，那么数值部分按以上规则用绝对值相乘，符号位部分单独做异或处理。

归纳成次序步骤可以总结如下：

列出竖式，写出被乘数和乘数的数值部分
首先，初态为0，加上一个被乘数
得到的和应该和被乘数相等，然后右移一位得到第一个部分积。同时乘数也要右移一位。
此时，引入乘数，根据乘数的末尾值是否1来判断是否加上一个被乘数。如果为1，则加上一个被乘数；如果为0，则加上0。（这里假设末位为1）
部分积加上一个乘数，得到一个和。
将和右移一位得到新的部分积，同时乘数右移一位：低位直接移丢，空出来的高位用来存储部分积右移移丢的低位值。
重复以上步骤n次，n为被乘数与乘数的长度，最后的积即为部分积拼接上乘数，此时存储乘数的寄存器内存储的应该是被乘数部分积在不断右移中移丢的低位积部分。
符号位单独异或处理，判断正负。

需要硬件实现：3个具有移位功能的寄存器，1个全加器。

以下竖式笔算计算机乘法（13×11=143=10001111）步骤供参考：

拼接被乘数和乘数寄存器内的数值，最后结果为0.10001111，经验证正确。

原码一位乘的特点是：

绝对值运算
用移位的次数判断乘法是否结束
逻辑移位

原码两位乘

原码乘的含义是：符号位和数值位部分分开运算
两位乘的含义是：每次用乘数的2位判断原部分积是否加和如何加被乘数

运算法则如下表所示：

乘数y_n-1y_n	新的部分积
0 0	加0，右移两位
0 1	加1倍的被乘数，右移两位
1 0	加2倍的被乘数，右移两位
1 1	加3倍的被乘数，右移两位

我们知道加1倍的被乘数就是直接算加法，两倍的被乘数就是先把被乘数进行算数左移1位后再与原部分积相加，那么3倍的被乘数怎么算呢？

答案是通过先减去1倍的被乘数再加上4倍的被乘数，也就是减去一个被乘数后再加上被乘数算数左移2位的值，我们需要留到下次再加，用一个进位标志C，来记录这次没加上的4倍。至于减法，我们选择计算加上其相反数的补码，这样可以方便运算。

引入进位标志C后，运算规律可以参考下列的表格，更加逻辑化：

这里给出一个例题，原码二位乘的运算过程可以参考如下：

要加2x，和的绝对值可能大于2，因此小数点左边取3位，最高位才是真正的符号位。

注意：在乘数（偶数）前面加两个0/（奇数）前面加一个0，若仍有进位没处理时，可以处理掉，使C重新等于0。这些添加的0非乘数本身数值，因此最后一步不用移位

其中符号位仍然继续使用异或来判断。

原码二位乘加快了计算机的远算速度，有以下几个特点：

绝对值的补码运算
用移位的次数判断乘法是否结束
算术移位

相比原码一位乘只是多了个补码运算，用于计算减法。

下表列出了原码一位乘和原码二位乘的比较：

	原码一位乘	原码两位乘
符号位	x₀⊕y₀	x₀⊕y₀
操作数	绝对值	绝对值的补码
移位	逻辑右移	算数右移
移位次数	$n$	$\frac{n}2(n为偶数)$ ， $\frac{n}2+1(n为奇数)$
最多加法次数	$n$	$\frac{n}2+1(n为偶数)$

补码一位乘

我先给出PPT上的运算方法

补码一位乘，又称校正法。我不知道多少人是和我一样根本看不懂这一页是在讲什么的，但是好歹只是个求补码，我决定还是采用自己的方法去计算，即：除符号位全部取反后末位加1。

所以这里我们抛开晦涩的教材，自己来总结一下补码一位乘的计算方法，其实大致和原码一位乘的方法相似，特点如下：

当被乘数符号任意，乘数为正时：运算规则同原码乘，但加和移位的方法要按照补码运算的规则，此时乘积的符号会自然形成而无非单独进行异或运算。
当被乘数符号任意，乘数为负时：乘数为[y]_补，去掉符号位当成正数与被乘数进行运算，步骤同1。最后要加上[–x]_补，进行校正。
运算时可能会出现绝对值大于1的情况，但此时并不是溢出，所以采用双符号位的方式计算。

这里给出一道例题供参考：

注意，最后加上[–x]_补进行修正时，不需要再进行移位。

Booth算法

Booth算法，又称比较法。适用于符号任意的被乘数与乘数，具有普适性。由于比较法的补码乘法运算规则不受符号约束，因此控制线路比较简明，在计算机中普遍采用。

比较法的公式过于抽象，这里就不再赘述，不方便理解。其实本质上还是继续加上[–x]_补，然后右移一位的迭代过程。每次要不要加[–x]_补，由y_i+1和y_i决定。其运算规律如下表所示：

y_i y_i+1	y_i+1 - y_i	操作
0 0	0	右移一位
0 1	1	+[x]_补，右移一位
1 0	-1	+[–x]_补，右移一位
1 1	0	右移一位

记住，比较法的最后一步不移位。

与校正法相比，比较法的部分积仍然取双符号位。乘数因为符号位参与运算，所以多取一位。

给出例题参考如下：

乘法小结

介绍了原码乘法和补码乘法后，总结如下：

整数乘法与小数乘法完全相同，可用逗号代替小数点
原码乘符号位单独处理；补码乘符号位自然形成
原码乘去掉符号位运算，即为无符号数乘法
不同的乘法运算需有不同的硬件支持

除法运算

除法运算分为恢复除数法和不恢复除数法。恢复除数法即使用加法器不断的作负数补码的加法来试探减法，一旦结果小于0则恢复除数，右移一位继续。这种做法降低了计算的效率，所以我们这里只介绍不恢复余数法。两种除法均为原码运算，故符号位需要单独处理。

不恢复余数法的步骤可以概括如下，大抵和前面介绍的乘法原码计算步骤类似：

（注意，y*表示y的绝对值）

列出被除数（也即余数，比如0.1011）、商（当n=4的情况下，初始化为0.0000）
首先加上[-y*]_原，即被除数减去除数，判断是否溢出
如果余数的符号位为1，小于0：
- 上商0
- 商与余数均逻辑左移一位
- +[y*]_原，即加上除数
如果余数的符号位为0，大于0：
- 上商1
- 商与余数均逻辑左移一位
- +[-y*]_原，即继续减去除数
这个步骤重复上商n+1次，总共需要逻辑左移n次，用移位的次数判断除法是否结束
符号位最后单独进行异或运算

下面给出例题作为参考：

补码的除法运算这里略过不讲，期末大概不会考它。

快速进位链

我们已经在数学层面上学习了如何实现计算机的运算，接下来我们来讨论如何在硬件层面上设计计算机的运算系统，这里主要以ALU加法器为例。

其中，A和B是输入变量，可以通过设置k工作信号的值，来选择ALU的功能，最后把结果输出到F。ALU没有记忆，因此需要在A、B和F处连接寄存器储存变量的值。在ALU中，最核心的组成部分就是快速进位链，接下来我们来学习如何设计快速进位链。

并行加法器

并行加法器由若干个全加器构成：

其中A和B是输入，C是进位信号，S是当前位数运算的值。可以看到，当操作的位数变多时，每一级的运算结果都要依赖于上一级的进位信号才能输出正确的结果，导致大部分时间前端的全加器都在等待，这是不可接受的。我们的任务就是优化计算进位的速度，也就是设计快速进位链。

根据全加器的逻辑表达式，我们可以很简单的构造出进位信号C的逻辑表达式：

$C=d_i+t_iC_{i-1}$

其中 $t$ 和 $d$ 的含义图中均已给出。

根据C的表达式，我们就可以将逐级进位的结构转换为进位链的方式来实现快速进位。目前的进位链形式有串行和并行两种。

串行进位链

串行进位链就是指并行加法器中的进位信号通过串行传输，如图：

进位表达式可写为：

$\begin{array}{l} C_{0}=d_{0}+t_{0} C_{-1}=\overline{\overline{d_{0}} \cdot \overline{t_{0} C_{-1}}} \\ C_{1}=d_{1}+t_{1} C_{0} \\ C_{2}=d_{2}+t_{2} C_{1} \\ C_{3}=d_{3}+t_{3} C_{2} \end{array}$

即我们先通过与非门计算 $t_0$ 和 $C_{-1}$ ，再和低电平 $d_0$ 信号通过一次与非门就能得到 $C_0$ ，同理可求 $C_n$ ，设计出进位链。

让我们假设与非门的延迟是 $t_y$ ，那么n位全加器产生进位的全部时间就为 $2nt_y$ ，因为一个进位需要使用两个与非门。

并行进位链

并行进位链，又称先行进位或跳跃进位，是指并行加法器的进位信号理想情况下是同时产生的，但这么实现通常有困难。一般来说有两种实现方案：单重分组和双重分组。

我们之前得到了串行进位链的进位信号表达式，对该表达式进行变换，可以得到如下结果：

$\begin{array}{l} C_{0}=d_{0}+t_{0} C_{-1} \\ C_{1}=d_{1}+t_{1} C_{0}=d_{1}+t_{1} d_{0}+t_{1} t_{0} C_{-1} \\ C_{2}=d_{2}+t_{2} C_{1}=d_{2}+t_{2} d_{1}+t_{2} t_{1} d_{0}+t_{2} t_{1} t_{0} C_{-1} \\ C_{3}=d_{3}+t_{3} C_{2}=d_{3}+t_{3} d_{2}+t_{3} t_{2} d_{1}+t_{3} t_{2} t_{1} d_{0}+t_{3} t_{2} t_{1} t_{0} C_{-1} \end{array}$

仔细分析表达式，均为与操作和或操作，所以我们可以设计出如下电路图：

放心，这个图很复杂，看看就好，重点不在这里。

假设或非门的延迟时间为 $1.5t_y$ ，那么 $d_it_i$ 形成后，只需要 $2.5t_y$ 就可以产生全部的进位。

可以看到这个速度比串行进位链已经提升了很多，但是当位数比较大时（比如32位），这个电路的设计会肉眼可见的变得非常复杂。为了简化电路设计，我们给出了以下两种折中方案，也就是我们先前提到过的单重分组跳跃与双重分组跳跃。

单重分组跳跃进位链

我们将n位全加器分若干小组，小组中的进位同时产生，小组与小组之间采用串行进位。以n=16为例，我们将全加器分为四组，可以设计出如下的电路图：

此时完成一个小组的用时为 $2.5t_y$ ，那么经过 $4\times2.5t_y=10t_y$ 即可完成四组的进位信号生成，而如果采用串行进位链，则需要 $32t_y$ 。

双重分组跳跃进位链

双重分组即n位全加器分若干大组，大组中又包含若干小组。每个大组中小组的最高位进位同时产生。大组与大组之间采用串行进位。以n=32为例，我们把32分为两个16的大组，再把16按照单重跳跃的方式进行分组，绘图如下：

其中， $C_{15}$ 产生的进位信号作为串行进位输入到第一大组和第4小组中。此时特点可总结为：组内并行，组间串行。

本质上，双重分组跳跃链就是对单重分组跳跃链的一层抽象，我们还可以根据这种抽象思维设计出更多重的跳跃链。这就是A new level of abstraction。

大组进位分析

上述的双重分组跳跃链只是一个简图，我们还没有讨论大组之间的电路是怎么设计的。

我们从第8小组为例，分析它的表达式。

$C_{3}=d_{3}+t_{3} C_{2}=\underbrace{d_{3}+t_{3} d_{2}+t_{3} t_{2} d_{1}+t_{3} t_{2} t_{1} d_{0}}_{D_{8}}+\underbrace{t_{3} t_{2} t_{1} t_{0} C_{-1}}_{T_{8}}$

其中 $D_8$ 是第8小组的本地进位，和外来进位无关； $T_8$ 是第8小组的传送条件，与外来进位无关，只是负责传递外来进位。

同理我们有：

第7小组 $C_7=D_7+T_7+C_3$
第6小组 $C_{11}=D_6+T_6+C_7$
第5小组 $C_{15}=D_5+T_5+C_{11}$

依次代入展开可以得到如下表达式：

$\begin{array}{l} C_{3}=D_{8}+T_{8} C_{-1} \\ C_{7}=D_{7}+T_{7} C_{3}=D_{7}+T_{7} D_{8}+T_{7} T_{8} C_{-1} \\ C_{11}=D_{6}+T_{6} C_{7}=D_{6}+T_{6} D_{7}+T_{6} T_{7} D_{8}+T_{6} T_{7} T_{8} C_{-1} \\ C_{15}=D_{5}+T_{5} C_{11}=D_{5}+T_{5} D_{6}+T_{5} T_{6} D_{7}+T_{5} T_{6} T_{7} D_{8}+T_{5} T_{6} T_{7} T_{8} C_{-1} \end{array}$

这又化成了只有与门和或门的形式，参照单重分组跳跃的方式，我们可以设计出大组间的跳跃电路：

小组进位分析

讨论完双重进位链中的大组，我们再来研究小组间的电路该如何设计。

小组间的电路其实就是一个单重进位链，但是我们需要它提供 $D$ 和 $T$ 给大组的跳跃链，所以我们还是给出了小组间的电路设计图，以第8小组为例，它只产生低3位的进位和本小组的D8、T8：

是否觉得很眼熟呢？我放出了原来的单重跳跃进位链作为对比

此时，我们就可以分析当n=16时的双重分组跳跃进位链的用时了，绘图如下：

当 $d_it_i$ 和 $C_{-1}$ 形成后：

经过 $2.5t_{y}$ ，产生 $C_2、C_1、C_0、D_5\sim D_8、T_5\sim T_8$
经过 $5t_{y}$ ，产生 $C_{15}、C_{11}、C_7、C_3$
经过 $7.5t_{y}$ ，产生 $C_{14}\sim C_{12}、C_{10}\sim C_8、C_6\sim C_4$

而如果使用串行进位链，则需要 $32t_y$

如果使用单重分组跳跃进位链，则需要 $10t_y$ 。

当n=32时，绘图如下：

当 $d_it_i$ 和 $C_{-1}$ 形成后：

经过 $2.5t_{y}$ ，产生 $C_2、C_1、C_0、D_1\sim D_8、T_1\sim T_8$
经过 $5t_{y}$ ，产生 $C_{15}、C_{11}、C_7、C_3$
经过 $7.5t_{y}$ ，产生 $C_{18}\sim C_{16}、C_{14}\sim C_{12}、C_{10}\sim C_8、C_6\sim C_4$

$C_{31}、C_{27}、C_{23}、C_{19}$
经过 $10t_y$ ，产生 $C_{30}\sim C_{28}、C_{26}\sim C_{24}、C_{22}\sim C_{20}$