计组笔记

功夫再高，也怕挂科。

有时间还是把视频看一遍为好，UP 主讲得挺好的。

第一章 概述

CPU 主要由运算器和控制器组成。
高速缓存 cache 采用 SRAM，内存采用 DRAM。
MIPS 和 ARM 都属于 RISC（Reduced Instruction Set Computer），x86 属于 CISC（Complex Instruction Set Computer）。
Amdahl 定律：$t_{new} = t_{related}/S + t_{unrelated}$，$S$ 为加速比。

时钟周期数 = 指令数 x 平均每条指令所需周期数（即 cycles = IC x CPI）
CPU 执行时间 = 指令数 x CPI x 时钟周期长（即 CPUtimes = IC x CPI x T）
或 CPUtimes = IC x CPI / f

能耗 = 负载电容 x 电压^2 = $CU^2$
功耗 = 1/2 x 负载电容 x 电压^2 x 开关频率 = $\frac12 CU^2 f$

七个伟大思想：使用抽象简化设计、加速大概率事件、通过并行提高性能、 通过流水线提高性能、 通过预测提高性能、存储器层次、通过冗余提高可靠性。

指令

MIPS 一共有 32 个 32 位的寄存器
程序中的变量放在保存寄存器（store reg）中：$s0~7 共 8 个
运算的临时变量放在临时寄存器（temp reg）中：$t0~9 共 10 个
零寄存器（zero reg）：$zero，常用于赋值为 0

三类指令：
运算指令：add、sub、mul、div、and、or、xor、nor、slt、sll、srl、sra
数据传送指令：lw、sw、lui
决策指令：beq、bne、j、jal、jr

三种指令格式：
R 型：op rd, rs, rt
I 型：op rt, rs, imm
J 型：op target

算术运算指令

如 a, b, c 三个变量分别存放在 $s0, $s1, $s2 中，要计算 c = a + b，则汇编代码为：

add $s2, $s0, $s1

计算 c = a - b，则汇编代码为：

sub $s2, $s0, $s1

加立即数，假设变量 i 位于 $s0，要计算 i = i + 1，则汇编代码为：

addi $s0, $s0, 1

要减就把立即数设为负数，故 MIPS 无 subi 指令。

逻辑运算指令

比较简单，nor 为或非，就是先或再非，与 0 或非可以实现取反。

sll $s2, $s0, 2 # $s2 = $s0 << 2

运算指令例子

result($s3) = a($s0) - 10 + (b($s1) + c($s2) * 5)

sll $t0, $s2, 2     # $t0 = c * 4
add $t1, $t0, $s2   # $t1 = c * 5
add $t2, $t1, $s1   # $t2 = b + c * 5
addi $t3, $s0, -10  # $t3 = a - 10
add $s3, $t3, $t2   # $s3 = a - 10 + (b + c * 5)

寄存器-存储器数据传送

lw 即 load word
假设数组 a 基址存放在 $s1 中，要把 a[5] 的值传送到 $s0 中：

lw $s0, 20($s1)

a[0] 到 a[5] 的距离是 5 个字，而在 MIPS 中，一个字是 4 个字节，所以 a[5] 的地址是 a 的基址加上 20。
把 $t0 的值传送到 a[2]：

sw $t0, 8($s1)

寄存器间数据传送

把 $t0 的值传送到 $s1：

addi $s1, $t0, 0
add $s1, $t0, $zero
move $s1, $t0           # move 是伪指令，等价于 add $s1, $t0, $zero

把常数 10 传送到 $s2：

addi $s2, $zero, 10
li $s2, 10              # li 是伪指令，即 load immediate

装载 32 位立即数

把 10A2 7FFF 放进 $s2：

lui $s2, 0x10A2         # load upper immediate
ori $s2, $s2, 0x7FFF    # or immediate

这里不能用 addi，因为如果低 16 位的最高位是 1，那么会被当作负数，造成结果错误。

例：数组元素运算与赋值
a[i] = a[0] + 100000，数组 a 的基址存放在 $s0 中，i 存放在 $s1 中：

