计算机系统结构

第一章

阿姆达尔定律（Amdahl’s Law）

$$ S_{n}=\frac{T_{0}}{T_{n}}=\frac{1}{(1-F e)+\frac{F e}{S e}} $$

公式的推导逻辑是：

1. 任务中不可优化部分的执行时间：$T_0 \times (1-Fe)$

2. 任务中可优化部分优化后的执行时间：$T_0 \times Fe / Se$

3. 优化后的总执行时间：$T_n = T_0(1-Fe) + \frac{T_0 Fe}{Se}$

4. 加速比：$S_n = \frac{T_0}{T_n} = \frac{1}{(1-Fe) + \frac{Fe}{Se}}$

这个定律揭示了一个重要的工程规律：系统的整体加速比受限于不可优化部分。即使可优化部分的加速比$Se$趋近于无穷大，系统整体加速比的上限也只是$\frac{1}{1-Fe}$。 $$ CPU时间 = \text{IC} \times \text{CPI} \times \text{时钟周期时间} \ = \sum_{i=1}^{n} (\text{CPI}_i \times \text{IC}i) \times \text{时钟周期时间} \[1em] \text{CPI} = \frac{\text{时钟周期数}}{\text{IC}} = \frac{\sum{i=1}^{n} (\text{CPI}_i \times \text{IC}i)}{\text{IC}} = \sum{i=1}^{n} \left( \text{CPI}_i \times \frac{\text{IC}_i}{\text{IC}} \right) \[1em] \text{MIPS速率} = \frac{f}{\text{CPI} \times 10^6} $$ CPU 时间：程序实际执行花费的总时间（秒）

IC (Instruction Count)：指令总数，程序一共执行多少条指令

CPI (Cycles Per Instruction)：每条指令平均时钟周期数

时钟周期时间：一个时钟周期持续的时间（秒）

时钟周期数：程序执行总共用了多少个时钟周期

f：CPU 主频 / 时钟频率（Hz）

MIPS 速率：每秒执行多少百万条指令

i：指令类型编号（如加法、乘法、访存等）

n：指令类型总数

CPIᵢ：第 i 种指令的 CPI

ICᵢ：第 i 种指令的执行条数

第二章

MIPS（Microprocessor without interlocked pipelined stages）:这个和第一章缩写一样，但是不是一个东西，是一种RISC处理器架构。

哈夫曼编码（Huffman Coding）

• 核心思想：按频率分配变长码，高频指令用短码、低频用长码，保证前缀性质（任一码字不是其他码字的前缀）。

扩展操作码

指令操作码不等长，短码给高频指令，长码给低频指令；

例子： ① 2 - 7 扩展操作码

数字含义：

• 第一个数 2：短指令最多 2 条
• 第二个数 7：长指令最多 7 条

② 3 - 3 - 3 扩展操作码

三个 3 依次代表三层：

• 第 1 个3：2 位短指令层，预留 3 个码做扩展
• 第 2 个3：4 位中指令层，预留 3 个码做扩展
• 第 3 个3：6 位长指令层，不再扩展

第三章

流水线

第一种流水线时空图：格子里填数字 i，代表第 i 条指令 / 第 i 次运算在对应时间、对应流水段执行，用来直观看指令重叠、冲突、吞吐率。

第二种流水线时空图：时空图方框里面是MIPS流水段指令，主要就是 IF ID EX MEM WB

IF：Instruction Fetch 取指段 从指令存储器中取出当前指令

ID：Instruction Decode 译码 / 取数段 解析指令 + 从寄存器堆读源操作数

EX：Execute 执行 / 运算段 ALU 进行运算、地址计算、分支比较

MEM：Memory 访存段 访问数据存储器

WB：Write Back 写回段 把运算 / 访存结果写回寄存器堆

STALL：因为数据冒险、控制冒险，当前指令不能继续往下走，空出一个周期。

下面是常用公式： $$ % 流水线四大性能指标公式 总执行时间

T_k = (k + n - 1)\Delta t \

吞吐量（单位时间完成指令数）

TP = \frac{完成运算数}{总执行时间} = \frac{n}{(k + n - 1)\Delta t} \

最大吞吐量

TP_{\text{max}} = \frac{1}{\Delta t} \

流水线效率

E =\frac{串行时间运算次数}{段数总执行时间} =\frac{n}{k + n - 1} \

