计算机组成原理

计算机结构

计算机的经典结构是冯·诺依曼结构，它由五大部件组成：运算器、控制器、存储器、输入设备和输出设备。现代计算机结构通常包括中央处理器（CPU）、内存、存储设备、输入/输出设备以及连接这些设备的总线系统。

运算器

• 算数逻辑单元(ALU)：执行算数和逻辑运算
• 累加寄存器(AC)：通用寄存器，为ALU提供一个工作区，用在暂存数据
• 数据缓冲寄存器(DR)：读/写内存时，暂存指令或数据
• 状态条件寄存器(PSW)：存状态标志与控制标志
  • 软考中存在争议，也有将其归为控制器的

控制器

• 程序计数器(PC)：存储下一条要执行指令的地址
• 指令寄存器(IR)：存储正在执行的指令
• 指令译码器(ID)：对指令中的操作码字段进行分析解释
• 时序部件：产生时钟脉冲（Clock Pulse），为整个CPU提供基准时序信号

计算机体系结构分类-Flynn

SISD - 单指令流单数据流 (Single Instruction, Single Data)

• 描述：

  • 单指令流：在任何时钟周期，只有一个控制单元（CU）从内存中取出一条指令。
  • 单数据流：该指令在单个处理单元（PU）上操作一个数据流。

• 特点：

  • 这是最传统的串行计算机模型。
  • 一次执行一条指令，一条指令处理一个数据。

• 典型代表：

  • 早期的单核处理器（Intel 8086, 8051等）。
  • 简单的微控制器。
  • 冯·诺依曼体系结构是这种类型的典型体现。

    SIMD - 单指令流多数据流 (Single Instruction, Multiple Data)

• 描述：

  • 单指令流：一个控制单元（CU）从内存中取出一条指令。
  • 多数据流：该指令被广播到多个处理单元（PU） 上，所有处理单元同时执行同一条指令，但操作不同的数据。

• 特点：

  • 非常适合数据并行计算，即对大量数据执行相同的操作。
  • 极大地提高了图像处理、科学计算、机器学习等领域的计算效率。

• 典型代表：

  • GPU：图形处理器是SIMD架构最成功的现代范例，拥有成千上万个核心执行相同的着色器指令。
  • 向量处理器：如早期的Cray超级计算机。
  • 现代CPU的SIMD指令集：如Intel的 SSE、AVX 和 ARM的 NEON。这些指令允许一条指令同时对多个数据（如4个float）进行操作。

    MISD - 多指令流单数据流 (Multiple Instruction, Single Data)

• 描述：

  • 多指令流：多个控制单元（CU）同时取出多条不同的指令。
  • 单数据流：这些不同的指令被发送到多个处理单元（PU） 上，同时对同一份数据流进行操作。

• 特点：

  • 这种结构在现实中非常罕见，几乎没有商业化的成功应用。
  • 通常用于容错系统，例如多个处理器对同一份数据进行计算并投票表决结果，以确保可靠性。

• 典型代表：

  • 理论上存在，但缺乏广泛应用的实例。有时被误用于描述流水线处理器，但流水线本质上是时间上的SISD，而非空间上的MISD。

MIMD - 多指令流多数据流 (Multiple Instruction, Multiple Data)

• 描述：
  • 多指令流：多个控制单元（CU）独立地、异步地从内存中取出不同的指令。
  • 多数据流：多个处理单元（PU）独立地、异步地操作不同的数据。
• 特点：
  • 这是目前最主流、最通用的并行计算机架构。
  • 每个处理器都有自己独立的程序和控制单元，可以完全独立地执行任务。
  • 灵活性极高，既能处理数据并行任务，也能处理任务并行任务。
• 典型代表：
  • 多核处理器：你的笔记本电脑或手机里的Intel Core i7、AMD Ryzen、Apple M1芯片等都是MIMD架构。每个核心可以独立运行不同的程序和操作不同的数据。
  • 多处理器系统：服务器上多个CPU插槽的系统。
  • 计算机集群：通过网络连接的多台计算机，是规模最大的MIMD系统。

    总结与对比表格

