考研冲刺前的总结 —— 计算机组成原理

无符号数与有符号数#

无符号数指的是机器数中不表示负数，即表示非负数（包括 0）。 所有位都用于表示数值，不需要单独的符号位。

例如，8 位无符号数可以表示的范围为 $0$ 到 $255$，即 $00000000_2$ 到 $11111111_2$。

而有符号数的第一位一定是符号位，0 表示正数，1 表示负数。需要注意的是，原码、反码、补码都是基于 有符号数 去讨论的，所以即便原码看着和无符号数很像，但是其本质是不一样的。

原码#

原码的第一位是符号位，0 表示正数，1 表示负数，后续的位数表示数值的绝对值。

例如对于 15 和 -15，其 8 位原码分别为 $00001111_2$ 和 $10001111_2$。

对于 8 位原码，其表示范围为 $[-127,127]$；负数和正数的最大编码分别为 $11111111_2$ 和 $01111111_2$。

从而产生了一个问题，即 0 的表示是不唯一的，即 $00000000_2$ 和 $10000000_2$ 都表示 0。

原码很直观，但是这里先不讲为什么原码的计算很不方便。

由于原码的计算很不方便，所以很少在计算机中使用。

反码#

反码的第一位是符号位，0 表示正数，1 表示负数，后续的位数是数值的绝对值的反码。

这里先不讨论反码的来源，先说反码的计算方法。

对于正数，其反码和原码相同，因为正数的反码就是其本身。

对于负数，其反码是原码除了符号位的每一位取反，即 0 变 1，1 变 0。

例如对于 15 和 -15，其 8 位反码分别为 $00001111_2$ 和 $11110000_2$。

对于 8 位反码，其表示范围为 $[-127,127]$；负数和正数的最大编码分别为 $11111111_2$ 和 $01111111_2$。

从而也有一个问题，即 0 的表示是不唯一的，即 $00000000_2$ 和 $11111111_2$ 都表示 0。

反码在现代整数编码中已经少用，主要作为补码的过渡概念。

半加器（Half Adder）#

半加器只负责计算本位两个一位二进制数的加法，不考虑来自低位的进位。

输入：被加数 $A$、加数 $B$。

输出：本位和 $S$，向高位的进位 $C$。

逻辑表达式：

示例：计算 $1+1$ 时，$S=1\oplus1=0$，$C=1\land1=1$， 合起来输出二进制 $10_2$。

半加器无法接收低位产生的进位输入，因此不能直接用于多位数的进位加法。

全加器（Full Adder）#

全加器在半加器的基础上，增加了接收低位进位的功能。

输入：被加数 $A$、加数 $B$，来自低位的进位 $C_{\mathrm{in}}$。

输出：本位和 $S$，向高位的进位 $C_{\mathrm{out}}$。

逻辑表达式：

示例：计算 $1+1+1$（包含低位进位 $1$）时，$S=1$， $C_{\mathrm{out}}=1$，合起来输出二进制 $11_2$。

并行加法器（Parallel Adder）#

为了实现多位二进制数的快速相加，通常将多个全加器组合起来使用：

串行进位加法器将多个全加器首尾相连，进位从低位向高位逐级传递，延迟较高。

超前进位加法器通过进位生成和传递的布尔逻辑提前计算各位进位， 不必等待低位逐级传递，延迟较低。实际工程中常以 4 位加法器作为基本模块， 再通过进位链级联。

算术逻辑单元（ALU）#

ALU 是组合逻辑电路，没有记忆功能。输入是操作数 $A$、$B$ 和功能选择信号，输出是运算结果 $F$ 以及若干标志位。

核心是一个加法器，再加移位电路、逻辑运算电路（与、或、异或、非）和一个多路选择器，由操作码决定最终输出哪一路。

ALU 的位数一般就是机器字长，因为 ALU 要能一次处理一个字。

需要注意，ALU 只负责算，不负责存。结果要打入寄存器（累加器、通用寄存器或标志寄存器）才算完成一次运算，这也是数据通路里“组合逻辑 + 寄存器”的基本套路。

加法器是 ALU 的子集，ALU 在加法器外面套了一层功能选择，所以支持减法、逻辑运算、比较（做减法看标志位）。

补码的好处在这里体现得很明显：减法直接用加法器加补数实现，ALU 不需要单独的减法电路，只需要把 $B$ 取反再把最低位进位设为 1。

在这里讲加法器，是因为可以理解补码的来源。

暂时不考虑溢出的情况，仅考虑下面的情况。

对于 8 位无符号数，$13$ 和 $12$ 的二进制表示分别为 $00001101_2$ 和 $00001100_2$，相加可得 $00011001_2$，即 $25$。

对于 8 位无符号数，$13-12$ 可写为 $00001101_2-00001100_2=00000001_2$，结果为 $1$。

对于 8 位原码，$13+12$ 的编码为 $00001101_2+00001100_2=00011001_2$，结果为 $25$。

对于 8 位原码，$13-12$ 的编码为 $00001101_2-00001100_2=00000001_2$，结果为 $1$。

这看起来对人类而言很直观，但是对于计算机来说，相减如何实现？

如果直接按原码的“绝对值相减、再确定符号”规则实现， 需要比较绝对值并单独处理符号；如果为无符号减法设计专用路径， 还要处理借位。

这些额外逻辑会增加硬件复杂度，因此通常复用加法器和补码来实现减法。

硬件资源是稀缺的，所以需要一种更简单的方法来实现减法。

对模 $n$ 的无符号数 $x$，其补数定义为 $(-x)\bmod n=(n-x)\bmod n$。

对于 8 位无符号数，模为 $2^8=256$。 因此，$12$ 的补数为 $256-12=244$，对应的位串为 $11110100_2$。

考虑硬件实现，计算 $13-12$ 等同于计算 $13+(256-12)=13+244=257$。在 8 位寄存器中，最高进位被舍弃， 结果为 $257\bmod256=1$。

在固定 $n$ 位二进制、模为 $2^n$ 的情况下，补数可以通过对 $x$ 的每一位取反再加 $1$ 得到。

所以可以得出下面的结论：

计算机的寄存器位数是固定的。对于 8 位无符号寄存器，其模为 $2^8=256$。

固定宽度运算只保留低 8 位，结果等价于按模 $256$ 截取；是否发生“溢出”要看数值解释： 无符号数看进位标志 CF，补码有符号数看溢出标志 OF。

在模 256 的系统中，减去一个数相当于加上这个数的补数。

例如：

那么对于有符号数呢？

考虑原码 $13-12$：其位串为 $00001101_2-00001100_2$。如果采用与无符号数补数求法类似的思路，能否得到正确结果？

补码#

补码的第一位是符号位，0 表示非负数，1 表示负数。对于非负数，其补码和原码相同。 对于负数，其补码是原码除符号位外的每一位取反再加 $1$。

对于 8 位补码，其表示范围为 $[-128,127]$，即从 $10000000_2$ 到 $01111111_2$；没有正 $128$，且只有一个 $0$。

例如，$-12$ 的原码为 $10001100_2$，其补码为 $11110100_2$。

在 8 位补码中，$13-12$ 等同于 $13+[-12]_{\text{补}}$，即 $00001101_2+11110100_2=00000001_2$；最高进位因位数限制被舍弃。

对于补码，可以把第一位（符号位）理解为负位权。 对 8 位补码，$-12$ 的位串可展开为 $-2^7+2^6+2^5+2^4+2^2=-12$。

移码#

对 $n$ 位整数，常规定义的移码（偏置码）偏置为 $2^{n-1}$， 编码值为真值加该偏置。

对于 $-128$，其补码为 $10000000_2$，其 8 位移码为 $00000000_2$。

对于 $0$，其补码为 $00000000_2$，其 8 位移码为 $10000000_2$。

对采用 $n$ 位补码、真值范围为 $[-2^{n-1},2^{n-1}-1]$ 的编码， 移码的位串等价于将补码的符号位取反。

移码在计算机中主要用于表示浮点数的阶码。IEEE 754 单精度的偏置为 $127$， 双精度的偏置为 $1023$。

