BUAA Software CO｜计算机组成原理概要1

01 绪论

冯诺依曼架构

计算机应由运算器、控制器、存储器、输入设备和输出设备五个基本部件组成。
各基本部件的功能
- 存储器不仅能存放数据，而且也能存放指令，形式上两者没有区别，但计算机应能区分数据还是指令。
- 控制器应能自动取出指令来执行。
- 运算器应能进行加/减/乘/除四种基本算术运算，并且也能进行一些逻辑运算和附加运算。
- 操作人员可以通过输入设备、输出设备和主机进行通信。
内部以二进制表示指令和数据。每条指令由操作码和地址码两部分组成。操作码指出操作类型，地址码指出操作数的地址。由一串指令组成程序。
采用“存储程序”工作方式：任何要计算机完成的工作都要先被编写成程序，然后将程序和原始数据送入主存并启动执行。一旦程序被启动，计算机应能在不需操作人员干预下，自动完成逐条取出指令和执行指令的任务。

程序编译与加载

截屏2022-12-26 23.33.32

两类指令集

截屏2022-12-26 23.38.37

截屏2022-12-26 23.38.46

计算机层级结构

截屏2022-12-26 23.40.47

ISA 是软件和硬件的界面（Interface，接口），也是计算机组成（organization）的抽象 / 接口，或者说一种计算机组成是某种 ISA 的实现。

应用程序二进制接口（Application Binary Interface，ABI）是运行在特定 ISA 及特定操作系统之上的应用程序中所遵循的一种机器级目标代码层接口，它描述了应用程序和操作系统之间、应用程序和所调用的库之间、不同组成部分（如过程或函数）之间在较低层次上的机器级代码接口。

ABI 接口规约的内容主要包括

过程间的调用规定

系统调用规定

目标文件的二进制格式

函数库使用规定

寄存器使用规定

程序的虚拟地址空间划分等

并行和并发

并发：逻辑上的并行，物理上的交替执行（使系统同时处理多个任务）
并行：物理上的并行（真正使系统运行更快）

指令级并行：流水线技术

超标量并行：多条流水线并行执行；动态多发射，一个时钟内发射多条指令，一个周期内可执行一条以上的指令

02 数制与运算

进制的转换

十进制转二进制：整数部分除以 2 所得余数逆序，小数部分乘 2 所得整数正序
二进制转十进制：整数部分从个位向高位乘以权重$1,2,4,8,\dots$；小数部分从十分位向低位乘以权重$\frac{1}{2},\frac{1}{4},\frac{1}{8},\dots$
二进制转十六进制：四位一组，整数部分高位补 0，小数部分低位补 0

定点数的编码

编码方式	正数	负数
原码	符号位为 0	符号位为 1
反码	符号位为 0	对应正数按位取反
补码	符号位为 0	对应正数按位取反 + 1
移码	带偏移量的编码	带偏移量的编码

补码运算规则

$\begin{split} [X+Y]_{补}=[X]_{补}+[Y]_{补}\\ [X-Y]_{补}=[X]_{补}+[-Y]_{补} \end{split}$

若符号位产生进位，则将进位舍弃

浮点数的编码：IEEE 754

截屏2022-12-27 11.35.56

数符 S：0 表示正数，1 表示负数
阶码 E：用移码表示，是非负整数，对于单精度浮点数偏移 +127，对于双精度浮点数偏移 +1023
尾数 M：必须规格化为小数点左侧一定为 1，且这个 1 作为隐含位被省略。例如，单精度浮点数的尾数实际为 24 位

大小端存储

地址总是从小到大排放的。访问一个数，或者说数的地址，总是低地址的那头。因此大小端指的是谁放在低位的问题。

大端方式：数的高位所在的地址是数的地址
小端方式：数的低位所在的地址是数的地址

截屏2022-12-27 12.09.41

布尔代数与门电路

1. 异或与同或

$\begin{split} A\oplus B&=A\overline{B}+\overline{A}B\\ A\odot B&=\overline{A}\ \overline{B}+AB\\ A\oplus B&=\overline{A\odot B} \end{split}$

2. 逻辑门电路的表示

截屏2022-12-27 12.26.53

3. 逻辑代数基本公理