加速比

S = \frac{nk}{k + n - 1},\quad S_{\text{max}} = k \ $$ k：流水线段数（MIPS 5 级流水 k=5）

n：任务 / 指令条数

Δt：流水线每段时钟周期（时钟周期 T=Δt）

Tk：流水线执行 n 条指令总时间

T0：非流水线顺序执行总时间

对于不等长时钟周期还有一个公式，核心是第一条走完要所有段，后面每条只占一个时钟周期 $$ T_k = \sum_{i=1}^k \Delta t_i + (n-1)T_{max} $$

第五章

标量流水处理机：就是之前学的每条指令分多段（取指 / 译码 / 执行 / 写回），每周期仅发射 1 条指令，流水线深度固定。

超标量处理机（Superscalar）：复制多套流水线与执行单元（ALU、访存端口），每周期动态发射多条独立指令。

超长指令字处理机（VLIW，Very Long Instruction Word）：编译器在编译期静态挖掘并行性，将多条无依赖指令打包成一条超长指令（数百位），含多个独立操作字段。

超流水线处理机（Superpipeline）：将标量流水线的每一级再细分为更小的子阶段（如 4 级→8/16 级），缩短周期（原周期 Δt→Δt/m，m 为流水度）。

重要参数ILP（Instruction-Level Parallelism），指令级并行：

超标量：ILP套流水线 并行挖

VLIW：一条长指令内含 ILP个操作 即EX

超流水线：拆分流水级、单周期吞吐 ILP条

第六章

GCD 循环依赖：

1. 规范化循环：确保循环索引从 1 开始，步长为 1

2. 提取数组下标表达式：对于两个数组引用，分别提取系数 a, b 和 c, d（写操作 a, b 读操作c, d）

3. 计算最大公约数：计算 g = GCD(a, c)

4. 判断整除性：检查 (d - b) 是否能被 g 整除：（d-b）% gcd(c, a) == 0

   • 如果不能整除：一定没有循环携带依赖

   • 如果能整除：可能存在循环携带依赖，需要进一步测试（如 Banerjee 不等式、Omega 测试等）

第七章

cache

复习计组三种形态：

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

见八股文.md文件

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#### 全相联映射

相当于随机存储，只要cache没满就往里面存，但是需要并行比较导致电路复杂，一多了设计难度就炸了。

主存地址 = 块号(s) + 块内字节号(w位) 

#### 直接映射方式

相当于分组，给主存按照每r行分为一组，然后每组的第i块只能存在cache的第i行中。

主存地址 = 组号 (s-r)+ 组内号数(r) + 块内字节号(w)

此时第i行的cache存的就是每组主存第i块的内容，可以省略cache中对于行数的存储

#### 组相联映射方式

是全相联和直接映射的折中。Cache被分成若干个**组**，每个组内包含多个**块**。

**映射规则**：主存中的一个块可以映射到**指定组**内的**任意一个空闲块**。

命名：cache每组行数v时，我们通常称这种方式为**v路组相联映射**，v通常为2、4、8、16。

对于主存每$2^v$分成一组，对于每个组中的第i块，可以存到cache中第i组的任意一行。

d = log2(cache组数)

主存地址=主存组号（s-d）+ 组内块号（d）+块内字节号（w）

#### 举例

我们以一个地址线为16的64KB主存为例。其地址形如`1001 0000 0000 0001`，字长为`1B`，假设块大小为`16B`。（由此我们可以理解一点：cache中存的不是一个主存地址的内容，而是主存中相邻的几个内容组成的一个块。进一步，我们可以知道，在此例子下，一个块有16个，对应着4位二进制，所以主存的后四位**对于命中cache的判断就没有用了**，只是用来确定块内偏移的。）

1. **全相联映射**：这种情况，主存的前12位就是用来定位cache的tag，每次cpu访问的时候和tag进行比较。

2. **直接映射**：这种情况与cache的行数有关，假如cache一共有32行，那么主存就是每32块视作一组。每一组的第i块，对应着cache的第i行。

   ~~64KB / 16B = 4K，可以求出主存有4K块。4K / 32 = 128，可以求出每一行cache被128行主存抢着用(我们可以视作把主存划分成128坨，但不能叫组，为了和下一种方式区分开)，log2(128) = 7~~。log2(32) = 5，定位cache的行需要5位。剩下的12 - 5 = 7 ，所以主存的地址就是 `7(tag) + 5(index) + 4(offset)`。