四种编码的对照#

设字长为 $n$ 位，把前面几种编码放在一起看：

从表中可以看出，补码比原码、反码多表示一个负数，这就是 0 唯一带来的好处。

移码的编码值随真值单调递增，所以比较浮点数阶码大小时可以直接按无符号数比较，这也是阶码用移码的原因。

原码和反码的对称性在计算时要多写判断逻辑，补码则把符号位也当成数的一部分参与运算，硬件最省事。

C 语言整数类型及转换#

C 语言整数类型的精确位宽由实现和 ABI 决定。但考研用的是 long 为 32 位。

以 CHAR_BIT=8、ILP32 环境举例：

• char：1 字节，通常为 8 位；
• short：2 字节，16 位；
• int：4 字节，32 位；
• long：4 字节，32 位；
• long long：8 字节，64 位。

在 LP64 等其他 ABI 中，long 可能是 8 字节；C 标准只规定各类型的最小范围。

对于整数类型和转换，需要注意：

转换到无符号目标类型时，结果按目标类型的模保留低位； 转换到有符号目标类型且值无法表示时，结果由实现定义，不能一概而论为截断。

在常见二补码实现中，如果是短转长，整型提升或转换通常会进行扩展：无符号数高位补 $0$， 有符号数按符号位扩展；具体结果仍以目标类型和实现规则为准。

1
unsigned short a = 65530;
2
int b = a;

分析可知，对于无符号数 $a$，其 16 位十六进制表示为 FFFAH。 整型提升时零扩展为 32 位 0000FFFAH，再解释为 int，结果为 $65530$。

1
short a = -1;
2
unsigned int b = a;

分析可知，对于 16 位有符号数 $a$，其位串为 FFFFH。 整型提升先符号扩展为 32 位 FFFFFFFFH，再转换为 unsigned int， 结果为 $2^{32}-1$。

移位运算#

移位运算分为逻辑移位和算术移位。

逻辑移位是直接将二进制位向左或向右移动，移动后空位补 0。

算术右移时，高位补入原符号位；算术左移时，低位始终补 $0$。

例如，对于 8 位补码 10101010，逻辑左移一位和算术左移一位均为 01010100；逻辑右移一位为 01010101，算术右移一位为 11010101。

由于二进制的表达，移位运算天然地和乘除法有关系。

在不发生溢出的前提下，算术左移通常相当于乘以 $2$； 对非负数，算术右移相当于整除 $2$，对负数则通常向负无穷取整。

例如，8 位补码 11001010 的真值为 $-54$。 算术左移一位得到 10010100，真值为 $-108$； 算术右移一位得到 11100101，真值为 $-27$。

需要注意的是，左移时若有效位被丢弃或符号位发生改变，可能发生溢出。 例如，8 位补码 10000000 的真值为 $-128$。算术左移一位得到 00000000（按 8 位补码解释为 $0$），但数学结果应为 $-256$， 超出了 8 位补码的可表示范围。

对加法器的补充#

对于固定为 $n$ 位的加法器，实现减法通常将 $B$ 按位取反，并把最低位进位输入设为 $1$， 最后只保留低 $n$ 位：

从上面可以看出，反码类似加法器的一种状态。对于加法器而言，不是直接把 $B$ 取补，而是取反再 $+1$。

补码加减法运算#

本质上，补码加减法运算就是将减法转换为加法。

对 $n$ 位补码运算，结果按模 $2^n$ 截取：

判定溢出与标志位#

判断补码溢出常用以下三种方法。对加法而言，只有同号数相加可能溢出： 两个正数相加得到负数，或两个负数相加得到正数时发生溢出。 对减法而言，只有异号数相减可能溢出：被减数与减数符号不同，且结果符号 与被减数符号不同时发生溢出。

也可以比较进入符号位和从符号位产生的进位：二者不同时发生溢出。

第三种方法是采用双符号位，即 $00$ 表示正数，$11$ 表示负数， $01$ 表示正数溢出，$10$ 表示负数溢出。

需要注意的是，双符号位只在运算过程中使用；存储一个 $n$ 位补码数时仍只保留 1 位符号位。

4 个标志位

• OF：Overflow Flag，代表有符号数运算是否发生溢出。
• SF：Sign Flag，代表运算结果的符号位。
• ZF：Zero Flag，代表运算结果是否为 0。
• CF：Carry Flag，代表无符号运算产生的进位或借位（具体语义取决于指令集）。
  • 对采用“减数取反并加 $1$”的加法器，硬件常用 $\text{CF}=C_{\text{out}}\oplus\text{Sub}$，其中 $\text{Sub}=0$ 表示加法、 $\text{Sub}=1$ 表示减法。
  • 加法运算（$A+B$）：$\text{CF}=C_{\text{out}}$。若最高位产生进位， 则表示无符号加法溢出。
  • 减法运算（$A-B$）：在 x86 等“CF 表示借位”的约定下， $\text{CF}=\lnot C_{\text{out}}$；若 $A<B$，则发生借位。

需要注意的是，对于无符号数的加减法，OF 通常不用于判断无符号溢出； 对于有符号数运算，CF 通常不用于判断有符号溢出，但处理器仍可能同时更新这两个标志位。

乘法#

常见实现有移位加法迭代、顺序乘法器和阵列乘法器。

对于这三者，可以在 CPU 那一章有一个经典的分析，即为什么从时间上来讲，模拟耗时 > 乘法器 > 乘法阵列器。

即大体上来分析，模拟需要消耗多个指令周期，乘法器只需要消耗一个指令周期，而乘法阵列器只需要消耗一个时钟周期。

无符号数乘法（原码一位乘）。思路和手算一样，只是把“错位相加”换成了“部分积右移”。设被乘数 $X$、乘数 $Y$ 都是 $n$ 位：

1. 看乘数最低位 $y_0$，为 1 则部分积加 $X$，为 0 则加 0；
2. 部分积和乘数一起逻辑右移一位；
3. 重复 $n$ 次，最后得到 $2n$ 位的积。

所以顺序乘法器需要 $n$ 次加法和 $n$ 次移位，一个加法器加几个寄存器就能实现，代价是慢。

阵列乘法器把 $n\times n$ 个全加器排成阵列，进位在阵列内部横向传递，一次就能算出 $2n$ 位结果，代价是硬件量大。

有符号数乘法可以直接按原码做：符号位单独异或，数值部分当无符号数乘。也可以用补码直接乘，就是下面的 Booth 算法。

Booth 算法（补码一位乘）。在乘数最低位右边虚设一位 $y_{-1}$，初始为 0，每次看 $y_i y_{i-1}$ 两位：

然后部分积和乘数一起算术右移一位，重复 $n$ 次（$n$ 为乘数位数，最后一步是否移位看具体教材的约定）。

Booth 的好处是不用管符号，正负数走同一套流程，而且乘数里连续的 0 和连续的 1 都只对应很少的加减操作。

除法器的两种方式#

除法的本质是“左移、试减、看余数符号定商”。

恢复余数法：

1. 余数左移一位，减去除数；
2. 若余数为负，说明不够减，商上 0，再把除数加回来恢复余数；
3. 若余数为正，商上 1；
4. 重复 $n$ 次。

恢复余数法的问题是多了一次“加回来”的操作，速度慢。

不恢复余数法（加减交替法）就不恢复了：

1. 若余数为正，商上 1，左移后减除数；
2. 若余数为负，商上 0，左移后加除数；
3. 重复 $n$ 次。

最后一步的规则要注意：如果第 $n$ 步余数为负，需要再做一次加法把它恢复成正确的余数。

需要注意，原码除法是符号单独处理，数值部分按无符号数除；补码除法可以直接做，但商的修正规则（末位恒置 1 还是加 1）要按教材来，不要自己推。

浮点数的表示#

其中 $S$ 是符号位，$1.M$ 是隐含最高位为 1 的规格化尾数（原码小数），$E$ 是把真实阶码加上偏置后得到的无符号阶码字段，$\text{bias}$ 是偏置值。