lw $t0, 0($s0)          # $t0 = a[0]
lui $t1, 1              # notice: 100000 = 0x186A0 > 0xFFFF
ori $t1, $t1, 0x86A0
add $t2, $t0, $t1       # $t2 = a[0] + 100000
sll $t3, $s1, 2         # $t3 = i * 4
add $t4, $s0, $t3       # $t4 = &a[i]
sw $t2, 0($t4)          # a[i] = a[0] + 100000

决策指令

beq 即 branch equal，bne 即 branch not equal
j 即 jump，无条件跳转
例子：将如下代码翻译成 MIPS 汇编代码

if (i == j) f = g + h;
else f = g - h;

假设 f, g, h 分别存放在 $s0, $s1, $s2 中，i, j 分别存放在 $s3, $s4 中：

beq $s3, $s4, Else
add $s0, $s1, $s2
j Exit
Else:
sub $s0, $s1, $s2
Exit:

slt 即 set on less than，即小于则置位，否则清零（复位）
比如 $s0 = 0, $s1 = 0, $s2 = 1，则：

slt $s0, $s1, $s2

$s0 的会被置为 1，因为 0 < 1。

例子：

while (a[i] == k) i++;

假设 i 存放在 $s3，k 存放在 $s5，a 的基址存放在 $s6：

Loop:
sll $t0, $s3, 2     # $t0 = i * 4
add $t1, $s6, $t0   # $t1 = &a[i]
lw $t2, 0($t1)      # $t2 = a[i]
beq $t2, $s5, Exit  # if a[i] == k, exit
addi $s3, $s3, 1    # i++
j Loop
Exit:

指令格式

R 型指令

指令中含三个寄存器的运算指令都属于 R 型（register type）指令，格式为 op rd, rs, rt。
32 位的 MIPS 指令一共分为 6 个字段：

• 操作码（opcode）：6 位
• 源寄存器 1（register source 1，rs）：5 位
• 源寄存器 2（register source 2，rt，叫 rt 应该是因为 t 是 s 的下一个字母）：5 位
• 目的寄存器（register destination，rd）：5 位
• 移位量（shamt）：5 位
• 功能码（funct）：6 位

MIPS 有 32 个寄存器，所以 5 位就可以表示全部的 32 个寄存器，所以 rs、rt、rd 都是 5 位。
R 型指令的 opcode 都是 0，由 6 位功能码指定操作，$t0 ~ $t7 的编号是 8-15，$s0 ~ $s7 的编号是 16-23，add 的 funct 是 32，sub 的 funct 是 34。
sll/srl 也是 R 型指令，没有第二个源寄存器，rt 被置为 0，用 shamt 表示移位量。

I 型指令

addi 和 ori 都属于 I 型（immediate type）指令，格式为 op rt, rs, imm。
I 型指令用 opcode 表示操作，rs 表示源寄存器，rt 表示目的寄存器，并把 rd-shamt-funct 三个字段合并成了 16 位的 imm，即立即数。

lw 和 sw 也是 I 型指令，但是 rt 表示目的寄存器，rs 表示基址寄存器，和上面相反，imm 表示偏移量，这两个指令的操作码分别是 35 和 43。

I 型指令还有 beq 和 bne，用于分支。

J 型指令

j 和 jal 都属于 J 型（jump type）指令，格式为 op target。

过程

支持过程的三大寄存器：4 个参数寄存器 $a0 ~ $a3，两个返回值寄存器 $v0 ~ $v1，返回地址寄存器 $ra。

jal 即 jump and link，跳转到标签并保存返回地址到寄存器 $ra，由调用者主程序使用。
jr 即 jump register，跳转到寄存器中的地址，由被调用者过程使用，一般是 jr $ra。

两个栈指针寄存器 $sp（stack pointer） 和 $fp （frame pointer），分别表示栈指针和帧指针。在过程调用时，如果要用到保存寄存器，就要先压入栈中，调用结束后再弹出。

还有一个全局指针寄存器 $gp，便于寻找位置固定的数据，如主程序使用的变量、声明为 static 的变量，统称静态变量。

一般程序在内存中有 5 个段，地址从低到高依次为

1. 保留段
2. 代码段
3. 静态数据段
4. 堆段（动态数据段）
5. 栈段