3. **组相联映射**：依旧和cache有关，我们假设cache有32行，设每组有4行，一共有32 / 4 = 8组。log2(8) = 3，需要3位来定位是哪一组cache。剩下的 12 - 3 = 9 位作为tag，用于和这一组的4行并行比较，判断是否命中缓存。所以主存的地址就是`9(tag) + 3(set index) + 4(offset)`

> [!WARNING]
>
> 直接映射中删除线部分求出log2(128) = 7来表示tag当且仅当主存填满地址空间时结果与减出来的结果一致，所以用地址线数减去 index和 offset 更加稳妥。tag就是剩下多少位都用作tag，就算超了也是未命中，没有任何风险。

写策略：

• 写直达法：不仅写入Cache，也写入下一级存储器。
• 写回法：只写入Cache，不写入下一级存储器，设置修改位，仅当Cache中相应的块被替换时，才写回主存，当一个块被替换时，若没有被修改过，则不必写回到下一级存储器

当发生写不命中时，是否需要调入相应的块：

按写分配（Write Allocate）（写时取）：写不命中时，先把所写单元所在的块调入Cache，再进行写入。

不按写分配（No-Write Allocate）（绕写法）：写不命中时，直接写入下一级存储器而不调块入Cache。

第八章

RAID

1. RAID 0（条带阵列，无冗余）

• 原理：数据分块并行分散到所有磁盘，纯条带化，无校验/备份
• 盘数：≥2块
• 容量：所有硬盘容量总和
• 性能：读写速度全系最高，IO并行优势极强
• 容错：零容错，任意一块盘损坏，全部数据丢失
• 适用：临时高速存储、非重要数据，严禁存核心资料

2. RAID 1（镜像阵列，全冗余）

• 原理：磁盘两两完全镜像，数据双向同步备份
• 盘数：≥2块（标准2块）
• 容量：仅等于单块硬盘容量（一半空间用于镜像备份）
• 性能：读速度快（双盘并行读），写略有损耗（双盘同步写入）
• 容错：单盘绝对容错，任意一块盘故障不丢数据
• 适用：系统盘、核心机密数据、高可靠低容量场景

3. RAID 2（位级条带+汉明校验，已淘汰）

• 原理：按比特位拆分数据，搭配多块专用校验盘做错误纠错
• 盘数：需多块数据盘+多校验盘，架构复杂
• 特点：早期技术、成本极高、硬件依赖强，目前彻底淘汰，无商用场景

4. RAID 3（字节条带+独立校验盘，小众淘汰）

• 原理：数据按字节条带分布，单独一块固定校验盘存奇偶校验
• 盘数：≥3块（N数据盘+1校验盘）
• 容量：(总盘数−1)×单盘容量
• 性能：连续读写强，随机读写极差，校验盘成为性能瓶颈
• 容错：仅容忍单盘故障
• 现状：基本被RAID5替代，极少使用

补充：RAID3 只支持整组读写，也数据一次性必须写N个数据盘

5. RAID 4（块条带+独立校验盘，基本弃用）

• 原理：数据按数据块条带，同RAID3，校验盘独立固定
• 盘数：≥3块
• 容量：(总盘数−1)×单盘容量
• 致命缺陷：所有写入操作争抢同一校验盘，IO瓶颈严重
• 容错：单盘容错
• 现状：商用几乎绝迹

6. RAID 5（分布式奇偶校验，主流通用）

• 原理：数据块条带化，奇偶校验码分散在所有磁盘，无独立校验盘
• 盘数：≥3块
• 容量：(总盘数−1)×单盘容量
• 性能：读写均衡，随机IO表现优秀；硬盘故障后重建开销大
• 容错：仅支持任意单盘故障，第二块盘损坏则数据丢失
• 适用：企业文件存储、普通业务数据，最经典通用型RAID

7. RAID 6（双分布式奇偶校验，高容错）

• 原理：搭载两套独立奇偶校验，校验信息分布式存储
• 盘数：≥4块
• 容量：(总盘数−2)×单盘容量
• 性能：读性能接近RAID5，写性能偏弱（双重校验计算开销大）
• 容错：全系常规RAID里容错最强，可同时容忍两块硬盘故障
• 适用：大容量硬盘阵列、长期运行、高可靠性要求场景