需要注意，尾数用原码表示，所以不能像补码那样直接按位串比大小；浮点数比较要按符号、阶码、尾数依次比。

• float 型浮点数
  • 符号位：1 位
  • 阶码：8 位
  • 尾数：23 位
• double 型浮点数
  • 符号位：1 位
  • 阶码：11 位
  • 尾数：52 位

做这类题的时候，主要是要小心翼翼，不要脑子抽了。

IEEE 浮点数的表示范围与特殊浮点数#

浮点数的相关计算#

• 对阶：小阶向大阶看齐。阶差为 $d$ 时，小阶的尾数右移 $d$ 位，阶码加 $d$。右移移出的位不能直接扔掉，要保留下来参加后面的舍入
• 尾数加减：对阶之后按定点小数做加减，可能进位，也可能出现前导 0
• 尾数规格化
  • 右规：尾数用双符号位时出现 $01.xxx$ 或 $10.xxx$（加减时进位了），尾数右移 1 位，阶码加 1
  • 左规：出现 $00.0xx\cdots$ 或 $11.1xx\cdots$（对阶时丢了有效位），尾数每左移 1 位，阶码减 1，直到变成 $00.1xx\cdots$ 或 $11.0xx\cdots$
  • 规格化的目的只有一个，让尾数最高位固定为 1，表示唯一，精度最大
• 舍入
  • 就近舍入（0 舍 1 入）：把保留位之后的部分看成 $0.xxx$，小于 $100$ 舍去，大于 $100$ 进 1，恰好等于 $100$ 时向偶数舍入，也就是看保留的末位，末位是 0 就舍，末位是 1 就进 1
  • 直接进位：只要后面还有非 0 位就进 1，误差朝大方向
  • 直接舍去：多余位直接扔掉，误差朝 0
  • 向无穷进位 / 舍去：正数进 1，负数舍去
  • 向 0 进位 / 舍去
• 溢出判断
  • 上溢：阶码超过最大阶码，按机器约定产生异常或置为 $\pm\infty$
  • 下溢：下溢指的是要下溢到非规格化浮点数都表示不了的程度，此时按机器零处理，不再当异常

浮点数与整型转换相关#

int 转 float，不会溢出，但可能会发生精度丢失。因为 float 的尾数只有 24 位有效（含隐藏位），而 int 有 31 位数值。

int 或 float 转 double，精确原值。double 的阶码和尾数都更长，能完整容纳。

double 转 float，可能溢出 / 精度丢失。阶码范围变小了，数值太大就变成 $\pm\infty$。

float 或 double 转 int，小数部分直接丢弃（向 0 取整），超出 int 的范围则结果未定义，一般表现为溢出。

需要注意，转换的顺序会影响结果：先把 float 转成 double 再转 int，和直接转 int 在边界上可能不同，做题时按题目的类型逐次转换。

大端法与小端法#

大端法：高位字节放在低地址，低位字节放在高地址，和人的书写顺序一致。

小端法：低位字节放在低地址，高位字节放在高地址，x86 用的是小端。

例如 32 位整数 0x12345678，从地址 0x1000 开始存放：

需要注意，大小端只影响多字节数据在内存中的字节顺序，不影响单字节的内部位序，也不影响寄存器内部的位序。

做题时判断是哪种方式，就看题目给出的内存内容里，低地址放的是高位字节还是低位字节。

数据对齐#

数据对齐指的是数据的起始地址必须是其自身大小的整数倍。不对齐时可能需要多访存一次，某些平台甚至直接异常。

对齐规则一般是：

• 每个成员的偏移量是其自身大小的整数倍，编译器在成员之间插入填充字节；
• 结构体总大小是其最大成员大小的整数倍，末尾也要填充。

1
struct Test{
2
    char a;
3
    short b;
4
    int c;
5
};

假设首地址是 0x1000H，那么 a 的地址是 0x1000H，b 的地址是 0x1002H（因为边界对齐，所以空 1 位），c 的地址是 0x1004H，结构体总大小为 8 字节。

如果把成员按“从大到小”排列，写成 int c; short b; char a;，那么 c 在 0x1000、b 在 0x1004、a 在 0x1006，总大小还是 8 字节，但没有浪费中间的空隙。

反过来写成 char a; int c; short b;，总大小会变成 12 字节。这就是调整成员顺序可以省空间的原因。

层次化#

CPU - Cache - 主存 - 磁盘 - 磁带/光盘

越往上速度越快、容量越小、单位成本越高；越往下容量越大、速度越慢、单位成本越低。寄存器也在最上层，容量最小、速度最快。

层次化能成立的前提是局部性原理：程序在一段时间内只访问一小部分地址。Cache 同时利用时间局部性和空间局部性，虚拟存储器主要利用时间局部性。

需要注意，各层之间的信息调度主体不同：Cache 与主存之间由硬件自动完成，主存与外存之间由操作系统的缺页处理完成。

辨析存储周期与存取时间#

存储周期 > 存取时间，存储周期 = 存取时间 + 复原时间。

SRAM#

本质为双稳态触发器，无须刷新。静态 RAM 存取速度快，但是集成度低，功耗大，成本高一般用于 cache 上。

DRAM#

本质为电容，需要定时刷新。存取速度较慢，容易漏电丢失信息，读出过程为破坏性读出。

DRAM 需要地址线复用，并且需要注意的是，看清楚题目要求你计算什么。是地址线多少，还是几个 DRAM 组合起来的地址线多少。

例如，对于一个容量为 $16\text{ KB}$、按字节编址的主存系统，CPU 访问该主存所需的系统地址线总共为 $14$ 根，因为 $16\text{ KB}=2^{14}\text{ B}$。

这 $14$ 根地址线（$A_{13}\sim A_0$）的功能划分为：

• 高 4 位地址线（$A_{13}\sim A_{10}$）：用于片选译码。整个 $16\text{ KB}$ 空间按 $1\text{ KB}$ 划分为 16 个模块，通过这 4 根线译码产生片选信号，分别选中 $2\text{ KB}$ 的 ROM 模块以及 14 片 $1\text{ K}\times 8\text{ 位}$ 的 DRAM 芯片；
• 低 10 位地址线（$A_9\sim A_0$）：用于片内寻址。由于单片 DRAM 采用地址线复用技术，该 10 位片内地址在进入 DRAM 芯片前会被分时复用，拆分为 5 位行地址和 5 位列地址，因此所有 14 片 DRAM 的片内地址引脚全部并联接到这组复用线路上。

注意，DRAM 内部是 5 根地址线，然后整个系统的地址总线就是 14。

内存条就是把多片 DRAM 芯片装在一块 PCB 上，再加一个 SPD 芯片（一般是 EEPROM，存容量、时序等参数，开机时由 BIOS 读取）。

需要注意，内存条的数据位宽要匹配内存总线宽度，例如 64 位总线就用 8 片 8 位的芯片并联；带 ECC 的内存条还要额外加校验芯片。

有三种刷新（复原）方式：

• 集中刷新：在规定的最大复原周期内，前面的时间专门划给 CPU 时候，然后最后的时间专门划给刷新，缺点是有死区
• 分散刷新：把每一个系统工作周期分为两半，前半部分用来供 CPU 进行正常的读写操作，后半部分固定用来复原刷新一行存储单元，复原操作完全分散在每一个存取周期内部，系统响应极度平滑，随时可访存；但由于每次存取都要强行带上复原操作，导致整个存取周期直接翻倍拉长，大大降低了存储器的实际工作效率
• 异步刷新：集中与分散的折中方案。假设刷新周期为 2ms，存储阵列有 $128$ 行，就把 2ms 均分为 $128$ 段，每隔约 $15.6\mu s$ 发出一次单行的复原请求。每一行有各自短暂的“死区”（仅占用一个读写周期的时间），死区被完全打散，宏观上几乎感觉不到停顿

对于集中刷新，集中刷新被粗暴分成两个部分，一部分是给 CPU 使用，一部分是给刷新使用。

对于分散刷新，是每一个工作周期都刷新，也就是执行一下，刷新一下。

对于异步刷新，是执行一行刷新一次。