堆由低向高增长，栈由高向低增长，双向奔赴，实现了内存空间的高效利用。

寻址

R 型指令都是寄存器寻址。
I 型指令第三个操作数（即第二个源操作数）是立即数的指令采用立即数寻址。lw 和 sw 采用基址偏移寻址。beq 和 bne 采用 PC(program counter) 相对寻址，分支 32 位地址 = PC + 4 + 字地址偏移量。
J 型指令都是伪直接寻址，因为 J 型指令是由 6 位操作码和 26 位目标地址组成的，寻址时先左移 2 位形成 28 位字节地址，再和 PC 的高 4 位拼接成 32 位地址。

假设第一行代码的地址是 10000，对如下代码：

Loop:
sll $t1, $s3, 2         # Temp reg $t1 = i * 4
add $t1, $t1, $s6       # $t1 = address of save[i]
lw $t0, 0($t1)          # Temp reg $t0 = save[i]
bne $t0, $s5, Exit      # go to Exit if save[i] != k
addi $s3, $s3, 1        # i = i + 1
j Loop                  # go to Loop
Exit:

bne $t0, $s5, Exit 中的立即数应该是 2，这里可以大概理解成隔了两条指令，而 j Loop 中的立即数稍微麻烦，首先因为 PC 的高 4 位是一样的，都是全 0，所以只需要考虑低 28 位，Loop 的地址是 10000，右移 2 位就是 100，所以 j Loop 的立即数是 100 （十进制的 4）的补码。

PC 相对寻址的范围是 (PC + 4) - 2e17 ~ (PC + 4 + 2e17 - 4)，大约是前后各 128 KB。
伪直接寻址的范围是和 PC 高 4 位相同的一切地址，即 256 MB。
要分支到更远的地址，就要把 beq 或者 bne 切换一下，然后下面跟一个 j 指令。
比如 beq $s0, $s1, L1 就换成如下代码：

bne $s0, $s1, L2
j L1
L2:

扩展跳转范围就直接换成 jr 指令，把目标地址放在寄存器中即可。
32 位系统最多只能支持 4 GB 的内存，所以 32 位的寄存器已经支持全部的内存寻址了。

C 语言的 4 个翻译层次

编译器将高级语言文件（.c）翻译成汇编文件（.asm），然后由汇编器将汇编文件翻译成机器码文件（.obj），再由链接器将机器码文件链接成可执行文件（.exe），最后由加载器将可执行文件加载到内存中执行。

算术运算

整数的表示

以下以 8 位二进制数为例：
无符号整数很好理解，就是 8 位全用来表示数值，如 0000 0000 表示 0，1111 1111 表示 255。
原码：用最高位表示正负号，其余 7 位表示绝对值
反码：将最高位为 0 的原码按位取反表示负数
补码：按位取反再加 1

符号扩展：
16 位扩展到 32 位时，将最高位（即符号位）复制到高 16 位。

大端编址和小端编址：
大端编址是将高位放在低地址，小端编址是将高位放在高地址。

比如 0xFFE0 在内存中时
大端编址：
低 8 位：0xFF
高 8 位：0xE0
小端编址：
低 8 位：0xE0
高 8 位：0xFF

ALU

符号位进位称为上溢，符号位借位称为下溢，统称溢出。

比较简单的 32 位 ALU 是行波进位加法器，即每一位都是一个全加器，每个全加器有三个输入：两个加数和上一位的进位，两个输出：和位和进位。
但是每次进位都要过一次或门和与门，就产生了 64 个门延迟。

为了加快进位，进而加速加法运算，现在广泛采用超前进位加法器，通过将进位分为 4 位一组，抽象成每组的进行，实现加法器的并行执行。

要执行 n 位加法，求出 n 是 4 的几次方，并向上取整，再乘 2 加 1，就是超前进位加法器的门延迟。
用数学表达式表示就是 $2 \times \lceil \log_4 n \rceil + 1$，n 为 16 时是 5，n 为 32 和 64 时都是 7。

除法中，规定余数和被除数同号，比如 -7/2 = -3 余 -1，而不是商 -4 余 1。