交换律
$\begin{split} A + B&=B+A\\ AB&=BA \end{split}$
结合律
$\begin{split} (A+B)+C&=A+(B+C)\\ (AB)C&=A(BC)\\ \end{split}$
分配律
$\begin{split} A(B+C)&=AB+AC\\ A+BC&=(A+B)(A+C) \end{split}$
0 - 1律
$\begin{split} A+0=A,\ A\cdot1=A\\ A+1=1,\ A\cdot 0 = 0 \end{split}$
互补律
$\begin{split} A+\overline{A}=1\\ A\overline{A}=0 \end{split}$

4. 逻辑代数基本定理

重叠律
$\begin{split} A+A=A \\A\cdot A=A \end{split}$
还原律
$\overline{\overline{A}}=A$
反演律
$\begin{split} \overline{A+B}&=\overline{A}\cdot \overline{B}\\ \overline{A\cdot B}&=\overline{A} +\overline{B} \end{split}$
吸收律 1
$\begin{split} A+A\cdot B&=A\\ A\cdot(A+B)&=A \end{split}$
吸收律 2
$A+\overline{A}B=A +B$
包含律
$\begin{split} A\cdot B+\overline{A}\cdot C+B\cdot C&=A\cdot B+\overline{A}\cdot C\\ (A+B)\cdot(\overline{A}+C)\cdot(B+C)&=(A+B)\cdot(\overline{A}+C)\\ A\cdot B+\overline{A}\cdot C + BCDEF\cdots&=A\cdot B+\overline{A}\cdot C \end{split}$

5. 逻辑代数的规则

代入定理
反演定理

$\begin{split}&将原函数F中的全部\cdot换成+，+换成\cdot，0\ 换成\ 1，1\ 换成\ 0，原变量换成反变量，\\&反变量换成原变量，得到的就是F的反函数\overline{F}(取反只取单个变量上的非号)\end{split}$
对偶定理

$\begin{split}&将原函数F中的全部\cdot换成+，+换成\cdot，0\ 换成\ 1，1\ 换成\ 0，就得到原函数F的\\&对偶式F’(F^*).\ 若F=G，则F’=G’\end{split}$

6. 最小项与最大项

最小项
- $n$ 个变量有 $2^n$ 个最小项
- 按照变量顺序将最小项中原变量用 $1$ 表示、反变量用 $0$ 表示，得到的二进制数对应的十进制数即为该最小项的编号 $i$
- 性质
  - 对于任意最小项，只有一组变量取值使之为 1
  - 全体最小项之和为 1
  - 任意两个最小项乘积为 0
  - 除了一个变量互为反变量外，其余变量都相同的两个最小项称相邻最小项。具有相邻性的最小项之和可以合并为一个乘积项，如$\overline{A}\ \overline{B}\ \overline{C}+\overline{A}\ \overline{B}\ C=\overline{A}\ \overline{B}$
- 最小项推导法：使输出为 1 的输入组合写成乘积项的形式，其中取值为 1 的输入用原变量表示，取值为 0 的输入用反变量表示，然后把这些乘积项加起来
最大项
- $n$ 个变量有 $2^n$ 个最大项
- 按照变量顺序将最小项中原变量用 $0$ 表示、反变量用 $1$ 表示，得到的二进制数对应的十进制数即为该最小项的编号 $i$ 。规律：$m_i=\overline{M_i}$
- 性质
  - 对于任意最大项，只有一组变量取值使之为 0
  - 全体最大项之积为 0
  - 任意两个最大项之和为 1
  - 具有相邻性的最大项之积可以合并为一个和项，例如$(\overline{A}+B+\overline{C})(A+B+\overline{C})=B+\overline{C}$
- 最大项推导法：把使输出为 0 的输入组合写成和项的形式，其中取值为 0 的输入用原变量表示，取值为 1 的输入用反变量表示，然后把这些和项乘起来

补充：BCD 码

将十进制数的数码转变为四位二进制数，即为 BCD 编码。常见的有 8421BCD、2421BCD、5211BCD 和余 3 BCD 等。其中数字代表对应二进制位的权重。

余 3 BCD：将 8421BCD 加上 3 即得余 3 BCD

03 数字逻辑

概述

