第一章

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

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

符号 含义
Sn 整体系统加速比：优化后系统性能与优化前的比值，也等于优化前执行时间与优化后执行时间的比值
T0 优化前的执行时间：没有任何优化措施时，完成整个任务需要的时间
Tn 优化后的执行时间：对部分组件进行优化后，完成整个任务需要的时间
Fe 可优化部分的占比：任务中可以被优化 / 加速的部分，占原始执行时间的比例（取值范围：0≤Fe≤1）
Se 可优化部分的加速比：优化措施给可优化部分带来的性能提升倍数（例如，优化后这部分运行速度是原来的 3 倍，则Se=3）

公式的推导逻辑是：

  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 位长指令层，不再扩展
指令 使用频度 哈弗曼编码1 哈弗曼编码2 3-3-3扩展编码 2-7扩展编码
ADD 0.43 0 0 00 00
CLA 0.22 10 100 01 01
SUB 0.13 110 101 10 1000
JMP 0.07 11100 1100 1100 1001
JOM 0.06 11101 1101 1101 1010
STO 0.05 11110 1110 1110 1011
CIL 0.02 111110 11110 111100 1100
SHR 0.01 1111110 111110 111101 1101
STP 0.01 1111111 111111 111110 1110

第三章

流水线

第一种流水线时空图：格子里填数字 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 测试等）

依赖类型 读写顺序 本质 是否可消除 对并行化的影响 典型例子
流依赖（真依赖，RAW） 先写后读 数据的 “生产 - 消费” 关系，后序语句依赖前序语句产生的数据 不可消除（硬依赖） 最大，必须严格保证顺序 循环无关：c[i]=2*c[i-1]; b[i+1]=c[i]+d[i];循环携带：c[i]=2*c[i-1];（第i次读依赖第i-1次写）
反依赖（WAR） 先读后写 避免后序写操作覆盖前序读操作需要的值 可通过变量重命名消除（伪依赖） 中等，消除后可并行 c a = b + c; // 先读b b = d + e; // 后写b 重命名后：a = b + c; b_new = d + e;
输出依赖（WAW） 先写后写 保证最终内存值是最后一个写操作的结果 可通过变量重命名消除（伪依赖） 中等，消除后可并行 c a = 1; // 先写a a = 2; // 后写a 重命名后：a1=1; a2=2;