一般采用异步刷新，从而引出了如何设计几行几列：设存储阵列为 $m$ 行 $n$ 列，要求 $m\ge n$，且 $n$ 尽可能接近 $m$。

需要注意，行数越多，单次刷新涉及的单元越少，但刷新次数越多；行列接近正方形时，地址复用最省引脚，芯片内部连线也最短。

对于行缓冲器，一般是 SRAM 实现，用于缓存行数据。

ROM#

断电后不会丢失数据，可靠。

• ROM
  • MROM，掩膜 ROM，不可修改
  • PROM，一次编程 ROM
  • EPROM，可擦除可编程 ROM，使用紫外线擦除且擦除次数有限
  • EEPROM，电擦除可编程 ROM
• Flash 闪存，读写性能不对称
• SSD 固态硬盘

可以注意，主存里一般是有 ROM 的，因为要存储 BIOS。

SRAM、DRAM 与 Flash 的对比#

需要注意，Flash 的读和写粒度不同：读以页为单位，写（编程）也是页，但擦除必须以块为单位，所以随机写要先读出整块、改完再写回，这也是 SSD 随机写慢的根本原因。

NOR Flash 可以按字节随机读，支持片内执行，常用来存 BIOS；NAND Flash 按页读写、成本低、容量大，用来做 SSD 和 U 盘。

多模块存储器#

• 连续编址，高位地址作为模块号，低位地址为模块内地址，各个模块不能并行访问，无法提高存储器的吞吐率。

• 交叉编址（低位编址），低位地址用作模块号，高位地址作为模块内地址。

  • 轮流启动：按模块号轮流启动，每个模块的存取周期为 $T$，总线传送周期为 $r$，则连续读取 $m$ 个字所需的时间为 $t=T+(m-1)r$
  • 同时启动：一次性取 $n$ 个模块，即连续几个字节一起读，可以理解为类似超字长
  • 需要注意，交叉编址能提高带宽的前提是 $m\ge \frac{T}{r}$，否则模块还没复原完，下一轮又轮到它了

需要注意，多模块交叉存储提高的是带宽，不是单个字的访问延迟。单个字的延迟还是由模块本身决定。

位扩展#

芯片的字数够、位数不够。所有芯片的地址线、片选线并联，数据线分别接到不同的位，几片一起构成一个更宽的字。

例如用 $1\text{ K}\times 4$ 位的芯片组成 $1\text{ K}\times 8$ 位的存储器，需要 2 片，两片的地址线全部并联，一片接 $D_0\sim D_3$，另一片接 $D_4\sim D_7$，读写同时进行。

字扩展#

位数够、字数不够。数据线并联，地址线的低位并联，高位用来译码产生片选信号。

例如用 $1\text{ K}\times 8$ 位的芯片组成 $4\text{ K}\times 8$ 位的存储器，需要 4 片，地址线 $A_9\sim A_0$ 并联，$A_{11}A_{10}$ 经 2-4 译码器产生 4 个片选信号。

字位扩展#

两者都需要，先位扩展成一组，再把多组字扩展。

需要注意，片选信号的产生有两种方式：

• 线选法：高位地址线直接作为片选，简单，但地址空间有空洞，不能充分利用；
• 译码片选法：高位地址经译码器产生片选，地址连续，用得多，但要考虑译码器的使能端接法。

计算地址范围时，先算出每片的容量，再乘以片数，然后根据题目给的起始地址写出十六进制范围，不要凭印象写。

cache 的基本工作原理#

主存和 Cache 都按块划分，块大小相同，块内地址一一对应。

CPU 访存时，先用地址中的某几位判断它落在 Cache 的哪一行，再比较标记，标记一致且有效位为 1 就是命中，直接读 Cache；否则就是不命中，需要从主存把整个块调入，再按替换算法决定换出哪一块。

所以一次访存的时间取决于命中率，而命中率取决于程序局部性和映射、替换策略。

需要注意，Cache 与主存之间以块为单位交换，CPU 与 Cache 之间以字为单位访问，块大小的选择是空间局部性和缺失代价的折中。

局部性原理#

• 时间局部性：访问我之后，在短时间内还会再访问自己
• 空间局部性：访问我之后，在短时间内会访问我身边的人

cache 命中率#

• 耗时
  • 在访问 cache 时同时读主存
  • 在访问 cache 后发现未命中，再读主存
  • 这两种方案看具体题目怎么讲

设命中率为 $h$，Cache 访问时间为 $t_c$，主存访问时间为 $t_m$。

同时访问时，未命中也不用再等一次 Cache，所以

先查 Cache、未命中再查主存时，未命中的那一次要先把 Cache 查完，所以

效率是

需要注意，题目说“Cache 与主存同时访问”时，主存里也要有这一块的数据，命中时主存的读出结果被丢弃，这是用硬件换时间。

多级 Cache 要分清局部缺失率和全局缺失率：局部缺失率是相对于本级的访问次数算的，全局缺失率是相对于 CPU 的总访问次数算的，两者的分母不同。

cache 映射方式#

• 直接映射
• 全相联映射
• 组相联映射

设 Cache 有 $2^c$ 行，块大小是 $2^b$ 字节，主存地址 $m$ 位。

直接映射：地址分为标记、行号、块内地址。行号 $c$ 位，块内地址 $b$ 位，标记 $m-c-b$ 位。一个主存块只能放到固定的行，硬件只需要一个比较器，冲突多。

全相联映射：地址分为标记、块内地址。标记 $m-b$ 位。任何块可以放到任何行，冲突最少，但要和所有行的标记同时比较，成本高，只适合小容量。

组相联映射：Cache 分成 $2^s$ 组，每组 $k$ 路。地址分为标记、组号、块内地址。组号 $s$ 位，标记 $m-s-b$ 位。这是前两者的折中，$k=1$ 就是直接映射，$k$ 等于行数就是全相联。

需要注意，块内地址的位数只由块大小决定，和 Cache 总容量无关；组号位数由组数决定，组数等于行数除以路数。

地址划分的位数一旦算错，后面的命中判断全错，所以做题第一步先把三个字段的位数写在草稿上。

命中率的典型场景分析见后面单独的一节。

cache 替换算法#

• RAND
• FIFO：对于 FIFO，需要注意其并不是按照物理顺序存进去的，而是也要存一个 id 来记录
• LRU：最近最少使用，对于 $n$ 个块需要 $\lceil\log_2 n\rceil$ 位来记录。每次访问都把自己的计数器清零，其他块的计数器 +1，替换则是替换掉计数器最大的（也就是最久没被访问的）
• LFU：最不经常使用算法，即新装入时计数器初始化为 0，每次访问 +1（到最大值了则是不变）。每次替换替换掉最小的。这个方法的问题是全局较大可能并非近期需求最大，例如半个小时前正在微信通话，而微信通话结束了，现在任务需求是聊天，那么微信通话的版块会持续占用

cache 一致性问题#

• cache 写命中处理
  • 全写法（直写法）：同时写入主存和 cache，可以引入缓冲机制
  • 回写法（写回法）：仅写回 cache，提高了 cache 效率
• cache 写不命中处理方法
  • 写分配法：写入主存对应单元，然后调入 cache（也有的书是先调入 cache 再写 cache），具体题目具体分析
  • 非写分配法：不命中直接写入主存，不调入 cache

四种组合里，全写法配非写分配、回写法配写分配是最常见的搭配：全写法每次都要写主存，再调入 cache 意义不大；回写法只写 cache，不调入的话修改无处落地。

需要注意，写分配法会带来一次额外的块调入，如果程序写的是整块数据（比如清零一个大数组），反而非写分配更快。

cache 的容量与位数计算#

注意指令 cache 与数据 cache 分离（看题目里具体要求）。

有效位是必要的，因为 cache 的命中与否需要通过有效位来判断。

对于脏位，则是回写法需要。

对于替换算法，例如 LRU，FIFO，LFU 需要替换算法位（注意直接映射不需要替换算法）

其他的是标记位 tag，数据位。

总位数可以按行算：

需要注意，写回法才有脏位，直接映射没有替换算法位，这两项是最容易漏的。