数字电路分为组合逻辑和时序逻辑
组合逻辑电路
- 将逻辑门以一定的方式组合在一起，使其具有一定逻辑功能的数字电路。**
- 组合逻辑电路是一种无记忆电路——任一时刻的输出信号仅取决于该时刻的输入信号，而与信号作用前电路原来所处的状态无关。
- 特点
  - 由逻辑门电路组成
  - 没有反馈电路和储存电路
  - 某时刻输出仅由该时刻输入决定（速度快）
时序逻辑电路
- 时序逻辑电路由组合逻辑电路和存储电路构成，具有记忆功能。
- 某一时刻的输出由该时刻的输入和电路当前状态有关。
- 触发器（Flip-Flop，FF）是构成记忆功能部件的基本单元。触发器有两个互非的输出 $Q$ 和 $\overline{Q}$，其中 $Q$ 称为状态变量。在外加信号的触发下，触发器可由原态 $Q^n$ 变为次态 $Q^{n+1}$。

组合逻辑

1. 加法运算电路

半加器：对两个 1 位二进制数求和，并向高位进位，不考虑来自低位的进位

$\begin{split} C_O&=A\cdot B\\ S_0=\overline{A}B&+A\overline{B}=A\oplus B \end{split}$
全加器：对两个 1 位二进制数求和，并向高位进位，考虑来自低位的进位

$\begin{split} S_0=A&\oplus B\oplus C_I\\ C_O =AB&+C_I(A\oplus B) \end{split}$
多位加法器通过并行进位（先行进位）减少延时，但实现相对复杂。
溢出问题
溢出的可能情形
- 符号位相同的两数相加，所得结果符号位发生变化，则溢出
- 符号位相异的两数相减，所得结果符号位与减数相同，则溢出
有符号数运算时，出现溢出表示结果是错误的。

采用双符号位判断溢出
- 00 表示正，11 表示负
- 运算结果出现 01 为正溢
- 运算结果出现 10 为负溢

2. 数值比较器

一位比较器

$\begin{split} F_{A>B}=A&\overline{B}=A\overline{AB}\\ F_{A=B}=AB+\overline{AB}&=\overline{A\overline{AB}+B\overline{AB}}\\ F_{A<B}=\overline{A}&B=B\overline{AB} \end{split}$
多位比较器（4 位比较器，7485 芯片）

比较规则：规则：从高位开始比较，高位不等时，数值的大小由高位决定；若高位相等，则再比较低位，数值的大小由低位比较结果决定。
数位拓展：将低位芯片的输出作为高位芯片在高位各位全相等时的输入，并原样输出。

3. ALU

具备加法、减法、与、或运算的一位 ALU

根据 $[X-Y]_{补}=[X]_{补}+[Y]_{补}=[X]+[Y]_{反}+1$，对于减法，只需要将第二个操作数取反，并将低位进位置一即可。对第二个操作数是否取反的二选一多选器，设 Binvert 信号取 0 时保持原数，取 1 取反；另设低位进位为 CarryIn。则对于加法，Binvert = 0，CarryIn = 0；对于减法，Binvert = 1，CarryIn = 1。故可以连到一根线上，设该信号为 Bnegate。
$n$ 位带标志的 ALU
- 溢出标志
  ${\rm OF}={\rm Cin}_{n-1}\oplus {\rm Cout}_{n-1}$
- 符号标志
  ${\rm SF}={\rm F}_{n-1}$
- 零标志
  ${\rm ZF} = 1\Leftrightarrow {\rm F }=0$
- 进位 / 借位标志
  ${\rm CF}={\rm Cin}_0 \ \oplus\ {\rm Cout}_{n-1}$
条件标志（Flag）在运算电路中产生，被记录到专门的程序 / 状态字寄存器或标志寄存器中。

4. 编码器

$2^n$ 线 - $n$ 线编码器：用 $n$ 位二进制代码对 $2^n$ 个信号进行编码。任意一个时刻只能对其中一个信号编码，其余信号为无效电平，否则输出会混乱

8 线 - 3 线编码器（输入高电平有效）：