MIPS 中的乘除指令有 4 条，mult 和 div 是有符号的乘法和除法，multu 和 divu 是无符号的乘法和除法，均为双操作数 R 型指令。
mfhi 和 mflo 分别是将乘法和除法的高 32 位和低 32 位传送到寄存器中，均为单操作数 R 型指令。

浮点数

IEEE 754 标准规定了浮点数的表示方法，32 位单精度浮点数由 1 位符号位、8 位指数位和 23 位尾数位组成。注意指数要加 127 的偏差，同时这里的尾数是指小数点后的部分，因为二进制的科学计数法里，只要不是 0.0，那么小数点前的部分一定是 1。
举个例子 -0.00101 = -1.01 x 2^-3，很明显，因为是负数，所以符号位是 1，指数位是 -3 + 127 = 124，尾数位是 01（后面补 0）。
64 位双精度浮点数由 1 位符号位、11 位指数位和 52 位尾数位组成，指数偏差是 1023。

MIPS 中增加了单独的 32 个单精度浮点寄存器 $f0 ~ $f31，一对单精度浮点寄存器组合成一个双精度寄存器，以偶数编号。

add.s 和 sub.s 是单精度浮点数的加减法，mul.s 和 div.s 是单精度浮点数的乘除法，s 换成 d 就是双精度浮点数的运算。
比较两个浮点数大小，用 c.eq.s 和 c.lt.s，分别表示等于和小于，为真时用 bc1t 跳转，为假时用 bc1f 跳转。

这里我查了一下应该是 bc1t 和 bc1f，但是课本写的是 bclt 和 bclf，我觉得应该是笔误。

IEEE 754 在运算时引入了两个尾数位，分别是保护位和舍入位，运算误差不超过 0.5 个 ulp（unit in the last place，即尾数最低位）。

处理器

最核心的部分。

数字逻辑基础

组合逻辑不含存储器，给定输入时输出唯一确定，如 ALU。
状态逻辑（又称时序逻辑）含存储器，至少拥有两个输入：数据输入和时钟输入和一个输出。
总线表示数据信息多于一位的信号线，在数字电路图中加粗表示并标记位宽，由于 MIPS-32 采用 32 位字，所以当总线为 32 位时不必写出位宽。

指令周期

一条 MIPS 指令的执行分为 5 个阶段，统称一个指令周期，分别是：

1. 取指令（IF，Instruction Fetch）：从内存中取指令
2. 指令译码（ID，Instruction Decode）：译码并取寄存器
3. 执行（EX，Execute）：执行指令
4. 访存（MEM，Memory）：访问内存
5. 写回（WB，Write Back）：写回结果

R 型指令和 lw/sw/beq 在 IF 的时候都是根据 PC 从存储器中取出指令。
R 型指令在 ID 时取源操作数 rs 和 rt，在 EX 时执行运算，没有 MEM，因为三个操作数都是寄存器，WB 时将结果写回 rd。
lw/sw 在 ID 时取基址寄存器 rs，并将偏移量 imm 符号扩展，EX 时计算内存地址，lw 在 MEM 时从内存中取数据，WB 时写回寄存器 rt，sw 在 MEM 时将数据写入内存，WB 时不做任何操作。
beq 在 ID 时取 rs 和 rt，将字地址符号扩展并左移两位，EX 时比较 rs 和 rt，计算分支地址，MEM 时写回 PC，WB 时不做任何操作。

在单周期实现中，每条指令都在一个时钟周期内完成，CPI 为 1。
多周期实现中可以缩减时钟周期到一个阶段的长度，一条指令占用几个阶段，就执行几个周期。

指令周期与流水级

与指令周期的五个阶段相对应，把数据通路分为五个流水级，形成流水线（pipeline）。
时钟周期数 = 指令数 + 流水级级数 - 1（cycles = IC + stages - 1）。
理想加速比 = 流水级级数（$S_{理想}$ = stages）。
理想条件为：1.每个流水级时间等长 2.流水线没有开销 3.指令数足够多。
省略流水周期可能导致两条指令抢占同一流水级的硬件部件，引发结构冒险（structural hazard），解决的通行方法是添加硬件。