cache 的应用#

• cache 数据与指令分离
• 多级 cache

关于 cache 其他需要注意的事项#

cache 块大小和 cache 本身大小无关。

虚拟存储器与 cache 的辨析#

两者都建立在局部性原理上，但方向不同：Cache 解决的是速度，虚拟存储器解决的是容量。

Cache 的缺失由硬件处理，代价是几十个时钟周期；虚存的缺页由操作系统处理，代价是毫秒级，所以虚存的缺失率必须极低。

正因为缺失代价太大，虚存几乎都采用全相联或大组相联，替换算法接近 LRU，写策略采用写回法。

虚存的地址转换是硬件（MMU）做的，但页表的填写、缺页的调入是操作系统做的，所以是软硬件结合。

页式虚拟存储器#

虚拟地址分成虚页号和页内偏移，物理地址分成实页号和页内偏移，页内偏移不变，只换页号。

页表项一般包含：有效位（是否在内存）、物理页号、访问权限、脏位（是否被修改）、访问位（供替换算法使用）。

地址转换：CPU 给出虚地址，MMU 用虚页号查页表得到物理页号，再和页内偏移拼成物理地址。

需要注意，页表在主存里，所以不命中 TLB 时一次访存要访问两次主存（一次查页表，一次取数据），这就是引入 TLB 的原因。

页表的表项数和虚拟地址空间大小有关，和物理内存大小无关；页表本身可能很大，所以用多级页表，只把用到的页表页放在内存里。

段式虚拟存储器#

段是按程序的逻辑结构划分的，每段长度不同，段表项包含段长、段基址、权限等。

虚地址分成段号和段内偏移，转换时用段号查段表得到段基址，再加上段内偏移。

需要注意两点：段内偏移不能超过段长，否则越界；段式便于共享和保护，因为段是有意义的逻辑单位（代码段、数据段、栈段）。

段页式虚拟存储器#

先把程序按逻辑分段，再把每个段分成固定大小的页。

虚地址分成段号、段内页号、页内偏移。转换时先查段表得到该段页表的基址，再查页表得到物理页号。

所以不命中 TLB 时，一次访存最多要查三次主存：段表、页表、数据。TLB 里通常直接存放最终的映射，避免重复查表。

组相联 TLB#

与 cache 类似。

辨析 TLB，Page 和 cache 的层次#

见下面的分析。

页号、块号与具体地址#

需要辨析，不要相互混淆，尤其是在做题的时候，给的是第 x 块，而不可以将之当成具体地址去算 cache。

由于边界对齐，所以很多时候都不需要存完整的地址，存“块”地址即可。

场景 1 深入辨析（容量截断效应）#

1. 数据规模与排布 - 1#

• 数组规模：$1024 \text{ 行} \times 64 \text{ 列}$。
• 数组总大小：$1024 \times 64 \times 4\text{ B} = 256\text{ KB}$。
• 每行大小：$64 \times 4\text{ B} = 256\text{ B}$（跨越 $256 / 64 = 4$ 个 Cache 块）。
• 核心关系：数组总容量（$256\text{ KB}$）$\gg$ Cache 容量（$8\text{ KB}$）。

2. 行优先访问分析 - 1#

• 访问模式：按内存连续物理地址线性扫描。
• 命中过程：
  • 每当访问到新 Cache 块的首个元素时，发生 1 次冷缺失（Cold Miss），并将包含连续 16 个 int 的整块装入 Cache。
  • 紧随其后的 15 个元素全部命中空间局部性（Hit）。
• 命中率计算： $\text{Hit Rate}_{\text{行}} = \frac{16 - 1}{16} = \frac{15}{16} = 93.75\%$ 满足命中率 $\ge 90\%$ 的要求！

3. 列优先访问分析 - 1#

• 访问模式：外层循环遍历列，内层循环遍历行。
• 访存步长（Stride）：每次访问跨越一行，步长为 $256\text{ B}$（$4$ 个块）。
• 命中过程：
  • 遍历第 0 列时，依次访问 A[0][0], A[1][0], ..., A[1023][0]，共访问 1024 个元素，分布在 1024 个互不相同的 Cache 块中。
  • 遍历整列需要的数据量为 $1024 \times 64\text{ B} = 64\text{ KB}$。
  • 但 Cache 只有 $8\text{ KB}$（只能存 128 个块）！当访问到第 128 行以后，前面装入的块早就被 LRU 策略无情淘汰冲刷掉了。
  • 当第 0 列全部结束、开始访问第 1 列的 A[0][1] 时，原本包含该元素的块早在一万年前就被踢出了 Cache！
  • 因此，每个元素在被访问时，其所在的块都不在 Cache 中。
• 命中率计算： $\text{Hit Rate}_{\text{列}} = 0\%$ 完美达成列访问 $0\%$ 的指标！

场景 2 深入辨析（工作集常驻效应）#

1. 数据规模与排布 - 2#

• 数组规模：$64 \text{ 行} \times 24 \text{ 列}$。
• 数组总大小：$64 \times 24 \times 4\text{ B} = 6144\text{ B} = 6\text{ KB}$。
• 占用的 Cache 块数：$6144\text{ B} / 64\text{ B} = 96$ 个块。
• 核心关系：数组总容量（$6\text{ KB}$）$<$ Cache 容量（$8\text{ KB}$，可容纳 128 个块）。
• 决定性结论：整个数组可以被 Cache 100% 完全装下，遍历全程不会触发任何容量替换（Capacity Eviction）！

2. 行优先访问分析 - 2#

• 访问总次数：$64 \times 24 = 1536$ 次。
• 缺失情况：按行线性读入，共经历 $96$ 个数据块，因此发生 $96$ 次冷缺失（Cold Miss）。
• 命中情况：其余所有访问均为块内空间局部性命中，命中次数为 $1536 - 96 = 1440$ 次。
• 命中率计算： $\text{Hit Rate}_{\text{行}} = \frac{1440}{1536} = \frac{15}{16} = 93.75\%$

3. 列优先访问分析 - 2#

• 访问总次数：同样是 $1536$ 次。
• 缺失情况：
  • 列优先访问时，由于数据跳步访问，冷缺失的发生时刻被打散了。
  • 但是，因为 Cache 容积（128 行）大于数组占用的总行数（96 行），一旦某个块因冷缺失被调入 Cache，在整轮遍历结束之前，它就永远不会被挤出 Cache！
  • 这意味着：整个数组占据的这 96 个块，无论按什么乱七八糟的顺序访问，每个块都仅且只会在第一次被触碰时发生 1 次冷缺失！
  • 整个遍历过程的总缺失次数依然严格等于 96 次！
• 命中情况：除了 96 次初次调入外，剩下的 $1536 - 96 = 1440$ 次访问，全部命中！
• 命中率计算： $\text{Hit Rate}_{\text{列}} = \frac{1536 - 96}{1536} = \frac{1440}{1536} = 93.75\%$

两者命中率不仅完全相同（均为 $93.75\%$），而且远超 $80\%+$！

场景 3 $1024 \times 4$ 的长条矩阵#

我们选取体系结构中极为经典的小列宽长矩阵：$1024 \text{ 行} \times 4 \text{ 列}$ 的 int 数组。

• 一行的大小：$4 \text{ 列} \times 4\text{ B} = 16\text{ B}$。
  • 核心几何特征：$16\text{ B} < 64\text{ B}$，一个 Cache 块内部可以横向并排严丝合缝地塞进 $64\text{ B}/16\text{ B}=4$ 行数组数据。
• 数组总容量：$1024 \times 4 \times 4\text{ B} = 16384\text{ B} = 16\text{ KB}$。
  • 核心容量特征：数组总容量（$16\text{ KB}$）等于 Cache 容量的 2 倍（$8\text{ KB}$），Cache 无法一次性容纳整张数组，遍历全程会发生残酷的容量替换（Capacity Eviction）！
• 数组占用的总 Cache 块数：$16\text{ KB} / 64\text{ B} = 256$ 个块。

场景 3 访问全流程深入推演#

1. 行优先访问 - 3#