分类	指令流	数据流	特点	应用场景	典型代表
SISD	单	单	串行执行	通用串行计算	单核CPU、微控制器
SIMD	单	多	数据并行	图形处理、科学计算、媒体编码	GPU、AVX/SSE指令集
MISD	多	单	理论模型，极少应用	容错系统	几乎无商用实例
MIMD	多	多	任务并行、数据并行	通用并行计算（主流）	多核CPU、分布式集群

现代架构的复杂性

需要注意的是，现代计算机架构通常是混合型的，而不是纯粹的某一种Flynn分类。例如：

• 一个 MIMD 的多核CPU（如8核CPU）。
• 每个核心内部是 SISD 的标量单元。
• 每个核心又包含了 SIMD 执行单元（如AVX512单元），可以并行处理多个数据。
  因此，Flynn分类法为我们提供了一个清晰的理论框架来理解和分析计算机架构，但在实际应用中，需要从不同层次去审视一个复杂的现代处理器。

指令

基本概念

一条指令通常由两部分组成：操作码与地址码

• 操作码：操作码指出了计算机要执行什么操作，如加法、减法、加载数据等
• 地址码：地址码包含操作数的地址以及操作结果的存放地址等，从其地址结构角度以下三种
  • 三地址指令
    • 格式：OP A, B, C
    • 含义：执行操作 A = B OP C，然后将结果存入 A。
    • 示例：ADD R1, R2, R3 // R1 = R2 + R3`
  • 二地址指令
    • 格式：OP A, B
    • 含义：执行操作 A = A OP B。其中一个源操作数同时也是存放结果的目的操作数。
    • 示例： ADD R1, R2   // R1 = R1 + R2
  • 一地址指令
    • 格式：OP A
    • 含义：通常隐含使用一个称为累加器的专用寄存器。操作通常为 ACC = ACC OP A。
    • 示例：LOAD A   // ACC = A (将A的值加载到累加器)
  • 零地址指令
    • 格式：OP
    • 含义：所有操作数都隐含地从一种称为堆栈的数据结构中获取。运算时从栈顶弹出操作数，运算后将结果压回栈顶。
    • 示例：PUSH A // 将操作数A压入堆栈

      总结对比

类型	格式	操作示例	优点	缺点	常见架构
三地址	OP A, B, C	A = B + C	直观，功能强	指令长	RISC (ARM, MIPS)
二地址	OP A, B	A = A + B	长度适中，常用	会覆盖源操作数	CISC (x86)
一地址	OP A	ACC = ACC + A	指令短	依赖累加器，效率低	早期计算机
零地址	OP	TOS = TOS + next(TOS)	指令极短，代码密度高	依赖堆栈，不直观	栈式机，虚拟机字节码

寻址方式

立即寻址

• 操作数位置：操作数本身直接包含在指令中，紧跟在操作码之后。

• 特点：

  • 取指令时，操作数也跟着被取出，无需再次访问内存来取操作数，执行速度最快
  • 操作数的值是指令的一部分，不能修改

• 应用：主要用于给寄存器赋常数。

• 示意图：

  指令： [操作码] [立即数 5]
                         ↓
                      操作数 = 5

  直接寻址

• 操作数位置：指令中直接给出操作数在内存中的有效地址。

• 特点：

  • 执行指令时需要再次访问内存（一次取指令，一次取数据）来获取操作数，速度较慢。
  • 地址字段的长度决定了可寻址的内存范围。

• 应用：访问单一的、固定的全局变量。

• 示意图：

  指令： [操作码] [地址 1064H]
                         ↓
                      内存[1064H] → 操作数

  间接寻址

• 操作数位置：指令中存放一个地址，这个地址对应的内容是操作数的地址，指令中的地址是操作数地址的地址指针

• 特点：

  • 执行指令时需要多次访问内存（一次取指令，一次取地址，一次取数据）来获取操作数

• 应用：实现指针和引用

• 示意图：

  指令： [操作码] [地址 1064H]
  					↓
  				内存[1064H]	
  					↓
  				内存[2084H]	→ 操作数

寄存器寻址

• 操作数位置：操作数存放在CPU内部的寄存器中，指令中直接给出寄存器名。

• 特点：

  • 无需访问内存，执行速度极快。
  • 指令长度非常短，因为只需要很少的位来编码寄存器号。

• 应用：最常用的寻址方式，用于中间计算和临时变量的存储。