数据冒险产生原因及其解决办法

产生原因：由于取到的指令需要的数据还没有准备好，导致指令不能在预定的时钟周期内执行。

解决办法：
1）数据旁路：将数据从一个流水级传递到另一个流水级，而不是等到写回阶段再传递。
2）先写后读：对寄存器堆操作时，前半个周期写，后半个周期读，可以减少一次数据冒险。
3）插入气泡：在流水线中插入一个空操作，让后面的指令等待，直到数据准备好。

ALU 运算结果引出旁路传到另一个 ALU，叫做 ALU-ALU 旁路，从 MEM 级传到 ALU 叫做 MEM-ALU 旁路，两个旁路都有时，称为全旁路。

控制冒险产生原因及其解决办法

产生原因：由于取到的指令并不是需要的指令，而导致指令不能在预定的时钟周期内执行。
说具体点，比如 beq 指令在 EX 阶段后才知道是否要跳转，但是在 ID 阶段已经取到了下一条指令，如果要跳转，就要把下一条指令丢弃，导致控制冒险。

解决办法：
1）缩短分支延迟：将分支地址计算从 EX 级提前到 ID 级；
2）动态分支预测：通过查找指令地址观察上一次执行该指令时分支是否发生，如果上次执行时分支发生，就从上次分支发生的地方开始取新的指令；
3）延迟分支调度：编译器通过分析代码用不影响分支的一条指令填充到分支延迟时间槽。

流水线性能

流水线在同一时间处理多条指令的不同阶段，实现指令级并行。
由时钟周期长度决定的吞吐率是评价流水线性能的重要指标。
在两个流水级间插入流水线寄存器，以左右两个流水级命名，分别叫 IF/ID、ID/EX、EX/MEM、MEM/WB。
流水线的时钟周期是由最慢的流水级决定的。
流水线的控制信号在译码时产生，逐级递减。
前半个周期写寄存器堆，后半个周期读寄存器堆，可以减少一次数据冒险。

控制单元信号

控制信号	功能
RegDst	启用 rd
ALUSrc	imm 输入 ALU
MemtoReg	存储器写回
RegWrite	写寄存器堆
MemRead	读存储器
MemWrite	写存储器
Branch	分支
ALUOp1 / ALUOp0	ALU 操作码

以指令 and rd, rs, rt 为例，RegDst 为 1，没有立即数，所以 ALUSrc 为 0，没有任何与存储器有关的操作，所以 MemtoReg MemRead MemWrite 均为 0，不是 beq，所以 Branch 也为 0，然后 R 型指令的 ALUOp 信号都是 10。

加速比 = 改进前的时钟周期数 / 改进后的时钟周期数

存储层次

cache 和内存

L1-L3 高速缓存
cache 通常集成在 CPU 中，采用静态随机访问存储器（SRAM）集成电路，由双稳态触发器构成，每 B（byte） 由 6-8 个晶体管组成，硬件规模较大
L4 内存
采用动态随机访问存储器（DRAM）集成电路，使用电容保存电荷，进而存储数据，每 B 仅使用一个晶体管，硬件规模远小于 SRAM（密度大于 SRAM），由于电荷只能短暂留存，需要周期性地将一行上的数据读出后重新写入，完成刷新
SRAM 和 DRAM 在断电后很快丢失数据，称为易失性存储器（volatile memory）
L5 二级存储器或辅存
磁盘每个盘片由数万道磁道组成，每个磁道又被分为几千个扇区，扇区是最小的存储单位。
现在多使用闪存，一种集成电路制造的电可擦除可编程只读存储器（EEPROM），数据更快，功耗更低。
磁盘和闪存断电后不丢失数据，称为非易失性存储器（non-volatile memory）

局部性原理

对一条程序正在执行的指令来说
如果该指令位于循环体中，很可能不久后会被再次访问——时间局部性
如果该指令位于循环体或顺序指令流中，将要执行的指令往往地址相近——空间局部性

那么就可以将内存中的一小块数据/指令复制到 cache 中，以提高访问速度。

命中与缺失