• 访问模式：内存连续线性地址访问。
• 过程推演：
  • 每当指针跨过一个 64B 边界时，触发 1 次冷缺失（Cold Miss），将 64B（连续 16 个 int，即整整 4 行数据）调入 Cache。
  • 随后的连续 15 次访问全部在同一 Cache 行内命中（Hit）。
• 命中率计算： $\text{Hit Rate}_{\text{行}} = \frac{16 - 1}{16} = \frac{15}{16} = 93.75\%$ （连续空间局部性完美发挥，依然高达 $93.75\%$！）

2. 列优先访问 - 3#

• 访问模式：外层按列循环，内层按行循环（依次访问第 0 列的 A[0][0] ~ A[1023][0]，接着第 1 列……）。
• 跨度与块内渗透：
  • 访问 A[0][0]：缺失（Miss）！系统从内存调入包含 A[0][0] ~ A[3][3] 的整整 64 字节块。
  • 访问 A[1][0]：命中（Hit）！它就在刚才载入的块的第 2 个 16B 槽位里。
  • 访问 A[2][0]：命中（Hit）！它在同一个块的第 3 个 16B 槽位里。
  • 访问 A[3][0]：命中（Hit）！同样命中！
  • 访问 A[4][0]：跳出当前块范围，缺失（Miss）！调入下一块（包含第 4~7 行）。
  • 访问 A[5][0], A[6][0], A[7][0]：连续 3 次命中！
• 容量颠簸效应：
  • 当第 0 列全部遍历完时，共访问了 1024 个元素，消耗了 256 个 Cache 块的装载。
  • 但 Cache 只有 128 行！依据 LRU 策略，前半段（前 128 个块）早就被后半段冲刷出去了。
  • 因此，当开始遍历第 1 列的 A[0][1] 时，先前调入的块已经不在 Cache 中，无法享受列与列之间的时间局部性！
  • 也就是说：每一列都要重新经历一次上述的“一漏三中”周期！
• 命中率计算： 在每一列内部，每连续 4 个垂直元素中，必有 1 次缺失，3 次命中： $\text{Hit Rate}_{\text{列}} = \frac{4 - 1}{4} = \frac{3}{4} = 75\%$

cache 命中率辨析#

第二个的本质是所有数据小于整个 cache。

第三个的本质是一行数组数据小于一个 cache 行。

阶段一：硬件初次地址转换与 TLB 缺失#

1. 发出虚拟地址：CPU 从程序计数器（PC）发出取指的 32 位虚拟地址 VA。
2. 查 TLB：MMU 提取 22 位 VPN，用其中的 3 位组索引定位 TLB 组，对比各路 Tag。
3. TLB Miss：初始全空，TLB 缺失。

阶段二：访存查页表与触发缺页异常（Page Fault）#

1. 查页表（Page Walk）：
   • MMU 结合页表基址寄存器（PTBR）与 VPN 计算出页表项（PTE）的物理地址并访问主存。
2. 检测到缺页：
   • 读出 PTE 后，硬件发现其有效位 Valid = 0，说明该页面尚未被调入物理内存中！
3. 抛出异常：
   • MMU 产生缺页异常（Fault），CPU 中断当前取指流程，保存当前的 PC 和程序状态字（PSW），硬件从用户态切换到内核态（核心态）。

阶段三：操作系统内核接管处理（缺页中断服务程序）#

1. 保护现场：OS 保存各通用寄存器现场。
2. 合法性检查：读取引发异常的虚拟地址（如 x86 的 CR2 寄存器），检查该地址是否合法（在进程的合法逻辑空间内且有执行权限）。
3. 分配物理页框：在主存中寻找一个空闲的物理页框（Frame），假设分配到的物理页号为 $\text{PPN}_x$。
4. 启动磁盘 I/O（调页）：
   • OS 向外存（磁盘/交换区）控制器发出读命令，将该页对应的 1KB 指令数据从外存读入到刚才分配的物理页框中。
   • 此时当前进程被置为阻塞态，CPU 调度其他进程执行（DMA 传输数据中）。
5. I/O 完成中断：
   • 1KB 数据全部传输进物理内存后，磁盘控制器发出 I/O 中断，OS 唤醒该进程。
6. 修改页表项（PTE）：
   • OS 将该页对应的 PTE 填入物理页号 $\text{PPN}_x$，将有效位置为 Valid = 1，设置访问权限。
7. 恢复现场与返回：
   • 恢复原进程现场，执行异常返回指令（如 iret），重新执行刚才被中断的那条取指指令，CPU 切回用户态。

阶段四：重新取指与第二次地址转换#

1. 重新发出 VA：PC 再次送出刚才的 32 位虚拟地址 VA。
2. 再次查 TLB：
   • 硬件再次用 VPN 查 TLB，依然 TLB Miss（因为刚才缺页处理一般不手动塞 TLB，或者即使软件重填此处也按标准硬件流程来走）。
3. 再次查页表：
   • MMU 再次通过 PTBR + VPN 查主存页表。
4. 页表命中（Hit）：
   • 这一次读到的 PTE 中 Valid = 1，成功读出物理页号 $\text{PPN}_x$！
5. 写入/更新 TLB：
   • MMU 将这次成功的映射对 (TLB Tag, PPN_x, 属性) 填入 TLB 对应的组中，有效位置 1。

阶段五：物理地址拼接与 Cache 访问#

1. 拼装物理地址 PA：
   • 将 18 位的 $\text{PPN}_x$ 与 10 位的页内偏移拼合，得到 28 位物理地址 PA。
2. 查询 Cache：
   • 用 PA 的中间 6 位定位 Cache 组，比对该组内 4 个路（Way）的 16 位 Cache Tag。
3. Cache Miss：
   • 因为 Cache 初始全空，发生 Cache 冷缺失。
4. 从主存装入 Cache：
   • 发出 PA 向主存（刚才刚刚从磁盘调入指令的物理页中）读取该指令所在的 64B 数据块。
   • 将 64B 载入到 Cache 对应组的一个空闲槽位中，填入 Cache Tag，有效位置 1。
5. 指令送达 CPU：
   • 从这 64B 的 Cache 块中，依据 PA 的低 6 位（Block Offset）截取出目标指令。
   • 送入指令寄存器（IR），CPU 终于可以开始译码执行了！

指令格式#

操作码 - 地址码

事实上，这个地址码的名我认为有点误导，因为其实不是地址码，更准确的来说应该是操作数。

根据指令的不同执行阶段，来划分这个地址码到底应该解释成什么。

• 零地址指令
• 一地址指令
• 二地址指令
• 三地址指令

关于上面的指令，如果题目没说，那么默认按照 x86 格式解析。

但是也应该具体题目具体分析。

定长与变长操作码#

可以迁移到计网的子网划分那块去理解，以及哈夫曼树。

定长操作码的位数固定，译码简单，但指令条数被限制在 $2^n$ 以内，浪费编码空间。

变长操作码（扩展操作码）把地址码的部分位拿来当操作码用，从“地址多、条数少”的指令开始分配，留出前缀给“地址少、条数多”的指令。

例如指令字长 16 位、每个地址码 4 位：

• 三地址指令的操作码有 4 位，最多 16 条，如果只安排 15 条（0000 到 1110），剩下的 1111 就可以用来扩展；
• 用 1111 当前缀，操作码变成 8 位，地址码剩两个，又能安排 16 条二地址指令；
• 如果二地址只用了 14 条，剩下的两种前缀又能各扩展出 16 条一地址指令，共 32 条。

需要注意两点：

• 扩展操作码必须满足“短操作码不能是长操作码的前缀”，否则译码有歧义，这和哈夫曼编码的规则是同一件事；
• 做这类题从地址最多的指令开始算，先确定留下的前缀数，再逐级往下推。

指令的类型#

• 数据传送指令
• 算术和逻辑运算指令
• 移位操作指令
• 顺序控制指令
• 输入输出指令
• CPU 控制指令

具体题目具体分析。

指令寻址#

指令寻址分为顺序寻址和跳跃寻址。

辨析 PC 与指令格式#