• 示意图：

  指令： [操作码] [寄存器 BX]
                         ↓
                      寄存器BX → 操作数

  寄存器间接寻址

• 操作数位置：操作数在内存中，但其有效地址存放在某个寄存器里。

• 特点：

  • 类似于C语言中的指针。寄存器里存的是一个地址，而不是数据本身。
  • 比直接寻址更灵活，因为可以通过改变寄存器的值来访问不同的内存单元。

• 应用：访问数组元素、传递函数参数的地址（引用传递）。

• 示意图：

  指令： [操作码] [寄存器 BX]
                         ↓
                      寄存器BX → 地址值
                         ↓
                      内存[地址值] → 操作数

CISC与RISC

根据指令系统的类型进行分类，可以将计算机分为复杂指令集计算机（CISC）与精简指令集计算机（RISC）

指令系统类型	指令	寻址方式	实现方式	其他
CISCS（复杂）	数量多，使用频率差别大，可变长格式	支持多种	微程序控制技术	研制周期长
RICS（精简）	数量少，使用频率接近，定长格式， 大部分为单周期指令，操作寄存器， 只有Load/Store操作内存	支持方式少	增加通用寄存器； 硬布线逻辑控制为主 适合流水线操作	优化编译 有效支持高级语言

层次化存储结构

计算机系统的理想存储器应该具备三大特性：速度快、容量大、成本低。然而，现有的硬件技术无法同时满足这三个目标：

• 速度越快的存储器，每位成本越高，因此容量难以做大。
• 容量越大的存储器，若要保证速度，则成本极高。
  为了解决这个矛盾，计算机科学家们提出了层次化存储结构。其基本思想是：

  将不同容量、不同速度、不同成本的多种存储器有机地组织在一起，使得从系统角度看，存储系统似乎拥有接近最快存储器的速度，同时又有接近最慢、最大存储器的容量和平均成本。

  存储层次金字塔

![[file-20260321135833.excalidraw]]

Cache

概念

Cache（高速缓存）是位于CPU和主内存之间的高速存储器，其作用是存放最常用的主内存数据副本，以解决CPU与主内存之间的速度差距。
在计算机的存储体系中中，除寄存器外Cache是访问最快的层次，使用Cacheg改善系统性能的依据是程序的局部性原理

如果以h代表对Cache的访问命中率，t表示Cache的周期时间，$t_2$ 表示主存储器周期时间，以读操作为例，使用”Cache+主存储器”的系统的平均周期为$t_3$ 则
$$t_3 = h \times t_1 + (1-h) \times t_2$$

其中$（1-h）$ 又称为失效率（未命中率）

Cache-映像

映像解决的就是一个核心问题：主内存中的某个数据块，可以被放置到Cache中的哪个位置？
Cache的容量远小于主内存，因此需要一套规则来建立两者地址之间的对应关系。主要有三种基本的映像方式：

直接相联映像

• 规则：主内存中的每一块数据只能被放置到Cache中唯一的一个特定位置。

• 地址结构：主内存地址被划分为三部分：

  • 标记：用于区分被映射到同一个Cache行的不同内存块。
  • 索引：直接指出这个内存块在Cache中的行号（相当于Cache的地址）。
  • 块内偏移：指出要访问的数据在该数据块内的具体位置。

• 工作流程：

  1. CPU给出内存地址。
  2. 用索引位找到Cache中对应的唯一一行。
  3. 比较该行中的标记位与内存地址中的标记位是否一致。
  4. 如果一致且有效位为1，则命中，再根据块内偏移取出数据。
  5. 如果不一致，则缺失，需要从主内存中调入整个数据块，并替换掉当前Cache行中的旧数据，同时更新标记位。

• 优点：

  • 硬件电路简单，查找速度快。因为每个地址在Cache中的位置是唯一的，不需要复杂的搜索算法。

• 缺点：

  • 冲突失效高。如果两个频繁访问的数据块恰好被映射到同一个Cache行，它们会互相驱逐对方，导致Cache频繁刷新，命中率急剧下降。这是最致命的缺点。

• 比喻：一个多层的停车场，每层只有一个车位（Cache行）。你的车（数据块）只能停在与你家楼层号（索引）相同的特定层。如果那层停了别人的车，你就没法停，必须把别人的车开走。

  全相联映像