访存即访问内存，分为读取和写入。
访存指令 = MEM-reg 数据传送指令 = L-S 指令（即 lw 和 sw 指令）
CPU 访问内存时，都会优先访问 cache，如果 cache 中有数据，就是命中，否则就是缺失。
命中/缺失占访存次数的比例叫做命中率（HR，Hit Rate）和缺失率（MR，Miss Rate），满足 HR + MR = 1。

访存阻塞周期数

CPU 访问 cache 的时间称为命中时间，通常只有 1T
CPU 访问内存比访问 cache 多出来的时间称为缺失代价（Miss Penalty）
注意访问内存比直接访问 cache 多出来的额外开销，才是缺失代价

定义一个程序的 L-S 指令数目为访存次数（MAC，Memory Access Count）
定义程序中 L-S 指令占总指令数的比重为访存率（MAR，Memory Access Rate）
为了评价存储器性能，我们将程序执行的周期 cycles 分为 CPU 执行周期数 + 访存阻塞周期数两部分
访存阻塞周期数 = 访存次数 x 缺失率 x 缺失代价 = MAC x MR x MP

直接映射

块号

cache 块号 = 内容块号 % cache 块数
对 $2^n$ 个块的 cache，cache 块号 = 内存二进制块号的后 n 位
注意内存的块号是地址的前 30 位，
假设 cache 有 1K（即 $2^{10}$ 个块），对访存地址 0000 0000 0000 0000 0000 0000 0011 1100，其块号是 00 0000 0000 0000 0000 0000 0000 1111，对应的 cache 块号是 00 0000 1111

内存地址字段

可以把 32 位内存地址分成三段
① 标记位 ② 索引位 ③ 块内（字节）偏移
索引位就是 cache 块号，后面的两位指示具体访问块中的哪个字节
索引位前面的高位是标记位，结合索引位就能唯一确定内存中的块

cache 最前面还要加上一个有效位，用于标记 cache 中的块是否有效

cache 位数计算

处理器访存读写的数据通常为一个 32 位字，一字一块根本不能利用空间局部性。

假设一个 16 KB 数据的 cache，块大小为 4 个字，地址为 32 位，问该 cache 总共需要多少字节？
首先块大小是 4 个字即 16 字节，所以块偏移应该占 4 位，16 KB/16 B = 1 K = 1024，所以索引位应该占 10 位，剩下的 18 位就是标记位。
对每个块，还要有一个有效位，所以一个块就有 1 + 18（地址标记） + 16*8 = 147 个 bit
总容量就是 147 x 1024 = 150528 bit = 18792 B = 18.375 KB
注意这里如果题目换成 16 KB 的 cache 也默认是 16 KB 数据的 cache，不是 16 KB 容量的 cache。

缺失分类 3C 模型

根据产生原因，缺失分为以下三大类：

1. 首次访问 cache 中没有的块必然产生的缺失，称为冷启动强制缺失（Compulsory Miss）
2. 由于 cache 的容量不能容纳程序执行需要的所有块，部分块被替换后再次调入 cache，称为容量缺失（Capacity Miss）
3. 多个内存块竞争映射到同一个 cache 块，导致仍需使用的块被替换，称为冲突碰撞缺失（Conflict Miss）

都是 C 开头的，所以称为 3C 模型

适当增加块大小（同时也会减少块数）可以更好地利用空间局部性，减少强制缺失；但是块数减少会增加冲突缺失。
加大 cache 容量可以减少容量缺失

缺失处理和写策略

cache 访问缺失处理的步骤为：

1. 将 PC + 4 - 4（即当前指令的地址）写回 PC，并阻塞处理器
2. 访问内存，将内存块写入 cache
3. 再次访问 cache 并命中

当 CPU 把新数据写入内存块时，又要把数据写到 cache，保持内存和 cache 内容一致
方式一：CPU 和 cache 同时开始写内存，称为写直达（Write Through），但是开销很大，可改进为缓冲，CPU 较快写入缓冲后执行其他操作，缓冲再慢慢写入内存
方式二：CPU 只写入 cache，仅当这个 cache 块被替换时才写入内存，称为写回（Write Back）

全相联映射