$\begin{split} A=Y_1+Y_3+Y_5+Y_7=\overline{\overline{Y_1}\cdot\overline{Y_3}\cdot \overline{Y_5}\cdot \overline{Y_7}}\\ B=Y_2+Y_3+Y_6+Y_7=\overline{\overline{Y_2}\cdot\overline{Y_3}\cdot \overline{Y_6}\cdot \overline{Y_7}}\\ C=Y_4+Y_5+Y_6+Y_7=\overline{\overline{Y_4}\cdot\overline{Y_5}\cdot \overline{Y_6}\cdot \overline{Y_7}} \end{split}$
优先编码器：允许多个输入，仅对优先级最高的信号编码输出
- 74LS148：8 线 - 3 线优先编码器，输入低电平有效，反码输出
- 74LS147：10线 - 4 线优先编码器，输入低电平有效，反码输出

5. 译码器

二进制译码器（变量译码器）

74LS138：3 线 - 8 线译码器
- 输入高电平有效
- 输出低电平有效
- 有三个使能控制 $S_1,\ S_2,\ S_3$ ，只有当它们分别为 1，0，0 时译码器才能正常工作
BCD 译码器
显示译码器
- 使用共阴极 LED 数码管：译码器输出高电平有效
- 使用共阳极 LED 数码管：译码器输出低电平有效

6. 多路选择器

8 选 1 多路选择器

$D_7\sim D_0$ 为数据输入端，$A_2A_1A_0$ 为选择控制端，使能信号 ${\rm EN}$ 低电平有效

截屏2022-12-27 18.19.49

$\begin{split} Y=\ &\overline{A_2}\ \overline{A_1}\ \overline{A_0}D_0+\overline{A_2}\ \overline{A_1}A_0D_1+\overline{A_2}A_1\overline{A_0}D_2+\overline{A_2}A_1A_0D_3\\ &+A_2\overline{A_1}\ \overline{A_0}D_4+A_2\overline{A_1}A_0D_5+A_2A_1\overline{A_0}D_6+A_2A_1A_0D_7\\ =\ &D_0m_0+D_1m_1+D_2m_2+D_3m_3\\ &+D_4m_4+D_5m_5+D_6m_6+D_7m_7 \end{split}$

利用多选器实现逻辑函数：将逻辑函数化为由最小项组成的与或式，若有项 $m_i$ 则将 $D_i$ 接高电平；反之低电平。

竞争冒险现象

相关概念
- 竞争：在组合逻辑电路中，某个输入变量通过两条或两条以上的途径传到输出端，由于每条途径延迟时间不同，到达输出门的时间就有先有后，这种（两个或多个信号不同步）现象称为竞争。
- 冒险：门电路因输入端的竞争而导致输出端产生不正常的尖峰干扰冒充信号（毛刺）的现象，成为冒险。
- 竞争冒险的原因：门电路的延时。
解决方案
- 修改设计逻辑：消除互补变量 / 增加冗余项
- 引入采样脉冲
- 输出端并联电容

时序逻辑

1. RS 锁存器

基本 RS 锁存器
- 特性方程 $Q^{n+1}=S_D+\overline{R_D}\cdot Q^n$
- 约束条件 $S_D\cdot R_D = 0\ (\overline{S_D}\ 和\ \overline{R_D}\ 不能同时为\ 0)$
钟控 RS 锁存器
- 有时钟控制端的锁存器称为钟控锁存器，只有当时钟信号为高电位或低电位时，锁存器的状态才会随输入变化。钟控锁存器是电位触发方式的锁存器。
- 钟控锁存器在时钟控制下同步工作，又称同步锁存器。
- 特性方程 $Q^{n+1}=S+\overline{R}\cdot Q^n({\rm CP}\ 为\ 0\ 时处于保持状态)$
- 约束条件 $S\cdot R=0$

2. 钟控 D 锁存器

截屏2022-12-27 20.41.21

特性方程 $Q^{n+1}=D({\rm CP}\ 为\ 0\ 时处于保持状态)$

3. D 触发器

触发器的状态变化只发生在时钟信号的有效沿（上升沿或下降沿）。