假设计算机主存为 4GB，采用 32 位的指令字。PC 指的是什么，PC 指的是程序计数器。也就是说，PC 是用来存储当前要执行的指令的地址的。那么总共有多少条指令呢？显然是 4GB/32bit，即 $2^{30}$ 条指令，所以 PC 至少需要 30 位。

相关的题目我认为本质上是需要辨析清楚 PC 的作用。

数据寻址#

• 隐含寻址：操作数隐含在指令或处理器约定中，例如 ALU 的累加器（AC）寄存器； 对双操作数指令，另一个操作数可能是隐含的。
• 立即寻址：立即数寻址即指令中直接给出操作数。
• 直接寻址：直接寻址即指令中直接给出操作数的地址，需要通过这个地址找到真正的数据。
• 间接寻址：间接寻址即指令中给出操作数地址的地址，需要通过这个地址的地址找到操作数的地址，然后通过这个地址找到真正的数据。
• 寄存器寻址：寄存器寻址即指令中直接给出操作数的寄存器，需要通过这个寄存器找到真正的数据。
• 寄存器间接寻址：指令给出保存操作数地址的寄存器，通过该寄存器中的地址找到数据。
• 相对寻址：相对寻址即指令中给出操作数相对地址，按 ISA 约定的 PC 基准（通常为下一条指令地址） 加上位移来找到真正的数据。
• 基址寻址：基址寻址以寄存器中的基地址加上偏移量形成有效地址，常用于数组、栈和结构体访问。
• 变址寻址：可以理解为数组寻址，基于数组首地址和偏移量来寻址， 例如 $\mathtt{0x1000}+4\times10=\mathtt{0x1028}$，即元素 a[10] 的地址（假设元素大小为 4 字节）。
• 堆栈寻址：可以理解为汇编的 push 和 pop 指令。

把寻址方式放在一起对比，重点看有效地址怎么来、取操作数要访存几次：

需要注意，基址寻址和变址寻址的式子长得一样，但用途相反：基址寄存器由操作系统设定，面向系统，用于程序重定位和多道程序；变址寄存器由用户设定，面向用户，用于数组和循环。

相对寻址的基准是“下一条指令的地址”，不是当前指令的地址，因为取指后 PC 已经自增了。

CISC#

对于 CPU 采用微程序控制方式。

指令多，指令功能强，大部分指令使用的很少。

指令一般大于 100 个。

指令长度不固定，寻址方式多，访存指令不受限制，通用寄存器数量少。

RISC#

对于 CPU 采用硬布线方式。

指令小于 100 个。

必须实现指令流水线。

指令长度固定，寻址方式少，只有 load/store 访存，通用寄存器数量多，大多数指令能在一个时钟周期内完成。

两者的对比#

需要注意，CISC 不等于“一定用微程序”，RISC 也不等于“一定不能有微程序”，这只是主流的实现倾向；同样，RISC 的程序代码量更大，但换来的是流水线友好。

指令周期相关#

一个完整的指令周期通常分成四个阶段：

• 取指周期：从 PC 指向的主存单元取出指令送到 IR，PC 加上指令字长；
• 间址周期：如果指令采用间接寻址，还要再访存一次取有效地址；
• 执行周期：真正做运算或访存；
• 中断周期：指令执行完检查是否有中断请求，有则保存断点、关中断、转入中断服务程序。

需要注意，不是每条指令都有间址周期和中断周期，取指周期和执行周期是必需的。

时钟周期、机器周期（CPU 周期）和指令周期的关系是：一个指令周期包含若干个机器周期，一个机器周期包含若干个时钟周期。

四个周期都可能访存，所以数据通路上的 MAR、MDR 是共用的，这也是单总线结构下不同周期要分时使用总线的根本原因。

需要注意，这里的四阶段是指令周期的划分，描述一条指令的生命周期；它和流水线的 IF / ID / EX / MEM / WB 五段不是一回事，五段式是流水段的划分，里面没有间址周期，中断也在取指段末尾顺便采样。五段式的展开见后面一条指令的不同阶段那一节。

见下面的模型分析。

处理器指令执行模型#

• 单周期处理器
  • CPI 为 1
  • 不擅长乘除法等复杂指令（因为这类指令需要运行的时间很久）
  • 不需要指令寄存器
• 多周期处理器
  • 将指令周期分为多个时钟周期
• 流水线处理器
  • CPI 接近 1

需要与单总线处理器辨析。

单周期处理器不可能是单总线处理器。

数据通路组织与分类#

• 按部件连接方式划分
  • 总线式数据通路
  • 专用数据通路
• 按时序组织方式划分
  • 单周期数据通路
  • 多周期数据通路
  • 流水线数据通路

单总线结构数据通路#

可见后续 2009 年真题，数据如何流动。

专用数据通路#

专用数据通路就是每个部件之间都有专门的数据线连接，不共享总线，可以并行传送，速度快但线路多。

单总线结构是所有部件挂在一条总线上，同一时刻只能有一对部件通信，所以要分多个时钟周期才能完成一次运算。

需要注意，考试里给单总线结构的数据通路图，就是要你按时钟节拍写出每个节拍的微操作。核心规则只有一条：同一时刻总线上只能有一个输出，写寄存器时要写使能。

辨析 CPU 内部的 CU 与数据通路#

CPU 大致可以分为负责做决策的 CU 以及下面负责干活的数据通路。

而数据通路又可以分为 ALU，寄存器组。

在做题的时候可以先想想物件是属于 CU 的，还是属于数据通路的。

微程序的工作流程#

和正常指令执行类似，先执行一段公共的取指微程序：从主存中取出机器指令送入 IR，并完成 PC 的更新。

随后根据 IR 中的操作码，通过微地址形成部件生成该机器指令对应微程序的首条微指令地址，送入 μPC。

接着从 CM 中取出首条微指令送入 μIR，之后就是逐条取出、逐条执行，直到这条机器指令的微程序结束。

微程序和机器指令#

一个机器指令对应一个微程序。

微程序总数 = 机器指令条数 + 公共微程序数

微程序的编码#

• 直接编码（直接控制）方式：每一位直接对应一个微命令
• 字段直接编码方式：将控制字段分成若干字段，每个字段分别编码，需要注意加一个停机位。比如说有 4 个互斥类，分别有 1，2，3，4 个微命令，加上停机位则是 2，3，4，5，所以分别需要 1，2，2，3 位来存储。
• 字段间接编码方式：某个微命令字段的实际含义由另一个字段的编码共同决定
  • 字段 A（模式选择字段，1 位）字段 B（具体操作字段，3 位）
  • 比如字段 A 为 0 的时候，代表算术模式，为 1 的时候为访存模式

微程序地址形成#

• 增量方式（计数器方式）：μPC 自动 + 1
• 断定方式（下址字段方式）：当前微指令显式指定下条微地址

实际运行时取决于以下三种情况

• 微程序入口地址形成：一条机器指令从主存中取出并送入 IR 后，其操作码经微地址形成部件生成对应微程序的首条微指令地址，送入 μPC
• 顺序执行
• 条件分支

微程序指令格式#

• 水平型指令：操作控制（n 位），顺序控制（判断测试字段，后继地址字段）

• 垂直型指令：微操作码，目的地址，源地址

  • 指令短，编写简单，但是微程序长，执行速度慢

• 水平并行能力强

• 一条水平可以完成更多工作

• 水平指令字长但微程序短

• 水平编写难度大，垂直类似机器指令好编写

异常#

异常是 CPU 在执行指令的过程中由内部检测到的意外事件，和当前指令有关。

• 故障（fault）：缺页异常，除 0 异常，处理完回到本条指令重新执行
• 自陷（trap）：由陷入指令主动触发，例如系统调用、断点，处理完执行下一条
• 终止（abort）：硬件故障等致命错误，处理程序一般直接终止进程

中断#

中断是外部设备发出的请求，和当前指令无关，响应在一条指令执行完之后。

• 可屏蔽中断：受中断屏蔽字和 EINT 控制，键盘、磁盘等普通外设
• 不可屏蔽中断：不受 EINT 影响，用于电源掉电等紧急情况