内存块可能映射到任何一个 cache 块，称为全相联映射（Fully Associative Mapping）
内存块可进入任何一个 cache 块，只要 cache 中有空位，就可以直接进入，不会产生冲突缺失
如果 cache 已满，则替换掉最长时间没有使用过的内存块，称为最近最少使用（Least Recently Used，LRU）替换策略
查找时需要比较每一块的标记位，开销过大，只适用于块数较少的 cache

组相联映射

将直接映射和全相联映射折中，对 cache 块进行分组，一个内存块直接映射到一个组，但分配到组内的哪一块较为自由，也就是在一个组内全相联，这种映射方式称为组相联映射（Set Associative Mapping）
一组包含 n 块则称为 n 路组相联，其相联度为 n
直接映射就是 1 路组相联，全相联就是相联度 = 块数的组相联

cache 组号 = 内存块号 % cache 组数
对 $2^n$ 个组的 cache，cache 组号 = 内存二进制块号的后 n 位

缺失处理、写策略、替换策略

全相联和组相联的缺失处理过程和直接映射相同
替换策略采用 LRU，用 1 位来编号记录 2 路组相联一组最久没有使用的块，用 2 位来编号记录 4 路组相联一组最久没有使用的块，以此类推，这个编号称为 LRU 位
实际上，LRU 的开销仍然较大，很多 4 路组相联的系统也只是近似实现 LRU

例 假设一个 cache 有 4096 个块，块大小为 4 个字，地址为 32 位，请计算两路组相联、全相联中 cache 的总位数。

4 个字就是 16 个字节，用 4 位表示块偏移；两路组相联就是每组有两个块，那么就是 2048 即 $2^{11}$ 组，用 11 位表示索引位，剩下的 17 位就是标记位，那么对每个块就有 1 + 17 + 16 x 8 = 146 位，总共就是 146 x 4096 = 598016 位 = 74752 B = 73.0 KB

cache 性能评价：AMAT 与 CPI

平均访存时间（Average Memory Access Time，AMAT）是评价 cache 性能的重要指标，用周期数表示即可，不一定要化成秒
平均访存时间 = 命中时间 + 缺失率 x 缺失代价（AMAT = HT + MR x MP）

例 设处理器基本 CPI 为 1，时钟频率为 4 GHz。设访存指令占指令数的 20%，一级 cache 缺失率为 10%，速度可满足处理器全速运行；现增加一个二级 cache，访问时间为 5 ns，全局缺失率为 2.5%，访问主存的时间为 100 ns。二级 cache 局部缺失率和该处理器的 CPI 为多少？

缺失率 = 2.5% / 10% = 25%
时钟频率为 4 GHz，那么时钟周期就是 0.25 ns，5 ns = 20 个时钟周期，100 ns = 400 个时钟周期
CPI = 1 + 20 x 20% x 10% + 400 x 20% x 2.5% = 3.4
若题干改为：一级 cache 中每条指令的缺失率为 2%，二级 cache 使得访问主存的缺失率减少到 0.5%
则 CPI = 1 + 20 x 2% + 400 x 0.5% = 1 + 0.4 + 2 = 3.4

多核 CPU 中的 cache 一致性

最常用的 cache 一致性协议是监听（Snooping）协议，每个 cache 都监听其他 cache 的读写操作，当有 cache 写入数据时，其他 cache 会将该数据置为无效，这称为写时无效协议（Write Invalidate Protocol）
使两个核的写操作一前一后的机制称为写串行化（Write Serialization）

广义 cache

任意两级相邻的存储器中较高的一级都可以称为较低一级存储器的广义的 cache
高速缓存是内存的 cache，同样，内存是磁盘的 cache，TLB 快表是页表的 cache

虚拟地址转换为物理地址

虚拟内存的空间大于物理内存
磁盘和内存之间交换的块称为页（Page）
对 4 KB 即 $2^{12}$ B 的页，需要 12 位表示页内偏移
虚拟页号通过查询页表（Page Table）转换为物理页号，由于内存和磁盘中页大小相同，页内偏移和物理页号拼接形成物理地址

页表和页表项 页表寄存器 缺页处理