基本的 D 触发器
- CP = 0 时，L1 通 L2 断，Q1 为 D 的值，Q2 的值保持不变
- CP 上升沿，Q1 的值赋给 Q2，这是触发时刻
- CP = 1 时，L1 断 L2 通，Q1 不变则 Q2 继续保持
加入使能信号 EN
- EN = 1 时触发器正常工作
- EN = 0 时触发器状态保持
- 一般不在时钟信号上设置逻辑，否则可能因为延迟导致时序错误
复位功能
- RESET 为低电平（有效）时，触发器复位（Q = 0）；为高电平（无效）时，正常工作
- 复位方式
  - 同步复位：复位信号和时钟有效沿同时到来才能复位
  - 异步复位：只要有复位信号就可以复位

4. JK 触发器

JK 触发器将 R = 1，S = 1 的无效状态变成了翻转功能。
特性方程 $Q^{n+1}=J\overline{Q^n}+\overline{K}Q^n$

5. 有限状态机（FSM）

Moore 型：输入仅改变状态，输出仅与当前状态有关。
Mealy 型：输出与状态和输入都有关。

6. 计数器

分类
- 按时钟连接方式：同步计数器和异步计数器
- 按计数方式：二进制计数器、十进制计数器、M 进制计数器
- 按状态变化方式：加法计数器、减法计数器、加 / 减法计数器
计数器特性分析

计数器 —— 若干触发器通过若干状态构成一个计数循环

同步 —— 所有触发器的时钟端连在一起

M 进制 —— 计数循环的状态个数为 M（模 M 计数器）

加 / 减法 —— 计数状态按递增 / 减方向变化

自启动性 —— 不存在由计数循环以外的状态构成的死循环，在无效状态也能回到计数循环中来
二进制加法计数器特点
- 触发器的模值是 $2^n$。
- 二进制计数器没有非编码状态，因此不存在不能自启动的问题。
- 不同的触发器的周期分别是计数脉冲 CP 的 2 倍、4 倍、8倍、16倍、… ，则相当于对 CP 波形进行了 2 分频、4 分频、8 分频、16 分频、… ，因此二进制计数器也成为分频器。
集成计数器与改变模值

设一个计数器的模值为 $M$，则两片级联后模值变为 $M^2$
- 反馈复位法：通过级联使模值充分够，当计数到指定模值后强行复位。
  用两片 74LS161 实现 M = 60 的加法计数器
  - 反馈复位条件 $(60)_{10}=(111100)_2$
  - 反馈复位逻辑 $\overline{R_D}=\overline{Q_5Q_4Q_3Q_2}$
- 预置法
  (1) 输出 C 预置法：产生进位（数到头）后将计数器预置到某一中间值。
  
  用一片 74LS161 实现 M = 10 的加法计数器
  - 预置数据 $(16-10)_{10}=(6)_10=(0110)_2=D_3D_2D_1D_0$（从 6 开始数）
  (2) 输出 Q 预置法：到达指定模值后将计数器预置到 0。
  
  用一片 74LS161 实现 M = 10 的加法计数器
  - 预置条件 $(10-1)_{10}=(9)_{10}=(1001)_2$
  - 预置逻辑 $\overline{LD}=\overline{Q_3Q_0}$
  注意预置 Q 与反馈复位的区别：前者通过预置复位到 0，预置本身需要花费一个时钟（因为要等下一个有效沿到来），因此预置的条件是模值 M - 1；而后者通过 Reset 方式直接强行复位到 0。

04 MIPS 汇编

MIPS 寻址方式

立即寻址：操作数直接在指令中给出，如addi $s1, $s2, 100
寄存器直接寻址：访问寄存器中的操作数，如add $t1, $t2, $t3
寄存器间接寻址：访问寄存器中的地址，进而访问位于该地址的操作数，如lw $t0, 0($t1)
基址寻址：访问寄存器中的基址，进而访问位于“基址 + 偏移量”处的操作数，如lw $t0, 100($t1)
变址寻址：寄存器中存有偏移量，通过数组名（形式地址）+ 偏移量的方式访问操作数，如lb $t1, arr($t0)
相对寻址：基址寻址的特例，基址存在于程序计数器 PC 中，如beq $t1, $t2, 100

MIPS 寄存器结构

组成
- 32 位（4G）虚拟地址空间
- 32 个 32 位通用寄存器（GPRs）
- 32 个 32 位浮点数寄存器（FPRs）
- 乘除寄存器 HI LO
- 程序计数器 PC