• 规则：主内存中的任何一块数据可以被放置到Cache中的任意一个位置。

• 地址结构：主内存地址被划分为两部分：

  • 标记：唯一标识一个内存块。因为块可以放在任何位置，所以需要完整的地址信息作为标记。
  • 块内偏移：指出要访问的数据在该数据块内的具体位置。
  • （没有索引位）

• 工作流程：

  1. CPU给出内存地址。
  2. 需要将地址中的标记与Cache中所有行的标记同时进行比较（使用一种称为“相联存储器”的硬件，可以并行比较）。
  3. 如果找到一致的标记且有效位为1，则命中，再根据块内偏移取出数据。
  4. 如果所有行都不匹配，则缺失。此时需要从主内存调入数据，并替换掉Cache中的某一行（根据替换算法，如LRU），同时更新标记。

• 优点：

  • 冲突失效最低，Cache的空间利用率最高。只要Cache还有空位，就不会发生冲突。

• 缺点：

  • 硬件成本高、速度慢。因为需要与所有Cache行的标记进行比较，电路非常复杂，随着Cache容量增大，比较器的成本和延迟会变得难以接受。通常只用于小容量的Cache，如TLB。

• 比喻：一个单层的停车场，有很多空车位（Cache行）。你的车（数据块）可以停在任何空位上。找车时，需要逐个车位查看车牌号（标记）是不是你的。

  组相联映像

• 规则：这是直接相联和全相联的一种折中方案，也是现代CPU中最常用的方式。

  • 将Cache分成若干个大组。
  • 每个组内包含多个行（n行，称为 n路组相联）。
  • 主内存中的每一块数据可以被映射到唯一的一个组中，但可以放入这个组内的任意一行。

• 地址结构：主内存地址被划分为三部分：

  • 标记：用于区分被映射到同一个组内的不同内存块。
  • 组索引：指出这个内存块属于Cache中的哪个组。
  • 块内偏移：指出要访问的数据在该数据块内的具体位置。

• 工作流程：

  1. CPU给出内存地址。
  2. 用组索引位找到Cache中对应的唯一一个组。
  3. 将这个组内的所有行的标记与内存地址中的标记进行比较（相当于在这个小组内进行全相联查找）。
  4. 如果在该组中找到一致的标记且有效位为1，则命中，再根据块内偏移取出数据。
  5. 如果该组内没有匹配的行，则缺失。需要从主内存调入数据，替换掉该组内的某一行（根据替换算法，如LRU），同时更新标记。

• 优点：

  • 有效降低了直接相联的冲突问题。
  • 相比全相联，硬件实现更简单（只需要比较一个组内的几路，而不是全部），速度更快。

• 缺点：

  • 比直接相联稍复杂。

• 常见配置：

  • 2路、4路、8路、16路组相联最为常见。
  • 极端情况：如果组数=1，就是全相联；如果每组只有1行，就是直接相联。

• 比喻：一个多层的停车场，每层有n个车位（n路组相联）。你的车（数据块）必须停在与你家楼层号（组索引）相同的那一层，但可以在该层任意选择一个空位停。找车时，只需在自己那层逐个车位查看车牌号（标记）即可。

  总结对比

特性	直接相联	全相联	组相联（n路）
映射规则	一对一	多对多	一对一组内多对多
冲突失效	最高	最低	中等（介于两者之间）
硬件复杂性	最简单	最复杂	中等（与n有关）
查找速度	最快	最慢	快（只需比较n个标记）
成本	最低	最高	中等
应用	早期CPU，对速度要求极严苛的场景	小容量特殊Cache（如TLB）	现代CPU通用Cache的主流方案
结论：组相联映像在命中率和硬件成本之间取得了最佳平衡，因此被广泛应用于现代计算机的L1、L2、L3 Cache设计中。

主存-编址与计算

• 按字编址
  • 含义：每个内存地址对应一个“字”（Word）的存储空间。“字长”取决于机器，如32位机器的字是4字节，64位机器的字是8字节。
  • 缺点：不灵活，如果只需要访问一个字节，也必须读写整个字。现代通用计算机已很少采用纯字编址。
• 按字节编址
  • 含义：每个内存地址对应一个字节（8位）的存储空间，现代计算机的绝对主流方式
  • 优点：可以精细地访问任何一个字节，非常灵活，特别适合处理字符数据。