8. RAID 10（RAID1+RAID0 镜像条带，高性能高可靠）

• 原理：先做RAID1镜像组，再对镜像组做RAID0条带（先镜像、后条带，区别于RAID01）
• 盘数：≥4块，必须为偶数盘
• 容量：(总盘数÷2)×单盘容量
• 性能：继承RAID0高速+RAID1稳定，读写性能优异，高IO首选
• 容错：同一镜像组内单盘损坏无影响；不同镜像组可同时坏多块盘，仅同一镜像对双盘同时损坏才丢数据
• 成本：硬件成本高
• 适用：数据库、虚拟化、核心业务等高IO+高可靠场景

还需要会画系统的可靠性框图

第九章

互联函数

互连函数是用于描述互连网络中输入端号与输出端号之间连接关系的数学表达式。在拥有 $N$ 个输入端和 $N$ 个输出端的网络中，互连函数 $f(x)$ 表示输入端 $x$ 连接到输出端 $f(x)$。

1. 交换函数（Exchange/Cube Function）

• 定义：对 n 位二进制地址的第 k 位单独取反，其余所有位保持不变。。
• 表达式：$Cube_k(x_{n-1}\dots x_k\dots x_0) = x_{n-1}\dots \bar{x}_k\dots x_0$。
• 特点：常用于构造立方体网络。当 $N=8$ 时，有 $Cube_0$、$Cube_1$、$Cube_2$ 三种。（补充一下，这个N请看开头的输入端输出端定义，所以就是3个二进制可以表示十进制8）

2. 均匀洗牌函数（Shuffle Function）

• 定义：将输入端的二进制编号循环左移一位。
• 表达式：$\sigma(x_{n-1}x_{n-2}\dots x_1x_0) = x_{n-2}\dots x_1x_0x_{n-1}$。
• 逆洗牌函数：$\sigma^{-1}$ 为循环右移一位。
• 应用：Omega 网络级间互连采用均匀洗牌连接方式。

3. 蝶式函数（Butterfly Function）

• 定义：将输入端二进制编号的最高位与最低位互换位置。
• 表达式：$\beta(x_{n-1}x_{n-2}\dots x_1x_0) = x_0x_{n-2}\dots x_1x_{n-1}$。

4. 反位序函数（Bit-reversal Function）

• 定义：将输入端二进制编号的位序完全颠倒。
• 表达式：$\rho(x_{n-1}x_{n-2}\dots x_1x_0) = x_0x_1\dots x_{n-2}x_{n-1}$。

5. PM2I 函数（Plus-Minus $2^i$ Function） 又被叫做移数网络

• 定义：一种移数函数，将输入端号加或减 $2^i$ 后取模 $N$。

• 表达式：

  • $PM2_{+i}(x) = (x + 2^i) \pmod N$
  • $PM2_{-i}(x) = (x - 2^i) \pmod N$

• 范围：$0 \le i \le n-1$，$n = \log_2 N$。

互连网络（Interconnection Network）的主要特性参数用于描述其拓扑结构和性能表现。根据源文件，这些参数主要分为结构参数和性能指标两大类：

一、 结构参数 这些参数主要从图论的角度描述网络的物理布局：

• 网络规模 ($N$)：指互连网络中结点的个数。它代表了该网络所能连接的部件（如处理器、存储模块等）的数量。
• 结点度 ($d$)：指与结点相连接的边数（通道数）。具体分为入度（进入结点的边数）和出度（从结点出来的边数）。
• 距离：指网络中任意两个结点之间通信时需要跨越的最少边数。
• 网络直径 ($D$)：指网络中任意两个结点之间距离的最大值。网络设计中通常希望直径越小越好，以减少通信延迟。
• 等分宽度 ($b$)：指将拥有 $N$ 个结点的网络切成结点数相同的两半时，在各种切法中沿切口边数的最小值。对应的线等分宽度 $B = b \times w$（$w$ 为通道宽度）。
• 对称性：指从网络中任何一个结点看去，其拓扑结构都是相同的。对称网络在实现和编程上通常更加容易。

2^n = N

混洗交换网：直径 2n-1 节点度2

移数网络：直径 n/2 节点度 2n-1