名称	编号	功能
zero	0	恒为常数 0
at	1	为汇编程序保留
v0 ~ v1	2 ~ 3	过程调用返回值
a0 ~ a3	4 ~7	过程调用参数
t0 ~ t7	8 ~ 15	临时变量
s0 ~ s7	16 ~ 23	保存
t8 ~ t9	24 ~ 25	其他临时变量
k0 ~ k1	26 ~ 27	为 OS 保留
gp	28	全局指针
sp	29	栈指针
fp	30	帧指针
ra	31	过程调用返回地址

MIPS 指令格式

R-Type（Register）：两个寄存器操作数计算，结果送给第三个寄存器（寄存器相关的指令）

I-Type（Immediate）：含有带符号 16 位立即数操作的指令

J-Type（Jump）：跳转指令，包含 26 位跳转地址

1. R 指令

6 位操作码 Op：全 0

3 × 5 位寄存器编号：分别代表 Rs、Rt、Rd

5 位偏移量：仅用于移位运算

6 位 Func 字段：表示具体运算类型

三个操作数全为寄存器 add rd, rs, rt # rd <- (rs + rt)
1
add $t0, $s1, $s2 # 000000 10001 10010 01000 00000 100000

移位运算 sll rd, rt, sa # rd <- (rt << sa)

1	sll $8, $9, 10 # 000000 00000 01001 01000 01010 000000

寄存器无条件跳转

jr rs # PC <- rs

1	jr $8 # 000000 01000 00000 00000 00000 001000

jalr rd, rs # rd <- return_addr; PC <- rs

1	jalr $8, $9 # 000000 01001 00000 01000 00000 001001

2. I 指令

6 位操作码 Op：表示对应的算数 / 逻辑运算或存取操作

2 × 5 位寄存器编号：分别表示 Rs 和 Rt

16 位带符号立即数

带立即数的算数 / 逻辑运算addi rt, rs, imm # rt <- (rs + imme)
1
addi $8, $9, 10 # 001000 01000 01001 0000000000001010
存取指令ld rt, offset(rs) # rt <- Mem[rs + offset]
1
ld $8, 4($9) # 110111 01001 01000 0000000000000100
条件跳转指令beq rs, rt, offset # if (rs == rt) then PC <- PC + offset
1
beq $8, $9, -4 # 000100 01000 01001 1111111111111100

3. J 指令

6 位操作码 Op：表示对应的跳转类型

26 位地址：跳转的地址（标签）

```assembly
j target # PC <- (PC_4_Highest_Bits || instr_index || 00)

1
2
3


- ```assembly
  jal target # ra <- (PC + 8); PC <- (PC_4_Highest_Bits || instr_index || 00)

跳转指令的范围问题
- j指令：跳转时 26 位地址低位补两个 0，高 4 位接上 PC + 4 的高四位，可以跳转 $2^{28}$ 个地址单元，即 256 MB。
- jr指令：属于 R 指令，地址为寄存器中的 32 位数，可以跳转全部的 $2^{32}$ 个地址单元，即 4GB。
- beq指令：属于 I 指令，将 16 位立即数低位补两个 0，符号扩展成 32 位后加上 PC + 4，可以跳转 $2^{18}$ 个地址单元，即 256 KB。

补充：伪指令

# li $t0, 0x12345678
lui $1, 0x1234 # $1 <- 0x12340000(装载到高16位)
ori $t0, $1, 0x5678

# move $t1, $t2
add $t1, $t2, $zero

# la $t1, label
addi $t1, $zero, 0x??? # 编译时刻确定的地址

系统调用`syscall`

服务类型	服务号 `v0`	参数	返回值
打印整数	1	a0 为要打印的整数
打印单精度浮点数	2	f12 为要打印的浮点数
打印双精度浮点数	3	f12 为要打印的浮点数
打印字符串	4	a0 为字符串的地址
读取整数	5		v0 存放读到的整数
读取单精度浮点数	6		f0 存放读到的浮点数
读取双精度浮点数	7		f0 存放读到的浮点数
读取字符串	8	a0 为字符串的起始地址，a1 为最多可以读取的字符个数
分配堆空间	9	a0 为空间的字节数	v0 存放分配到的空间的首地址
终止程序	10
打印字符	11	a0 为要打印的字符
读取字符	12		v0 存放读到的字符