根据存储器所要求的容量和选定存储芯片的容量，就可以计算出所需要的芯片总数，即：
$$总片数 = 总容量 \div 每片容量$$
例：若内存地址区间为4000H~43FFH，每个存储单元可存储16位二进制数，该内存区域用4片存储芯片构成，则构成该内存所用的存储芯片的容量是多少？
内存地区区间是400H~43FFH，计算该区间的存储单元数量：$43FFH - 4000H + 1 = 400H = 1024(十进制)$ 个存储单元
每个存储单元可存储16位二进制数，因此总存储容量为$1024 \times 16 = 16384 位$
该内存区域由4片存储芯片组成，因此每片芯片的容量为$16384 \div 4 = 4096位$

总线

一条总线同一时刻仅允许一个设备发送，但允许多个设备接收

总线的分类

• 数据总线（Data Bus）：在CPU与RAM之间来回传送需要处理或需要存储的数据。
• 地址总线（Address Bus）：用来指定在RAM之中存储的数据的地址。
• 控制总线（Control Bus）：将微处理器控制单元（Control Unit）的信号传送到周边设备，一般常见的为USB Bus和1394 Bus。

串联系统与并联系统

串联系统

![[file-202603251418271827.excalidraw|800]]

系统可靠性 $R = R1 \times R2 \times … \times R_n$
系统故障率 $\lambda = \lambda_1 + \lambda_2 + … + \lambda_n$

并联系统

![[file-202603251419241924.excalidraw|600]]

系统可靠性 $R = 1 - (1-R_1) \times (1-R_2) \times … \times (1-R_n)$

推导过程：
假设一个并联系统由 n 个独立的组件组成，每个组件的可靠性（正常工作的概率）分别为 R1,R2,…,Rn​。每个组件的不可靠性（失效的概率）则为 $Fi=1−Ri$​。
由于系统失效需要所有组件同时失效，这个事件的概率是各组件不可靠性的乘积：
$Fs=F1×F2×…×Fn=(1−R1)×(1−R2)×…×(1−Rn)$
那么，系统的可靠性 RsRs​ 就是系统不失效的概率，即用 1 减去所有组件都失效的概率：
$R=1−Fs=1−[(1−R1)×(1−R2)×…×(1−Rn)]$

N模混合系统

![[file-20260325142004204.excalidraw | 800]]

将混合系统分解为基本的串联和并联子系统，分别计算每个子系统的系统可靠性
可靠性 $R=R\times(1-(1-R)^3)\times(1-(1-R)^2)$

校验码

校验码是在原始数据（信息位）的基础上，附加一些额外的冗余码（校验位）而组成的一种编码，通过增加冗余信息，使合法的编码符合某种特定的规律（如奇偶性、能被某个数整除等）。如果接收到的编码不符合这个规律，就表明发生了错误。

目的与作用

• 错误检测：发现数据在传输或存储过程中是否发生了错误（如比特翻转）。
• 错误纠正：不仅发现错误，还能自动纠正错误，恢复原始数据。
• 提高系统可靠性：是保证数据完整性的关键技术，广泛应用于内存、网络通信、磁盘存储等领域。

  码距

  码距是理解和衡量校验码能力的根本性概念，也称为海明距离，码距是指一个编码系统中，任意两个合法编码之间对应位不同的最小位数。
  可以把所有合法编码想象成一个多维空间中的点。码距就是这些点之间的最小距离。

码距与校验能力的关系

码距的大小直接决定了一种编码的检错和纠错能力，它们的关系如下：

1. 码距 ≥ 1：是合法编码的基本要求（否则所有编码都一样）。
2. 码距 ≥ 2：具有1位检错能力。
   • _原因_：任何一位发生错误，都会变成一个非法编码（因为没有任何一个合法编码与它相差1位）。例如，合法编码是 00 和 11（码距=2）。如果 00 出错变为 01，01 既不是 00 也不是 11，所以能被检测出错误。