异常和中断的检测与响应#

检测的时机不同：中断请求在每个指令周期的末尾统一采样，异常在指令执行过程中由内部逻辑检测。

响应需要满足条件：有请求、CPU 处于开中断状态（对可屏蔽中断）、当前指令执行完（对中断）。

响应的过程由中断隐指令完成，全部由硬件自动实现：

• 关中断，防止响应过程被打断；
• 保存断点，把 PC 和 PSW 压栈或存入指定单元；
• 识别中断源并转入中断服务程序，可屏蔽中断一般通过中断向量表。

需要注意，隐指令不是指令，它没有操作码，也不在指令系统中，是硬件在响应阶段自动做的一串动作。

中断处理程序的完整流程在 I/O 那一章展开，这里只要记住“硬件做前一半，软件做后一半”。

指令流水线操作#

见本节模型。

先把性能指标写清楚。设流水线有 $k$ 段，每段时间为 $\Delta t$（取最慢的那一段），连续执行 $n$ 条指令，则总时间为

吞吐率、加速比和效率分别是

当 $n\to\infty$ 时，$TP\to 1/\Delta t$，$S\to k$，$E\to 1$。

需要注意，段数不是越多越好：段数增加后，每段的时间受流水寄存器开销限制，而且冒险带来的停顿会变多，实际加速比远小于 $k$。

流水线时空图就是把每条指令画成一行、横轴是时间，斜着看就是流水，有停顿的地方画一段空白。

MIPS 指令#

见上一节模型。

结构冒险#

即共同争夺某种资源，又称资源冲突。例如取指和访存同时要用存储器，或者两条指令同时要用同一个功能部件。

处理办法：

• 资源重复：把指令存储器和数据存储器分开（哈佛结构），或者增加功能部件、增加端口；
• 分时使用：同一部件在不同流水段轮流使用，代价是插入停顿。

数据冒险#

例如写后读：后一条指令要读的寄存器，正好是前一条指令还没写回的结果。

数据冒险有三种：写后读（RAW）、读后写（WAR）、写后写（WAW）。按序流水线只可能出现 RAW，乱序流水线三种都要考虑。

处理办法：

• 延迟指令：插入气泡，等结果写回再继续；
• 旁路转发：把 ALU 的结果直接送给下一条指令的输入端，不用等写回寄存器，能解决大多数 RAW；
• load-use 冒险：load 的数据要到 MEM 末尾才出来，转发也来不及，必须停一个周期，然后再转发。

这三类处理见后续模型。

控制冒险#

对于 if / loop 相关指令，需要等待条件跳转判断是否成立。

主要有几种解决方案：

• 延迟分支处理：把一条一定执行的指令放进延迟槽，或者插入气泡
• 分支预测技术：尽早生成目标地址并预测方向
  • 静态预测：每次都选择成立 / 不成立
  • 动态预测：根据程序运行时的历史信息来预测，常用两位饱和计数器和分支历史表
  • 预测错误：需要清除流水线，惩罚是已经取入的指令条数

需要注意，分支预测只解决“猜方向”，目标地址的计算还要在 ID 段尽早完成，否则就算方向猜对了也要等地址算出来。

高级流水线技术#

• 超标量流水线：增加功能部件（硬件），结合动态分支预测以及乱序执行
• 超长指令字技术：多条并行的指令合成一个长指令字
• 超流水线技术：把一个指令进一步细分成更多的流水段，理想情况下 CPI < 1

需要注意，超标量的并行是硬件在运行时找出来的（动态），超长指令字的并行是编译器在编译时打包好的（静态），后者对编译器要求高，但硬件简单。

动态流水线指的是流水段可以按需重组，允许指令乱序执行、乱序完成，但必须顺序提交，以保持程序语义。

SISD#

单指令单数据流。

SIMD#

单指令多数据流，代表为向量处理器。

向量处理器的一条向量指令处理一整个向量，内部用流水线的方式逐元素计算，元素之间没有数据相关性，所以能流水起来，还能用链接技术把多条向量指令串起来。

需要注意，SIMD 的并行度受向量长度限制，遇到条件分支不好处理，所以后来又有带掩码的向量指令。

MISD#

多指令单数据流（无应用）

MIMD#

多指令多数据流，应用有多计算机系统 / 多处理器系统。

硬件多线程#

• 细颗粒度多线程：每个时钟周期轮流切换不同线程的指令执行，可隐藏短流水线停顿，但单线程执行被拉长。
• 粗颗粒度多线程：平时专注跑单一线程，仅在发生重大停顿（如 Cache 缺失）时才切换到其他线程，切换有充填开销。
• 同时多线程：基于多发射超标量流水线，允许在同一个时钟周期内同时发射和执行多个不同线程的指令，硬件利用率最高。

多核处理器#

一个 CPU 有多个核，实现真正的并行。

但是需要注意的是，多任务操作系统并发就足够了。

共享内存多处理器#

多个处理器核心围着“同一口超级大饭锅”吃饭！

1. 共享单一地址空间： 系统里虽然有多个 CPU（或处理器核心），但它们看到并使用的是同一个统一编址的物理内存空间。任何一个 CPU 都可以直接通过访存指令（Load/Store）去读写整个内存里的任意一个地址。

2. 通信方式超简单（靠内存通信）： 处理器之间不用像发微信、寄快递（消息传递）那样麻烦，CPU-A 想给 CPU-B 传数据，只需要写到某块内存变量里，CPU-B 直接去读这个变量就拿到了。

3. 关键难点：同步与一致性： 大家都在读写同一个地方，就容易“抢饭吃”发生打架（数据冲突/读写冲突）！所以硬件必须提供 Cache 一致性协议（确保各 CPU 的私有 Cache 里数据是一致的），软件上也需要加锁/互斥机制来保证同步。

4. 常见两大家族：

   • UMA（均匀存储访问 / 经典 SMP）：每个 CPU 访问内存中任何区域的时间都是一模一样的（平权模式）。
   • NUMA（非均匀存储访问）：内存物理上分块挂在不同 CPU 旁边，访问自己身边的“本地内存”超快，访问挂在别人那里的“远程内存”稍慢，但逻辑上依然是一个统一的大内存。

指令一：RISC 纯算术指令 ADD R1, R2, R3#

语义：$R1 \leftarrow R2 + R3$（寄存器之间运算，完全不碰内存）

1
[IF] 取指 -> [ID] 译码 + 读 R2/R3 -> [EX] ALU 算加法 -> [MEM] 旁路空闲 -> [WB] 写回 R1

1. 取指令阶段（IF）：
   • PC 送出地址，从 Instruction Cache 中读取 32 位定长指令字到 IR。
   • PC 自动递增：$\text{PC} \leftarrow \text{PC} + 4$。
2. 分析指令 / 译码阶段（ID）：
   • 译码：硬件识别出操作码为 ADD。
   • 读寄存器：由于 RISC 指令格式规整，硬件直接并行读取源寄存器堆中的 $R2$ 和 $R3$ 的内容，存入流水线寄存器（ID/EX 寄存器）。
3. 执行阶段（EX）：
   • 真正做加法！ALU 将输入的 $R2$ 和 $R3$ 直接相加： $\text{ALU\_Out} = R2 + R3$
   • 将计算结果锁存进流水线寄存器（EX/MEM 寄存器）。
4. 访存阶段（MEM）：
   • 空操作（NOP / 旁路透传）！
   • 因为这是纯算术指令，不访问任何数据 Cache，该阶段完全不消耗内存总线，ALU 的运算结果原封不动地直接传到下一个流水线寄存器（MEM/WB 寄存器）。
5. 写回阶段（WB）：
   • 控制信号打开通用寄存器堆的写使能。
   • 将经过 MEM 阶段传递过来的运算结果写入目的寄存器 $R1$。指令顺利结束！

指令二：RISC 纯存储指令 SW R1, 0(R2)（Store Word）#

语义：$\text{Mem}[R2 + 0] \leftarrow R1$（纯地址计算并写入内存，不修改通用寄存器）