每个进程都有一张页表，存放自己的内存空间
页表首地址存放在页表寄存器（Page Table Register，PTR）中
页表项记录每个虚拟地址对应的物理地址
和高速缓存类似，页表中需要一个有效位来识别访问的页是否在内存中
访问页不在内存时，产生一次缺页，此时需要读取磁盘用于扩充物理内存的部分，即交换区（Swap Space）

替换策略 写策略

当一个进程的物理内存空间占满时，从磁盘交换区中调入内存的块需要替换掉内存中的某一块
使用引用位（Reference Bit）来近似实现 LRU 替换算法

由于磁盘访问时间长达几千万个时钟周期，所以需要尽量减少访问磁盘特别是写入磁盘的操作
因为内存中的页只能使用写回机制写入磁盘
还需要在页表中添加一个脏位（Dirty Bit），用于标记页是否被修改过，被修改过的才需要写回磁盘

TLB 快表

页表位于内存中，CPU 访存时，需要先拿着虚拟地址访存读取页表得到物理地址，再真正进行访存
为了加快第一次物理地址的访存，引入了页表的 cache，即 TLB（Translation Lookaside Buffer）

页表将每一个虚拟页号作为索引，因此不需要类似于标记位的字段，但是 TLB 只保存部分虚拟页号的映射信息
故 TLB 需要将虚拟页号作为标记位，并保留页表中全部信息，即 3 个标志位和物理页号

可靠性与可用性评价

从开始使用到失效的时间间隔称为平均无故障时间（Mean Time To Failure，MTTF）
应对故障从而提高 MTTF 的策略有：故障避免、故障容忍、故障预报
一年的时长比上 MTTF 得到年失效率（Annual Failure Rate，AFR），即 AFR = 一年 / MTTF

恢复一个系统功能的时间为平均维修时间（Mean Time To Repair，MTTR）
从开始使用到失效维修结束为平均失效间隔时间（Mean Time Between Failures，MTBF）
可用性定义为系统正常工作时间与两次服务中断间隔时间之比
MTBF = MTTF + MTTR
可用性 = MTTF / MTBF

奇偶校验码 汉明距离

在奇校验中，校验位确保整个校验码有奇数个 1，偶校验则相反
任意两个合法校验码之间至少相差的位数称为汉明距离（码距）
奇偶校验码距为 2，能实现检测一位错（Single Error Detection，SED），但不能定位错误

汉明码

对 8 位数据 1001 1010 编入偶校验的汉明校验码

1. 从左往右第 1、2、4、8 位挖空
2. 其他位依次填入数据
3. 对校验位 p1，检测 1、3、5、7 位
   对校验位 p2，检测 2、3、6、7、10、11 位
   对校验位 p4，检测 8、9、10、11、12 位

如下表所示

位号	1	2	3	4	5	6	7	8	9	10	11	12	偶校验结果
分类位号	p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	-
数据	0	1	1	1	0	0	1	0	1	0	1	0	-
p1 覆盖	√		√		√		√		√		√		1
p2 覆盖		√	√			√	√			√	√		1
p4 覆盖				√	√	√	√					√	1
p8 覆盖								√	√	√	√	√	1

所以其汉明码为 011100101010
汉明码码距为 3，能够定位一位错，对该位取反可实现纠正一位错（Single Error Correction，SEC）
定位步骤：

1. 根据新的码字，重新进行汉明码校验编码
2. 将新旧两组校验位从右往左写，按位异或
3. 结果即为出错位号

如果码距为 4，能够检测两位错，但不能纠正

从客户端到云的并行处理器

第四章讨论指令级并行，这一章讨论的是任务级并行，主要通过多核和多线程实现。
单指令流多数据流（SIMD）计算机对向量数据进行操作，性能优于标量机。
Roofline 模型被广泛用于评价并行浮点计算机的性能。

汇编语言拥有编译器输出语言和编程语言两种角色。
使用汇编语言编程的情况：
1）性能要求极端苛刻，如控制汽车刹车的嵌入式系统
2）需要深入硬件底层优化程序
3）需要使用定制指令
4）为没有可用编译器的老旧计算机编写程序

参考

https://www.bilibili.com/video/BV1je4y1Q7BK