3. 码距 ≥ 3：具有1位纠错能力，或2位检错能力。
   • _纠错原因_：任何一位发生错误后产生的非法编码，只唯一接近原来的那个合法编码。例如，合法编码是 000 和 111（码距=3）。如果收到 001，我们知道它最可能是 000 出错了一位（而不是 111 错了两位），从而可以纠正为 000。
   • _检错原因_：有两位出错时，编码会变得更像另一个错误编码，可能无法正确纠错，但通常仍能被检测为非法编码。
4. 码距 ≥ 4：具有1位纠错 + 1位检错能力，或2位纠错能力，或3位检错能力。
   • _原因_：设计上更加安全，纠错后如果还有一位错误，依然能被发现。
     这个关系可以总结为一个通用的公式：

• 要检测 e 位错误，需满足：码距 ≥ e + 1
• 要纠正 t 位错误，需满足：码距 ≥ 2t + 1
• 要同时检测 e 位错误并纠正 t 位错误（通常 e > t），需满足：码距 ≥ t + e + 1

奇偶校验

奇偶校验的核心思想是：通过增加一个额外的校验位，使整个二进制编码中“1”的个数为奇数或偶数。

• 奇校验：确保整个编码中“1”的个数为奇数。
• 偶校验：确保整个编码中“1”的个数为偶数。
  这个“整个编码”包括原始数据位和附加的校验位。
  奇偶校验可以检查1位的错误，不可纠错。

循环校验码-CRC

CRC 的核心思想是：将数据位串看作一个多项式（的系数），并通过一个预先约定的“生成多项式”对其进行模2除法运算，将得到的余数作为校验码（CRC码）附加在原始数据后面。接收方使用同样的生成多项式对收到的数据进行同样的计算。如果计算结果与收到的CRC码不符，则表明传输过程中发生了错误。

模2运算

CRC的所有计算都是基于模2运算（在GF(2)域，即伽罗华域），这是一种二进制算法，没有进位和借位。其规则非常简单：

• 模2加法：0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0 (等价于异或运算)
• 模2减法：0 - 0 = 0, 0 - 1 = 1, 1 - 0 = 1, 1 - 1 = 0 (同样等价于异或运算)
• 因此，在CRC中，加法和减法本质上是相同的操作。
• 模2乘法：与普通乘法类似，但按模2加法求和。
• 模2除法：与普通除法类似，但使用模2减法（即异或操作）。
  异或操作：如果两个相应的二进制位不同，则结果为1，否则为0

发送端

假设原始数据为 11001010101，生成多项式为 $G(x) = x^4 + x^3 + x + 1$，如何得到发送的数据

• 原始数据 11001010101 可以表示为多项式：$M(_x) = 1\times x^5 + 0 \times x^4 + 1 \times x^3 + 0 \times x^2 + 0 \times x^1 + 1 \times x^0 = x^5 + x^3 + 1$
• 生成多项式$G(x) = x^4 + x^3 + x + 1$ 其二进制表现形式为 11011，它的最高次幂是 4，这意味着最终产生的 CRC校验码将是4位
• 在原始数据 11001010101 的末尾添加 r 个 “0”，其中 r 是生成多项式的最高次幂（这里是3）。得到新的数据：110010101010000
• 执行模2除法，使用110010101010000 作为被除数，用生成多项式 11011 作为除数，进行模2除法

         —————————————————
  11011 ) 110010101010000
  	 11011
  	 —————————————————
  	    10010
  	    11011
  	    —————————————————
  	     10011
  	     11011
  	    —————————————————
  	       10000
  	       11011
  	       —————————————————
  	        10111
  	        11011
  	        —————————————————
  	         11000
  	         11011
  	         —————————————————
  	             11000
  	             11011
  	            —————————————————
  	                11   <- 余数

• 将模2的余数补足校验码的位数0011并附加到原始数据的后面，最终发送的数据为110010101010011

接收端

接收端接收到110010101010011后，进行相同的操作

• 用同样的方式生成多项式11011，去除接收到的数据
• 如果传输没有错误，模2除法的余数应为 0
• 如果余数不为 0，则表明传输过程中肯定发生了错误

海明校验码

海明校验码既可以检错，也可以纠错
海明校验码的原理是：在有效的信息位中加入几个校验位形成海明码，使码距比较均匀的拉大，并把海明码的每个二进制位分配到几个奇偶校验码组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据。

$$
2^r >= m + r + 1
$$
r：校验位的个数
m：数据位的个数