Featured image of post 计原复习
计算机系统原理

计原复习

计算机抽象及相关技术

IC Cost

die: 芯片
wafer: 晶圆
Yield: 良品率
defects: 缺陷

$$\text{Cost per die} = \frac{\text{Cost per wafer}}{\text{Dies per wafer}\times \text{Yield}} = \frac{\text{晶圆成本}}{\text{晶圆上可用的芯片数量}}$$

$$ \text{Dies per wafer} \approx \frac{\text{晶圆面积}}{\text{芯片面积}} $$

$$ \text{Yield} = \frac{1}{(1+\frac{\text{单位面积缺陷数} \times \text{芯片面积}}{2})^2} $$

性能与执行时间

  1. 性能的定义：

    • Performance = 1 / Execution Time
    • 表示为：

    $$ \frac{\text{Performance}_X}{\text{Performance}_Y} = \frac{\text{Execution Time}_Y}{ \text{Execution Time}_X} $$

    • 如果系统 A 运行一个程序用时 10 秒，而系统 B 用时 15 秒，则：
      • Execution_Time_B / Execution_Time_A = 15s / 10s = 1.5
      • 所以 A 比 B 快 1.5 倍。

  2. CPU 时间计算：

    CPU Time：CPU 执行某个任务所需的时间。
    Clock Cycle Time：每个时钟周期的持续时间。
    CPU Clock Cycles：执行该任务所需的时钟周期数。
    Clock Rate：时钟频率，时钟周期的倒数。
    CPI：CPU 每条指令平均所花费的时钟周期数。

    • CPU Time = CPU Clock Cycles × Clock Cycle Time = CPU Clock Cycles / Clock Rate
    • 或者表示为：CPU Time = Instruction Count × CPI × Clock Cycle Time

    例题 1: 假设有一个程序，在 Computer A 上运行时，CPU 时间为 10 秒，其时钟频率为 2GHz（即每个时钟周期为 0.5 纳秒）。如果设计 Computer B 的目标是将 CPU 时间减少到 6 秒，但是由于更快的时钟导致 CPI 增加了 1.2 倍，那么为了满足新的 CPU 时间要求，Computer B 的时钟频率应该是多少呢？

    设 Computer A 的 CPI 为 $\text{CPI}_A$，那么：

    $$\text{CPU Clock Cycles}_B = \text{Instruction Count} \times (1.2 \times \text{CPI}_A)$$

    $$\text{CPU Time}_B = \frac{\text{CPU Clock Cycles}_B}{\text{Clock Rate}_B} $$

    给定目标 CPU 时间为 6 秒，则：

    $$6s = \frac{\text{Instruction Count} \times 1.2 \times \text{CPI}_A}{\text{Clock Rate}_B} $$

    我们知道 Computer A 的 CPU 时间为 10 秒，因此：

    $$10s = \frac{\text{Instruction Count} \times \text{CPI}_A} {\text{Clock Rate}_A} $$

    结合两个方程，解出 Computer B 的时钟周期频率：

    $$\text{Clock Rate}_B = 4GHz $$

    所以，Computer B 的时钟频率应该设定为 4GHz。

    例题 2：比较两台计算机的性能

    • 计算机 A：
      • Cycle Time = 250ps (皮秒)
      • CPI = 2.0
    • 计算机 B：
      • Cycle Time = 500ps
      • CPI = 1.2
    • 假设两台计算机使用相同的指令集架构（ISA）。

    问题：哪台计算机更快，快多少？

    解答：

    $$\text{CPU Time}_A = \text{Instruction Count} \times \text{CPI}_A \times \text{Cycle Time}_A $$

    $$\text{CPU Time}_B = \text{Instruction Count} \times \text{CPI}_B \times \text{Cycle Time}_B$$

    代入给定值：

    $$\text{CPU Time}_A = I \times 2.0 \times 250ps = I \times 500ps$$

    $$\text{CPU Time}_B = I \times 1.2 \times 500ps = I \times 600ps$$

    所以，计算机 A 比计算机 B 快 1.2 倍。

    例题 2：不同编译代码序列的平均 CPI

    • 指令类别：
      • Class A: CPI = 1
      • Class B: CPI = 2
      • Class C: CPI = 3
    • 两种不同的编译代码序列：
      • 序列 1：$IC_A = 2, IC_B = 1, IC_C = 2$
      • 序列 2：$IC_A = 4, IC_B = 1, IC_C = 1$

    问题：分别计算两个序列的平均 CPI。

    解答：

    对于序列 1：

    $$\text{Clock Cycles}_{\text{seq1}} = 2 \times 1 + 1 \times 2 + 2 \times 3 = 10 $$

    $$\text{Avg. CPI}_{\text{seq1}} = \frac{\text{Clock Cycles}_{\text{seq1}}}{\text{Total Instructions}} = \frac{10}{5} = 2.0 $$
    对于序列 2：

    $$\text{Clock Cycles}_{\text{seq2}} = 4 \times 1 + 1 \times 2 + 1 \times 3 = 9 $$

    $$\text{Avg. CPI}_{\text{seq2}} = \frac{\text{Clock Cycles}_{\text{seq2}}}{\text{Total Instructions}} = \frac{9}{6} = 1.5 $$

功率消耗

  1. CMOS IC 技术中的功率公式：

    $$ \text{Power} = \text{Capacitive load} \times \text{Voltage}^2 \times \text{Frequency} $$

    • Power (功率)：指的是电路消耗的电功率，单位通常为瓦特(W)。
    • Capacitive load (电容负载)：表示电路中所有电容器的等效总电容，单位为法拉(F)。电容负载决定了每次开关操作时需要充放电的能量量级。
    • Voltage (电压)：指工作电压，单位为伏特(V)。较高的电压意味着每次开关操作时转移更多的能量。
    • Frequency (频率)：即电路的工作频率或时钟频率，单位为赫兹(Hz)。频率越高，单位时间内发生的开关次数越多。

Amdahl 定律

$$T_{\text{total}} = T_{\text{unaffected}} + \frac{T_\text{improved}}{\text{improvement factor}}$$

考虑一个程序，其中 80%的时间花在乘法运算上，20%的时间花在其他不可并行化的操作上。如果我们设法使乘法运算的速度提高了 5 倍，那么根据 Amdahl’s Law，整个程序的最大加速比将是：

$$\frac{T_\text{origin}}{T_\text{total}} = \frac{T_\text{origin}}{0.2 \times T_\text{origin} + \frac{0.8\times T_\text{origin}}{5}} = \frac{1}{0.2+0.16} \approx 2.78$$

这意味着尽管我们大大加快了乘法运算的速度，但整个程序只能大约快 2.78 倍。

MIPS

MIPS 表示一个处理器在一秒钟内可以执行多少百万(Million)条指令。

MIPS 曾经是评估处理器性能的一个重要参数，但由于其不能全面反映现代计算机系统的复杂性和多样性，现在更多地被其他更为精确和综合的性能评估方法所取代。

指令—计算机的语言

MIPS 指令集

由斯坦福大学开发，并商业化为 MIPS Technologies 的产品。广泛应用于嵌入式系统、消费电子、网络/存储设备等。

寄存器

拥有 32 个通用寄存器，每条指令只能对寄存器中的数据进行算术操作。

名称 寄存器编号 用途
$zero 0 始终为 0 的常量值
$at 1 保留给汇编器使用
$v0-$v1 2-3 存储函数返回值或表达式计算结果
$a0-$a3 4-7 函数参数传递
$t0-$t7 8-15 临时变量，不被子程序保存
$s0-$s7 16-23 保存的变量，子程序需要保存和恢复
$t8-$t9 24-25 额外的临时变量
$k0-$k1 26-27 保留给操作系统使用
$gp 28 全局指针
$sp 29 栈指针
$fp 30 帧指针
$ra 31 返回地址

指令类型

MIPS 指令分为三种主要类型：R 型（Register）、I 型（Immediate）和 J 型（Jump），它们有着不同的格式。

  • R 型指令

    用于执行两个寄存器的操作数，并将结果存储在另一个寄存器中。例如 add 和 sub。

    • 格式：op rs rt rd shamt funct
    • 字段解释：
    • op (6 bits)：操作码，R 型指令为 0。
    • rs (5 bits)，rt (5 bits)，rd (5 bits)：源寄存器和目标寄存器。
    • shamt (5 bits)：移位数量（对某些指令有效）。
    • funct (6 bits)：功能码，指定具体的操作。

  • I 型指令

    包含一个立即数（Immediate value），可以是偏移量或者直接的数值。例如 lw（加载字）、sw（存储字）以及带立即数的算术指令如 addi。

    • 格式：op rs rt immediate
    • 字段解释：
    • op (6 bits)：操作码。
    • rs (5 bits)，rt (5 bits)：源寄存器和目标寄存器。
    • immediate (16 bits)：立即数。

  • J 型指令

    用于无条件跳转，直接提供下一条指令的地址。

    • 格式：op address
    • 字段解释：
    • op (6 bits)：操作码。
    • address (26 bits)：目标地址，与当前 PC 组合以形成完整的跳转地址。

MIPS 指令汇总

符号拓展：符号扩展会复制最高位以填充高字节。
零拓展：无论加载的字节是什么，零扩展都会用 0 来填充高字节。

  • R-type

    对于 R 型指令，add 和 addu 唯一的区别就是 add 会做溢出检查，而 addu 不会，其他语句同理

    助记符 操作及其解释 op rs rt rd shamt func 示例 示例含义
    add rd = rs + rt 000000 rs rt rd 00000 100000 add $1,$2,$3 $1=$2+$3
    addu rd = rs + rt 000000 rs rt rd 00000 100001 addu $1,$2,$3 $1=$2+$3
    sub rd = rs - rt 000000 rs rt rd 00000 100010 sub $1,$2,$3 $1=$2-$3
    subu rd = rs - rt 000000 rs rt rd 00000 100011 subu $1,$2,$3 $1=$2-$3
    and rd = rs & rt 000000 rs rt rd 00000 100100 and $1,$2,$3 $1=$2 & $3
    or rd = rs | rt 000000 rs rt rd 00000 100101 or $1,$2,$3 $1=$2 | $3
    xor rd = rs xor rt 000000 rs rt rd 00000 100110 xor $1,$2,$3 $1=$2 ^ $3
    nor rd = not(rs | rt) 000000 rs rt rd 00000 100111 nor $1,$2,$3 $1=~($2 | $3)
    slt if (rs < rt) rd=1 else rd=0 000000 rs rt rd 00000 101010 slt $1,$2,$3 if($2<$3) $1=1 else $1=0
    sltu if (rs < rt) rd=1 else rd=0 (以无符号数解释 rs 和 rt) 000000 rs rt rd 00000 101011 sltu $1,$2,$3 if($2<$3) $1=1 else $1=0
    sll rd = rt << shamt 000000 00000 rt rd shamt 000000 sll $1,$2,10 $1=$2<<10
    srl rd = rt >> shamt (logical) 000000 00000 rt rd shamt 000010 srl $1,$2,10 $1=$2>>10
    sra rd = rt >> shamt (arithmetic) 000000 00000 rt rd shamt 000011 sra $1,$2,10 $1=$2>>10 用原符号位填充高位
    sllv rd = rt << rs 000000 rs rt rd 00000 000100 sllv $1,$2,$3 $1=$2<<$3
    srlv rd = rt >> rs (logical) 000000 rs rt rd 00000 000110 srlv $1,$2,$3 $1=$2>>$3
    srav rd = rt >> rs (arithmetic) 000000 rs rt rd 00000 000111 srav $1,$2,$3 $1=$2>>$3 用原符号位填充高位
    jr PC = rs 000000 rs 00000 00000 00000 001000 jr $31 goto $31

  • I-type

    同上，addi 和 addiu 唯一的区别就是 addi 会做溢出检查，而 addiu 不会，其他语句同理。
    特别注意，无论是 addi 还是 addiu，都做符号拓展。
    更一般的，所有算术运算都做符号拓展，而逻辑运算都做零拓展。

    助记符 操作及其解释 op rs rt immediate 示例 示例含义
    addi rt = rs + (sign-extend)immediate 001000 rs rt immediate addi $1,$2,100 $1=$2+100
    addiu rt = rs + (sign-extend)immediate 001001 rs rt immediate addiu $1,$2,100 $1=$2+100
    andi rt = rs & (zero-extend)immediate 001100 rs rt immediate andi $1,$2,10 $1=$2 & 10
    ori rt = rs | (zero-entend)immediate 001101 rs rt immediate ori $1,$2,10 $1=$2 | 10
    xori rt = rs xor (zero-extend)immediate 001110 rs rt immediate xori $1,$2,10 $1=$2 ^ 10
    lui rt = immediate*65536(加载高 16 位) 001111 00000 rt immediate lui $1,100 $1=100*65536
    lw rt = memory[rs + (sign-extend)immediate] 100011 rs rt immediate lw $1,10($2) $1=memory[$2 + 10]
    sw memory[rs + (sign-extend)immediate] = rt 101011 rs rt immediate sw $1,10($2) memory[$2 + 10]=$1
    beq if (rs == rt) goto (label)immediate 000100 rs rt immediate beq $1,$2,exit if($1==$2) goto exit
    bne if (rs != rt) goto (label)immediate 000101 rs rt immediate bne $1,$2,exit if($1!=$2) goto exit
    slti if (rs < (signed-extend)immediate) rt=1 else rt=0 001010 rs rt immediate slti $1,$2,10 if($2<10) $1=1 else $1=0
    sltiu if (rs < (signed-extend)immediate) rt=1 else rt=0(注意，将 immediate 经过有符号拓展后，拓展后的结果与 rs 进行无符号比较) 001011 rs rt immediate sltiu $1,$2,10 if($2<10) $1=1 else $1=0

  • J-type

    助记符 操作及其解释 op address 示例 示例含义
    j PC = (PC+4)[31..28],address,0,0 000010 address j exit goto exit
    jal $31=PC+4；PC = (PC+4)[31..28],address,0,0 000011 address jal 10000 $31=PC+4; goto exit

  • 特别的指令

    1. lb (Load Byte)

      • 功能：从内存中加载一个带符号的字节到寄存器。

      • 格式：lb $rt, offset($base)

      • 操作：从地址 $base + offset 中加载一个字节，并将其符号扩展为 32 位后存储到寄存器 $rt 中。

      • 示例：lb $t0, 0($s1) # 将内存位置$s1指向的字节加载到$t0，并进行符号扩展

    2. lbu (Load Byte Unsigned)

      • 功能：从内存中加载一个不带符号的字节到寄存器。
      • 格式：lbu $rt, offset($base)
      • 操作：从地址 $base + offset 中加载一个字节，并将其零扩展为 32 位后存储到寄存器 $rt 中。
      • 示例：lbu $t0, 0($s1) # 将内存位置$s1指向的字节加载到$t0，并进行零扩展

    3. sb (Store Byte)

      • 功能：将寄存器中的低 8 位存储到内存中的一个字节位置。
      • 格式：sb $rt, offset($base)
      • 操作：将寄存器 $rt 的最低 8 位存储到地址 $base + offset 所指向的内存位置。高 24 位被忽略。
      • 示例：sb $t0, 0($s1) # 将$t0寄存器的低8位存储到$s1指向的内存位置

用 MIPS 实现递归

在 C 语言中，递归函数会自动处理调用栈。而在 MIPS 中，需要显式管理栈指针（$sp）和帧指针（$fp），并且保存返回地址（$ra）。

例如，考虑一个简单的递归阶乘函数：

1
2
3
4

int factorial(int n) {
    if (n <= 1) return 1;
    else return n * factorial(n - 1);
}

MIPS 代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

factorial:
    addi $sp, $sp, -8      # 为新的栈帧分配空间
    sw   $ra, 4($sp)       # 保存返回地址
    sw   $a0, 0($sp)       # 保存参数 n

    slti $t0, $a0, 2       # 测试 n 是否小于 2
    beq  $t0, $zero, L1    # 如果 n >= 2，则跳转到 L1
    li   $v0, 1            # 如果 n < 2，设置返回值为 1
    j    L2                # 跳转到结束

L1:
    addi $a0, $a0, -1      # 减少 n
    jal  factorial         # 递归调用 factorial，并将当前地址保存到 $ra
    lw   $a0, 0($sp)       # 恢复原始 n
    mul  $v0, $v0, $a0     # 计算 n * factorial(n-1)

L2:
    lw   $ra, 4($sp)       # 恢复返回地址
    addi $sp, $sp, 8       # 恢复栈指针
    jr   $ra               # 返回调用者

指令的十六进制表示

每条 MIPS 指令最终会被编码成 32 位二进制字符串，然后可以转换成 8 位一组的十六进制形式。例如，以下是一条机器指令 add $s0, $a1, $t7 的十六进制表示过程：

  • 首先将其转换为二进制：
    • 0000 0000 0000 1010 1111 1000 0000 0010 0000
  • 然后转换为十六进制：
    • 0x00af8020

计算机的算术运算

整数加法与减法的溢出情况

  • 整数加法：

    • 加法操作可能导致溢出，尤其是当两个正数相加结果为负或两个负数相加结果为正时。
    • 溢出判断：如果最高位（符号位）产生进位，则发生溢出。

  • 整数减法：

    • 减法通过加法来实现。
    • 溢出发生在减法结果超出表示范围时，例如从正数减去较大负数或从负数减去较大正数，如果最高位（符号位）与被减数不同，则发生溢出。

进位逻辑与加法器设计

全加器（Full Adder）

全加器是一种数字电路，用于执行两个二进制数的加法操作，并考虑来自低位的进位。它有三个输入：两个加数 A 和 B 以及一个低位进位 Cin；有两个输出：一个是本位的和 S，另一个是向高位的进位 Cout。

  • 逻辑表达式：

    • 和 (Sum, S) = A ⊕ B ⊕ Cin
    • 进位 (Carry out, Cout) = (A ∧ B) ∨ (Cin ∧ (A ⊕ B))

  • 真值表：

    A B Cin Sum (S) Carry out (Cout)
    0 0 0 0 0
    0 0 1 1 0
    0 1 0 1 0
    0 1 1 0 1
    1 0 0 1 0
    1 0 1 0 1
    1 1 0 0 1
    1 1 1 1 1

串行进位加法器（Ripple Carry Adder）

串行进位加法器由多个全加器级联组成，每个全加器接收前一级产生的进位并计算自己的和与进位。由于每一位的结果依赖于前一位的进位，因此延迟会随着位数的增加而线性增长。

  • 特点：
    • 进位按顺序传递，导致较长的延迟。
    • 对于 n(从 0 开始) 位加法器，从最低位到最高位的总延迟为 2n (每级进位都需要 2 级门延迟)个门延迟。
    • 最后一位和数的延迟时间约为 2n + 1 ((A xor B)(可提前计算) xor(3 级) CarryIn(2(n-1) 级延迟) = 3+2(n-1) = 2n+1)个门延迟。

先行进位加法器（Carry Lookahead Adder, CLA）

先行进位加法器通过预计算所有可能的进位来加速加法过程。它不等待前一级的进位，而是利用辅助函数 $G_i=A_iB_i$（生成函数）和 $P_i=A_i+B_i$（传播函数）直接得出各级进位。

  • 公式推导（以 4 位为例）：

    • $C_1 = G_0 + P_0C_0$
    • $C_2 = G_1 + P_1C_1 = G_1 + P_1G_0 + P_1P_0C_0$
    • $C_3 = G_2 + P_2C_2 = G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0$
    • $C_4 = G_3 + P_3C_3 = G_3 + P_3G_2 + P_3P_2G_1 + P_3P_2P_1G_0 + P_3P_2P_1P_0C_0$

  • 特点：

    • 各进位之间无等待，可以同时独立产生。
    • 从 $C_0,A,B$ ，先得到 $G,P$（1 级门），再得到 $C_i$（1+2=3 级门），最后得到答案 F （3+3 = 6 级门）

局部（单级）先行进位加法器

为了降低成本，局部先行进位加法器仅对一部分位使用先行进位技术，其余部分采用传统的串行进位方法。这种方式可以在性能和成本之间找到平衡点。

例如，将四个 8 位先行进位加法器串联成一个 32 位的加法器。门延迟可以按照如下思路计算：

1
2
3
4
5
6
7
8

输入 A,B 得到 G,P ：1级门延迟
输入 C_0,G,P 得到 C_8 ：2级门延迟，此时开始计算第一部分的 F (同上，异或操作，3级门延迟，但是可以和后面并行，下同)
输入 C_8,G,P 得到 C_16 ：2级门延迟，此时开始计算第二部分的 F
输入 C_16,G,P 得到 C_24 ：2级门延迟，此时开始计算第三部分的 F
输入 C_24,G,P 得到所有的 C: 2级门延迟
通过所有的 C 计算 F：3级门延迟

因此总延迟为 1+2+2+2+2+3=12 级门延迟

n 位带标志加法器

这种类型的加法器不仅能够进行加法运算，还可以设置各种标志位来反映运算结果的状态，如溢出（OF）、符号（SF）、零（ZF）和进位/借位（CF）。

  • 标志位定义：
    • OF = $C_n$ ⊕ $C_{n-1}$ （溢出标志）
    • SF = $F_{n-1}$ （符号标志）
    • ZF = 当且仅当 F=0 时为 1 （零标志）
    • CF = $C_{out}$ ⊕ $C_{in}$ （进位/借位标志）

n 位整数加/减运算器

这类运算器支持带符号或无符号的 n 位整数之间的加法和减法操作，并且可以通过控制信号选择执行加法还是减法。

  • 操作模式：

    • 加法：当 Sub 为 0 时，执行 A + B。
    • 减法：当 Sub 为 1 时，执行 A - B，这相当于 A + (-B)，其中-B 是 B 的补码形式。

  • 硬件构成：

    • 包含 ALU（算术逻辑单元）、寄存器（如乘积寄存器 P、被乘数寄存器 X、乘数寄存器 Y）、计数器（循环次数计数器 Cn）、进位触发器（保存加法器的进位信号）等组件。
    • 控制逻辑确保正确的数据流动和同步操作。

向量运算

  • SIMD 指令用于图形和多媒体处理中的向量数据类型（如 8-bit, 16-bit）。
  • 饱和运算：在发生溢出时，结果是最大的可表示值，类似于音频中的削波或视频中的饱和。

乘法器

基本乘法器

  • 原理：基于长乘法算法，类似于手工计算乘法的方式。
  • 实现：通过多次执行“加+左移”操作来完成多位乘法。每次迭代中，如果乘数的当前位为 1，则将被乘数加到部分积上，并在每一步后将结果左移一位。

优化后的乘法器

  1. 寄存器和组件：

    • 被乘数寄存器 X：存放被乘数。
    • 乘积寄存器 P：开始时置为 0，结束时存放 64 位乘积的高 32 位。
    • 乘数寄存器 Y：开始时存放乘数，结束时存放 64 位乘积的低 32 位。
    • 进位触发器 C：保存加法器的进位信号。
    • 循环次数计数器 Cn：初值为 32，每循环一次减 1，当 Cn=0 时结束。
    • ALU：执行加法操作。

  2. 工作流程：

    • 每次循环中，ALU 对 P 和 X 的内容进行加法操作。
    • 结果被送回 P 寄存器，进位保存在 C 寄存器中。
    • P 和 Y 寄存器同步右移一位。
    • 循环次数计数器 Cn 每次减 1，直到 Cn=0 时结束。

运行示例：以 4 位为例，X=1011(11),Y=1001(9)

Cn PY(上一步) PY（加了还没右移） PY（加了且右移了，即这一步的结果）
4 00001001 10111001(左边加了 1011) 01011100
3 01011100 01011100(没加) 00101110
2 00101110 00101110(没加) 00010111
1 00010111 11000111(左边加了 1011) 01100011
0 结束 结束 01100011(99)

流水线方式的快速乘法器

  1. 部分积生成阶段：

    • 对于每一位乘数 Y[i]，如果 Y[i]=1，则将被乘数 X 左移 i 位后送入后续阶段；如果 Y[i]=0，则送入 0。
    • 这一步骤可以在同一时钟周期内并行地为所有乘数位生成相应的部分积。

  2. 加法阶段：

    • 每个部分积与前一阶段传递过来的部分积相加。
    • 使用多个加法器并行工作，每个加法器负责处理特定位置的部分积相加。
    • 加法结果包括本位和及进位输出，这些信息传递给下一个阶段。

  3. 移位和合并阶段：

    • 将所有加法结果正确对齐，并最终合并成完整的乘积。
    • 在这个阶段，还需要考虑高位进位的处理，确保最终结果的准确性。

例如：被乘数 X = 00001010 (10) ，乘数 Y = 00001011 (11)

  1. 部分积生成

在这个阶段，我们根据乘数 Y 的每一位，决定是否将被乘数 X 加入到当前部分积中。具体来说：

  • Y[0] = 1：部分积为 X « 0 = 00001010
  • Y[1] = 1：部分积为 X « 1 = 00010100
  • Y[2] = 0：部分积为 0
  • Y[3] = 1：部分积为 X « 3 = 01010000
  • Y[4] = Y[5] = Y[6] = Y[7] = 0：部分积为 0

所有这些部分积在第一个时钟周期内并行生成。

  1. 流水线加法

注意到加法显然满足结合律，我们可以通过分治并行的方式计算

1
2
3
4

00001010
00010100
00000000
01010000

因此，最终答案为 0000000001101110 = 0x006E = 110

阵列乘法器

原理上也是移位再运算，就是这里使用全加器而不是 ALU，每一级接收一个斜向（横向）进位，不再赘述

MIPS 中的乘法

乘法指令

MIPS 提供了专门用于执行乘法操作的指令，包括无符号和有符号两种类型：

  • mult rs, rt：有符号整数乘法，将寄存器rs和rt中的值相乘，并将 64 位结果存储到 HI/LO 寄存器对中。
  • multu rs, rt：无符号整数乘法，与mult类似，但处理的是无符号数。
  • mfhi rd：从 HI 寄存器读取 32 位高阶结果并存入通用寄存器rd。
  • mflo rd：从 LO 寄存器读取 32 位低阶结果并存入通用寄存器rd。
  • mul rd, rs, rt：只返回 32 位乘积的最低有效部分，直接存入指定的目标寄存器rd。

HI/LO 寄存器

HI 和 LO 是两个特殊的寄存器，用于保存乘法或除法指令的结果。具体来说：

  • HI 寄存器保存 64 位乘积的高 32 位。
  • LO 寄存器保存 64 位乘积的低 32 位。

这些寄存器不能通过常规的加载或存储指令访问，必须使用mfhi和mflo指令来读取它们的内容。

溢出检测

对于mult和multu指令，如果乘积超过了 32 位，则需要检查 HI 寄存器的值是否为非零来判断是否存在溢出。

除法与除法器

除法器设计

类似于乘法器，从高位向低位进行除法运算，如果被除数对应的位 < 除数，则该位为 0，否则为 1

为了避免比较操作，我们使用试商法，无论大小都先执行减法操作，如果被除数出现负数，则将除数加回被除数中

优化除法器等设计与乘法器基本一致。

MIPS 中的除法

MIPS 提供了专门用于执行除法操作的指令：

  • div rs, rt：有符号整数除法，将寄存器rs（被除数）除以rt（除数），并将商存储到 LO 寄存器，余数存储到 HI 寄存器。
  • divu rs, rt：无符号整数除法，功能同上，但将 rs,rt 视为无符号数。

浮点数

IEEE 754 标准

  • 制定背景：为了解决不同计算机系统间浮点数表示的差异性问题，提高科学计算代码的可移植性。

  • 广泛采用：现在几乎被所有现代计算机系统所采纳。

  • 组成部分：

    • 符号位 (S)：0 表示非负数，1 表示负数。
    • 指数部分 (Exponent)：单精度 8 位，双精度 11 位。
    • 尾数部分 (Fraction/Mantissa)：单精度 23 位，双精度 52 位。

  • 规范化：尾数总是有一个隐含的前导 1 位，即实际值为1.Fraction。

  • 偏置值 (Bias)：用于确保指数是非负的；单精度为 127，双精度为 1023。

  • 浮点数范围

    • 单精度：
      • 最小：$\pm 1.0 \times 2^{-126} \approx \pm 1.2 \times 10^{-38}$
      • 最大：$\pm 2.0 \times 2^{127} \approx \pm 3.4 \times 10^{38}$
    • 双精度：
      • 最小：$\pm 1.0 \times 2^{-1022} \approx \pm 2.2 \times 10^{-308}$
      • 最大：$\pm 2.0 \times 2^{1023} \approx \pm 1.8 \times 10^{308}$

  • 精度

    • 单精度：约等于 $2^{-23}$ ，相当于大约 7 位十进制数字的精度。
    • 双精度：约等于 $2^{-52}$ ，相当于大约 16 位十进制数字的精度。

  • 特殊情况

    • 非规范数 (Denormal Numbers)：当指数全为 0 时，允许表示更小的数，但精度逐渐降低。
    • 无穷大 (Infinity)：当指数全为 1 且尾数全为 0 时，表示正无穷或负无穷。
    • 非数字 (NaN)：当指数全为 1 且尾数不全为 0 时，表示未定义或非法结果，如0/0。

浮点数运算

  • 加法：
    • 对齐小数点（调整较小指数）。
    • 相加尾数。
    • 规范化结果并检查溢出/下溢。
    • 四舍五入。
  • 乘法：
    • 添加指数（考虑偏置）。
    • 乘以尾数。
    • 规范化结果并检查溢出/下溢。
    • 四舍五入。
    • 确定符号。

MIPS 中的浮点指令

  • 寄存器：FP 寄存器分为单精度（32 个）和双精度（配对使用）。
  • 常用指令：
    • add.s, sub.s, mul.s, div.s：单精度算术运算。
    • add.d, sub.d, mul.d, div.d：双精度算术运算。
    • c.xx.s, c.xx.d：比较指令（xx 是 eq, neq, lt, le, gt, ge）。
    • bc1t, bc1f：基于 FP 条件码的分支指令。
    • lwc1, swc1：加载和存储 FP 数据到内存。

处理器

CPU 简介

  • 性能指标：

    • 指令数量：由指令集架构(ISA)和编译器决定。
    • CPI (每条指令周期数) 和 时钟周期时间：由 CPU 硬件决定。

  • 指令执行过程

    • 取指：程序计数器(PC)指向指令存储器，取出指令。
    • 读寄存器：寄存器编号指向寄存器文件，读取寄存器值。
    • 使用 ALU 计算：如算术结果、内存地址或分支目标地址。
    • 访存：对于加载/存储指令访问数据存储器。
    • 更新 PC：PC 要么增加 4（下一条指令），要么转向新的目标地址。

控制逻辑设计基础

信息编码

  • 二进制表示：计算机中所有的信息都以二进制形式（0 和 1）进行编码。
  • 电压水平：低电压代表逻辑0，高电压代表逻辑1。每个比特位使用单独的一条导线来传输。
  • 单比特线：一个比特的信息通过一条导线传递。
  • 多比特数据：多个比特的数据则通过多条导线组成的总线同时传递。例如，32 位的数据将通过 32 条并行的导线传输。

组合逻辑与顺序逻辑

  • 组合逻辑元件：这些元件的操作结果仅依赖于当前输入信号的状态，它们没有内部状态记忆。常见的组合逻辑元件包括：

    • 与门 (AND-gate)：其输出 Y 等于输入 A 和 B 的逻辑与运算，即 Y = A & B。
    • 多路选择器 (Multiplexer)：基于选择信号 S 决定输出 Y 是从输入 I0 还是 I1 中选取，表达式为 Y = S ? I1 : I0。
    • 加法器 (Adder)：用于计算两个输入 A 和 B 的和，即 Y = A + B。
    • 算术逻辑单元 (ALU)：能够执行多种算术和逻辑操作，具体功能由输入 F 确定，比如加法、减法、小于判断等，即 Y = F(A, B)。

  • 顺序逻辑元件：这类元件不仅取决于当前输入，还依赖于之前的状态。主要的例子是寄存器。

    • 寄存器：寄存器是一种电路，用来保存数据直到需要更新为止。只有当时钟信号从 0 变为 1 时，寄存器才会更新其存储的值。

    • 带写入控制的寄存器：只有在写入控制信号为激活状态（通常是1）且在时钟边沿到来时，寄存器才会更新其内容。这种机制确保了即使有新数据可用，也不会立即覆盖旧数据，除非明确指示这样做。

  • 控制器的功能：它负责解码指令，并生成相应的控制信号来指导数据通路的动作。这涉及到协调各个硬件组件的工作，确保按照程序要求正确地读取数据、执行计算和写回结果。

时钟方法学 (Clocking Methodology)

  • 在时钟周期之间：组合逻辑电路会在时钟边缘之间的时段内对输入数据进行变换，产生输出结果。

  • 确定时钟周期：系统中最慢的部分（即具有最长延迟的路径）决定了整个系统的最快速度，因为这是保证所有操作都能完成所需的最小时间间隔。

  • 所有状态部件在上升沿写入信息：为了同步，所有的状态保持元件（如寄存器）都在时钟信号的上升沿更新其内容。

  • Latch Propagation Time + Longest Delay Path + Setup Time + Clock Skew：这些因素共同决定了一个完整的时钟周期长度，以确保数据稳定并且可以在下一个时钟周期开始前准备好。

  • 状态部件是唯一能存储信息的地方：所有的操作部件必须从状态部件接收输入，并将输出写回到状态部件中。这意味着任何数据处理的结果都需要经过状态部件来维持其持久性。

ALU 控制

控制信号的作用
  • RegDst：决定写入寄存器的编号是从rt字段还是rd字段获取。
    • 当为 0 时，写入寄存器号来自rt（适用于加载指令等）。
    • 当为 1 时，写入寄存器号来自rd（适用于 R 型指令）。
  • ALUSrc：确定第二个 ALU 操作数的来源。
    • 当为 0 时，第二操作数来自寄存器文件的输出（适用于 R 型指令）。
    • 当为 1 时，第二操作数是经过符号扩展后的指令低 16 位（适用于 I 型指令如加载、存储和分支）。
  • MemtoReg：指定写回寄存器的数据来源。
    • 当为 0 时，数据来自 ALU 的结果（适用于 R 型指令和存储指令）。
    • 当为 1 时，数据来自数据存储器（适用于加载指令）。
  • RegWrite：控制是否将数据写入寄存器文件。
    • 当为 0 时，不执行写入操作。
    • 当为 1 时，将指定的数据写入寄存器。
  • MemRead：控制是否从数据存储器读取数据。
    • 当为 0 时，不执行读取操作。
    • 当为 1 时，从内存读取数据并将其放置在读数据输出上。
  • MemWrite：控制是否向数据存储器写入数据。
    • 当为 0 时，不执行写入操作。
    • 当为 1 时，将指定的数据写入内存。
  • Branch：控制是否根据分支条件更新 PC。
    • 当为 0 时，PC 按顺序递增。
    • 当为 1 时，根据分支条件计算新的 PC 值。
  • ALUOp：指示 ALU 应执行的操作类型。
    • 使用 2 位编码表示不同的操作，例如加法、减法等。
  • PCSrc：决定 PC 的下一个值。
    • 当为 0 时，PC 增加 4 指向下一指令。
    • 当为 1 时，PC 被替换为分支目标地址。
控制信号表
信号名 R 型 lw (加载) sw (存储) beq (相等分支)
RegDst 1 0 x x
ALUSrc 0 1 1 0
MemtoReg 0 1 x x
RegWrite 1 1 0 0
MemRead 0 1 0 0
MemWrite 0 0 1 0
Branch 0 0 0 1
ALUop1 1 0 0 0
ALUop0 0 0 0 1

注：

  • x 表示该信号对于特定指令无关紧要或未定义。

流水线

流水线模型

流水线是一种并发处理机制，它将一条指令的执行过程分割成若干个步骤（或阶段），每个步骤由不同的硬件单元完成。这样，在一个时钟周期内，不同的指令可以在不同的阶段同时进行。

  • 五阶段流水线模型：
    • IF (Instruction Fetch)：从内存中取出指令。
    • ID (Instruction Decode & Register Read)：解码指令并读取所需的操作数。
    • EX (Execute)：执行操作或计算地址。
    • MEM (Memory Access)：访问数据存储器以加载或存储数据。
    • WB (Write Back)：将结果写回寄存器文件。

冒险类型及解决方案

  1. 结构冒险 (Structural Hazard)

  • 原因： 结构冒险发生在多个指令尝试同时访问同一硬件资源时。例如，在一个周期内有两个指令需要访问同一个功能单元（如 ALU），或者在一个周期内同时有指令取指和数据存储器访问的需求。

  • 例子： 假设有一个 MIPS 流水线，其中只有一个数据存储器用于加载和存储操作。如果一条加载指令和一条存储指令在同一周期内试图访问这个唯一的存储器，就会发生结构冒险。

  • 解决方法：

    • 分离指令和数据存储器：使用独立的指令缓存（I-cache）和数据缓存（D-cache）。这样可以避免指令获取与数据访问之间的冲突。
    • 增加资源数量：为常用的功能单元（如 ALU）增加额外的副本，确保每个周期可以处理更多的指令。
  1. 数据冒险 (Data Hazard)

  • 原因： 数据冒险发生在当前指令依赖于前一条指令的结果，但该结果尚未准备好。这种依赖关系可能是因为寄存器之间的读写顺序不正确，导致后续指令无法获得正确的输入值。

  • 例子： 考虑以下两条 MIPS 指令：

    1
2

    add $t0, $s0, $s1    # $t0 = $s0 + $s1
sub $t1, $t0, $s2    # $t1 = $t0 - $s2

    在这条sub指令执行之前，add指令的结果还没有被写入寄存器t0，因此sub指令不能立即获取到正确的t0值。

  • 解决方法：

    • 转发（Forwarding）：当检测到数据依赖时，直接将 ALU 计算出的结果传递给后续指令，而不是等待其写入寄存器后再读取。
    • 插入气泡（Stall/Bubble Insertion）：如果无法进行转发，则在流水线中插入一个空操作周期（即“nop”），以确保所有依赖的数据都已准备好。
  1. 控制冒险 (Control Hazard)

  • 原因： 控制冒险主要由分支指令引起，因为分支改变了程序的正常执行路径，使得难以预测下一条要执行的指令是什么。这会导致流水线中的指令序列被打乱，甚至可能取错了指令。

  • 例子： 考虑一个简单的条件分支：

    1

    beq $s0, $s1, target   # 如果$s0 == $s1，则跳转到target标签处

    当处理器到达这条beq指令时，它不知道是否会发生跳转，直到比较了两个寄存器的内容之后才能确定。这意味着在此期间，流水线可能会继续预取错误的指令。

  • 解决方法：

    • 分支预测（Branch Prediction）：
      • 静态预测：基于常见的编程模式来猜测分支的行为，例如向后跳转通常会被认为是采取的（taken），而向前跳转则通常不采取。
      • 动态预测：记录每个分支的历史行为，并根据这些信息做出更准确的预测。例如，2 位饱和计数器可以根据最近几次分支的结果调整预测方向。
    • 延迟分支（Delayed Branches）：在分支指令之后放置一条或多条无关紧要的指令(如"nop")，以掩盖分支决策的时间。
    • 快速分支决策：尽量早地计算分支条件，(MIPS)如在 ID 阶段就判断分支是否成立，以便尽早开始正确的指令获取。

流水线性能评估

  • 加速比（Speedup）：

    • 如果所有阶段平衡，则加速比等于阶段数；不平衡则加速比会减少。
    • 加速比公式：$ \text{Speedup} = \frac{\text{非流水线的时间}}{\text{流水线的时间}} $

异常

  • 异常（Exception）： 发生于 CPU 内部，通常由非法操作或特定条件触发，如未定义指令、溢出、系统调用等。
  • 中断（Interrupt）： 来自外部 I/O 控制器，例如定时器、键盘输入或其他外设发出的信号，用于通知 CPU 有需要立即处理的事件。

MIPS 中的异常处理机制

  • System Control Coprocessor (CP0)：

    在 MIPS 架构中，异常由系统控制协处理器（CP0）管理。CP0 负责保存引起异常的指令的 PC，并跳转到异常处理程序。

  • 关键寄存器：

    • EPC (Exception Program Counter)：保存导致异常的指令的地址（实际上是 PC+4），以便异常处理后可以返回到该位置继续执行。
    • Cause Register：记录异常的原因代码，帮助确定发生了哪种类型的异常。

  • 异常处理入口地址： MIPS 规定了固定的异常处理入口地址8000 0018，所有异常都将跳转到这里开始处理。

处理步骤

  • 保存状态信息：

    当异常发生时，当前指令的 PC 值被保存到 EPC 寄存器中，同时异常原因被记录到 Cause 寄存器。

  • 跳转到处理程序：

    CPU 会自动将程序计数器（PC）设置为异常处理入口地址8000 0018，开始执行异常处理程序。

  • 执行处理程序：

    处理程序读取 Cause 寄存器以确定异常类型，并采取相应的措施，如纠正错误、终止程序或报告问题。

  • 恢复执行： 如果异常是可以恢复的（即重启式的异常），则可以通过 EPC 寄存器返回到异常发生的点继续执行；否则，程序可能需要终止或进行其他处理。

精确异常（Precise Exceptions）

  • 定义：

    • 精确异常确保即使在流水线环境中也能准确报告异常发生的位置。这意味着每个指令都按序完成，异常发生在预期的地方。

  • 实现方式：

    流水线必须能够识别并处理异常，确保在异常发生时保存足够的状态信息，以便恢复或调试。

  • 优点： 提供了更强的调试支持和更可靠的程序行为，因为每个异常都能明确地指向具体的指令。

非精确异常（Imprecise Exceptions）

  • 定义：

    非精确异常简化了硬件设计，但在复杂管道中增加了软件处理的难度。异常可能不会精确对应到引发它的指令。

  • 实现方式：

    硬件只需停止流水线并保存基本状态信息，后续的细节由软件处理程序来确定哪些指令受到了影响。

  • 适用场景： 适用于深度和超标量流水线，在这些架构中维持精确异常变得非常复杂。

向量化中断（Vectored Interrupts）

  • 定义：

    向量化中断根据不同的中断源使用不同的处理程序地址，从而加快响应速度。

  • 工作原理：

    中断发生时，CPU 直接跳转到预先配置好的处理程序地址，而不是统一跳转到一个固定的入口点再分发。

  • 示例： 未定义指令异常跳转到8000 0000，溢出异常跳转到8000 0180，等等。

异常处理中的性能考虑

  • 最小化停顿：

    设计良好的异常处理机制应尽量减少对正常程序执行的影响，避免不必要的停顿或重试。

  • 快速恢复：

    对于可恢复的异常，应该提供快速且有效的恢复路径，使得程序可以尽快恢复正常运行。

  • 硬件与软件协同： 异常处理往往需要硬件和软件的紧密配合，硬件负责初步检测和状态保存，而软件负责具体的处理逻辑。

指令级并行（ILP）

  • 定义：

    ILP 是指在单个程序中同时执行多个指令的能力，通过增加每个时钟周期内完成的有用操作数量来提升性能。

  • 实现方式：

    • 加深流水线：将指令处理过程分解为更多的阶段，使得每条指令可以在不同阶段并行处理。
    • 多发射：在一个时钟周期内发出多条指令，充分利用硬件资源。
    • 超标量（Superscalar）：设计能够在一个时钟周期内执行多条指令的处理器架构。

多发射（Multiple Issue）

  • 静态多发射（Static Multiple Issue）：

    • 编译器分组：编译器负责将指令打包成“发射包”，确保它们可以并发执行。
    • 移除冒险：编译器必须移除一些或全部的数据冒险，并可能需要填充 NOP 以保持正确性。

  • 动态多发射（Dynamic Multiple Issue）：

    • CPU 运行时选择：CPU 决定每个周期发出多少指令，尽量避免结构和数据冒险。
    • 乱序执行（Out-of-Order Execution）：允许 CPU 在不影响结果的前提下乱序执行指令，从而更好地利用硬件资源。
    • 保留站（Reservation Stations）和重排序缓冲区（Reorder Buffer, ROB）：这些结构帮助管理指令的依赖关系，并确保最终提交的结果按程序顺序。

推测执行（Speculative Execution）

  • 定义：

    • 推测执行是指通过猜测分支方向或加载结果来提前启动操作，如果猜测错误则回滚。

  • 目的：

    • 减少因等待分支条件或内存访问而产生的延迟，提高指令吞吐量。

  • 类型：

    • 分支预测（Branch Prediction）：使用静态或动态方法预测分支的方向，减少控制冒险的影响。
    • 加载推测（Load Speculation）：提前执行加载指令，即使目标地址尚未确定。

  • 挑战：

    • 当推测执行的指令发生异常时，需要有机制确保异常处理的正确性，例如保存足够的状态信息以便恢复。

编译器与硬件协同推测

  • 编译器推测：

    编译器可以通过重排指令来进行推测，例如通过循环展开（Loop Unrolling）和代码调度（Code Scheduling）来暴露更多并行性，减少循环控制开销。

  • 硬件推测： 硬件可以在运行时查看指令流并缓存结果，例如使用分支目标缓冲区（Branch Target Buffer, BTB）来加速分支决策。

动态调度 CPU 结构

  • 内部结构：

    • 保留站（Reservation Stations）：用于暂存等待执行的操作数，直到所有依赖项都准备好。
    • 重排序缓冲区（Reorder Buffer, ROB）：确保指令提交结果时仍然保持有序，即使它们是在乱序执行的情况下完成的。

  • 寄存器重命名： 使用保留站和 ROB 有效地提供了寄存器重命名功能，避免了写后读（RAW）、读后写（WAR）和写后写（WAW）冒险。

大容量和高速度——开发存储器层次结构

局部性原理（Principle of Locality）

  • 时间局部性（Temporal Locality）：最近访问过的项目很可能在不久后再次被访问。

  • 空间局部性（Spatial Locality）：靠近最近访问位置的数据项也可能会很快被访问。

  • 利用局部性

    • 将所有数据存放在磁盘上，并将最近访问过（及其附近的）项目复制到更小的 DRAM 内存中。
    • 主存中的数据会被进一步复制到更小、更快的 SRAM 缓存中，该缓存直接连接到 CPU。

不同的存储技术

基本概念

  • 块（Block）：数据传输的单位，可能包含多个字。
  • 命中（Hit）：当访问的数据存在于较高层级时，称为命中，否则称为未命中（Miss）。
  • 命中率（Hit Ratio）：命中率定义为命中的次数与总访问次数的比例；未命中率（Miss Ratio）则是未命中的次数与总访问次数的比例，等于 1 - 命中率。

DRAM 技术（DRAM Technology）

  • 数据存储方式：数据以电荷形式存储在电容器中，单个晶体管用于访问这些电荷。

  • 刷新需求：由于电容会逐渐失去电荷，必须周期性地进行刷新操作。刷新通常在读取内容后立即将其写回。

  • 高级 DRAM 组织（Advanced DRAM Organization）

    • 矩形阵列排列：DRAM 中的位以矩形阵列形式组织，一次访问整个行。
    • 突发模式（Burst Mode）：可以连续提供同一行内的多个字，减少延迟。
    • 双倍/四倍数据速率（DDR/QDR）：DDR DRAM 可以在时钟上升沿和下降沿传输数据，QDR 则进一步区分输入和输出，提高了数据传输效率。

  • 主存的主要性能指标

    主存是按字节连续编址的：每个存储单元为 1 个字节（8 个二进制位）。

    • 存储容量：所包含的存储单元总数，单位通常是 MiB 或 GiB。
    • 存取时间（$T_A$）：从 CPU 发出地址到主存读出数据并送到 CPU 所需的时间，分为读取时间和写入时间，单位是纳秒（ns）。
    • 存储周期（$T_{MC}$）：两次连续访问所需的最小间隔，等于存取时间加上下一次存取开始前所要求的附加时间，因为存储器电路需要一段时间来恢复稳定状态。

  • DRAM 性能因素（DRAM Performance Factors）

    • 行缓冲（Row Buffer）：允许并行读取和刷新多个字，提高带宽。
    • 同步 DRAM（Synchronous DRAM）：支持突发访问，无需每次发送地址，改善了带宽。
    • DRAM 银行（Banking）：允许多个 DRAM 同时访问，增加了带宽。
CPU 与存储器之间的通信方式
  • 异步方式（Asynchronous）：
    • CPU 发送地址到地址线，主存进行地址译码。
    • CPU 发出读命令，然后等待存储器发回“完成”信号。
    • 主存完成后发送“完成”信号给 CPU，CPU 再从数据线取数。
  • 同步方式（Synchronous）：
    • CPU 和主存由统一时钟信号控制，无需应答信号。
    • 主存总是在确定的时间内准备好数据，CPU 在固定时间内取数据。
    • 存储器芯片必须支持同步方式，确保在特定时间窗口内完成操作。

Flash 存储（Flash Storage）

  • 非易失性半导体存储：比磁盘快 100 至 1000 倍，但价格介于磁盘和 DRAM 之间。
  • NOR 闪存：随机读写访问，用于嵌入式系统的指令存储。
  • NAND 闪存：更密集且便宜，适用于 USB 驱动器、媒体存储等。
  • 磨损均衡（Wear Leveling）：通过重映射数据到较少使用的块来延长寿命。

磁盘存储（Disk Storage）

磁盘结构

  • 磁道（Track）：磁盘表面被划分为许多同心圆，每个同心圆称为一个磁道。最外面的是 0 磁道，每个磁道都有一个编号。

  • 扇区（Sector）：每个磁道被划分为若干段，每段称为一个扇区。早期的扇区大小为 512 字节，现代磁盘已迁移到更大的 4096 字节（通常称为 4K 扇区）。国际硬盘设备与材料协会（IDEMA）将这种格式化操作称为高级格式化。
    每个扇区记录了以下信息：

    • 扇区 ID：标识扇区位置。
    • 数据：实际存储的数据，通常是 512 字节或 4096 字节。
    • 错误校正码（ECC）：用于隐藏缺陷和纠正记录错误。
访问过程
  • 排队延迟（Queuing Delay）：如果有其他访问请求正在处理中，则新请求需要等待。
  • 寻道（Seek）：移动读写头到指定磁道。
  • 旋转延迟（Rotational Latency）：等待磁盘旋转至读写头对准目标扇区。
  • 数据传输（Data Transfer）：从磁盘读取或写入数据。
  • 控制器开销（Controller Overhead）：处理和管理 I/O 请求的时间。

磁盘访问示例（Disk Access Example）

假设条件如下：

  • 扇区大小：512 字节
  • 转速：15,000 转/分钟 (rpm)
  • 平均寻道时间：4 毫秒
  • 数据传输速率：100 MB/s
  • 控制器开销：0.2 毫秒

计算平均读取时间：

$$ \text{平均读取时间} = \text{寻道时间} + \frac{1}{2} \times \left(\frac{60}{15,000}\right) \text{秒} + \frac{512}{100 \times 10^6} \text{秒} + 0.2 \text{毫秒} $$

$$ \text{平均读取时间} = 4 \text{ms} + 2 \text{ms} + 0.005 \text{ms} + 0.2 \text{ms} = 6.2 \text{ms} $$

假设目标扇区随机分布在磁盘上，那么从统计角度来看，平均等待时间将是磁盘旋转一圈所需时间的一半。

如果实际平均寻道时间为 1 毫秒，则：

$$ \text{平均读取时间} = 1 \text{ms} + 2 \text{ms} + 0.005 \text{ms} + 0.2 \text{ms} = 3.2 \text{ms} $$

磁盘存储器的连接
  • 磁盘控制器通过 I/O 总线连接到系统，I/O 总线与其他总线（如系统总线、存储器总线）之间使用桥接器连接。
  • 磁盘最小读写单位是扇区，采用直接存储器存取（DMA）方式进行数据输入输出，确保数据不通过 CPU 而直接在外部设备和主存之间交换。
  • DMA 接口控制外设与主存之间的直接数据交换，专门的 DMA 控制器负责总线进行 DMA 传送。
磁盘性能问题（Disk Performance Issues）
  • 制造商宣称的平均寻道时间：基于所有可能的寻道距离，但实际上由于局部性和操作系统调度，实际平均寻道时间通常较小。
  • 智能磁盘控制器：分配物理扇区以呈现逻辑扇区接口给主机，例如 SCSI、ATA、SATA 标准。
  • 磁盘缓存：预取可能访问的扇区，以避免寻道和旋转延迟。
  • 优化因素：
    • 局部性：程序倾向于重复访问相同或相邻的数据块。
    • 操作系统调度：减少不必要的磁头移动。
    • 并行访问：多个磁盘可以同时工作，提高带宽。
    • 缓存机制：磁盘驱动器内部的缓存可以加快数据读取速度。

缓存内存（Cache Memory）

  • 定义：最接近 CPU 的存储层，用于存储最近或频繁访问的数据及其地址。
  • 作用：减少 CPU 访问主存的时间，提高系统性能。

直接映射缓存（Direct Mapped Cache）

  • 工作原理：每个块只能存储在一个特定的位置，使用低阶地址位确定位置。
  • 计算方法：(块地址) 模 (#Blocks in cache)，（类似于哈希映射），#Blocks 是 2 的幂次方，使用低阶地址位。
标签和有效位（Tags and Valid Bits）
  • 标签（Tag）：用于识别具体块的高阶地址位。
  • 有效位（Valid Bit）：指示该位置是否有有效数据（1=存在，0=不存在）。
  • 初始状态：所有位置都无效。
缓存示例

8-blocks, 1 word/block, direct mapped：

这里指的都是字地址（因为每个块 1 字，所以块地址就是字地址），而非字节地址

  • 初始状态：所有位置无效。
  • 访问 10110b：需要访问 110b 位置的缓存（因为缓存为 8block 即 3 位，低 3 位即为数据在缓存中的位置），未命中，此时将 110b 位置的缓存块替换为内存中 10110b 的数据，Tag 位置为 10b（内存地址的高位），Valid Bit 设为 1
  • 访问 11010b：同上
  • 访问 11010b：命中，直接访问缓存块，无需替换
  • 访问 10010b：未命中（Valid Bit = 1 但是 Tag != 10），将缓存的 010b 块替换为内存中 11010b 的数据，Tag 位置为 10b，Valid Bit 设为 1
直接映射缓存的位数计算

假设缓存由 $2^n$ 个块组成，则需要使用 $n$ 位为这些块编址。每个块包含 $2^m$ 个字，即 $2^{m+2}$ 个字节的数据，则需要 $m+2$ 位为这些字节编址。

在一个 32 位的地址中，除去用于索引和块内地址的位之后，剩下的位用来作为标记（Tag）。所以每个块的标记字段占 $32-(n+m+2)$ 位。

对于直接映射缓存，每个缓存行需要存储数据、标记和一个有效位（valid bit）。因此，对于 $2^n$ 个块，总的位数可以计算为：

  • 数据部分：$2^n \times 32 \times 2^m$（因为每个字有 32 位）
  • 标记字段：$2^n \times (32-n-m-2)$
  • 有效位：$2^n * 1$ 这些加起来就是直接映射缓存的总位数。

例子：当 $n=10$ 且 $m=0$ 时，意味着缓存有 $2^{10} = 1024$个块，每个块只有一个字（4 字节）。在这种情况下：

数据占用 $1024 \times 4 = 4096$ 字节，即 4 KB。

标记和有效位字段总共占用 $1024 * ((32-10-0-2)+1) = 1024 * 21 = 21504$ 位，即 2.625KB

通常来说，当我们提到缓存大小时，我们指的是它能存储的数据量，而不是包括标记和有效位在内的总大小。因此，即使实际使用的空间可能更多，人们还是习惯称其为 4 KB Cache，指的就是它可以存储 4 KB 的数据。

块大小考虑（Block Size Considerations）
  • 较大的块：可以降低未命中率，因为利用了空间局部性。
  • 较小的块：在固定大小的缓存中，更大的块意味着更少的块数量，意味着更大的竞争，增加了未命中率。
当缓存未命中时……

如果 CPU 请求的数据或指令不在缓存中，则发生了缓存未命中。此时需要采取额外步骤来获取所需的数据或指令，这通常会导致性能下降。

当发生缓存未命中时，CPU 流水线可能会被阻塞（stall），即暂停进一步的指令执行，直到缺失的数据或指令被加载到缓存中。

在缓存未命中后，系统会尝试从缓存层次结构的下一级（通常是更慢但更大的缓存或主存储器）中获取整个块的数据，并将其加载到当前级别的缓存中。这样做是为了提高未来访问相同数据的可能性，从而减少未来的缓存未命中。

如果未命中的是指令缓存（I-cache），这意味着 CPU 需要的下一条指令不在缓存中。这时，CPU 必须从主存或其他更高级别的缓存中重新获取指令，之后重新开始指令的取指过程。一旦缺失的指令被加载到指令缓存中，CPU 就可以重新开始指令取指，继续正常的指令执行流程。

如果未命中的是数据缓存（D-cache），意味着 CPU 需要的数据不在缓存中。在这种情况下，CPU 必须等待数据从更慢的存储层级加载进来。一旦缺失的数据被加载到数据缓存中，CPU 就可以完成对这些数据的访问操作，例如读取或写入。然后，程序可以按照预期继续执行。

写数据方法
直写（Write-Through）
  • 定义：更新缓存的同时也更新内存，保证一致性但写操作较慢。
  • 解决方案：写缓冲区（Write Buffer），允许 CPU 立即继续执行，除非缓冲区已满。
  • 写分配行为：
    • Write Allocate：在这种情况下，如果发生写未命中，缓存会先从主存中获取相应的块，然后执行写操作。这适用于那些可能很快会被再次访问的数据块。
    • No Write Allocate：对于写未命中，只更新主存，不加载到缓存。这适用于那些不太可能立即被再次访问的数据块。
回写（Write-Back）
  • 定义：仅更新缓存，当替换脏块时才写回内存，提升写性能。
  • 脏位（Dirty Bit）：跟踪是否块已被修改。
  • 好处：减少了写入次数，提高了性能。可以使用写缓存来读取脏块中被修改的内容。
  • 写分配行为： 在回写模式下，当发生写未命中时，一般会选择将缺失的块加载到缓存中。

主存对缓存的支持（Main Memory Supporting Caches）

  1. 主存技术：

    • 使用 DRAM 构建主存。
    • DRAM 宽度固定（例如，1 个字），通过固定宽度的时钟总线连接。
    • 总线时钟频率通常慢于 CPU 时钟。

  2. 缓存块读取示例：

    • 地址传输：1 个总线周期。
    • 每次 DRAM 访问：15 个总线周期。
    • 数据传输：每个数据 1 个总线周期。
    • 对于 4 字节块，使用 1 字宽的 DRAM，缺页惩罚为 65 (发送地址 1 个，访问数据 4*15=60 个，传输数据 4*1=4 个)个总线周期，带宽为 0.25 字节/周期。

  3. 优化方案：

    • 增加总线宽度：从 1 字宽到 4 字宽可以显著减少传输时间（从 65 个总线周期降到 17 个总线周期）。
    • 交错存储体（Interleaved Banks）：采用 4 个交错存储体，可以在一定程度上提高效率（20 个总线周期）。

测量和改善缓存性能 (Measuring and Improving Cache Performance)

  1. CPU 时间的组成：

    包括程序执行周期（含缓存命中时间）和内存停顿周期（主要来自缓存未命中）。

  2. 平均内存访问时间 (Average Memory Access Time, AMAT)：

    • 计算公式：AMAT = 命中时间 + 缺页率 × 缺页惩罚。
    • 例子：如果 CPU 有 1ns 的时钟周期，命中时间为 1 个周期，缺页惩罚为 20 个周期，且缓存缺页率为 5%，那么 AMAT 为 1 + 20 * 0.05 = 2ns。
缓存性能实例分析
  • I-cache miss rate (指令缓存未命中率)：2% （即 2% 的指令会导致缓存未命中。）
  • D-cache miss rate (数据缓存未命中率)：4% （即 4% 的数据加载或存储操作会导致缓存未命中。）
  • Miss penalty (未命中惩罚)：100 （即每次未命中会额外花费 100 个周期来从主存中获取数据。）
  • Base CPI (理想的缓存情况下基本 CPI)：2（即在没有任何缓存未命中的理想情况下，每个指令需要 2 个周期。）
  • Load & stores are 36% of instructions (加载和存储指令占所有指令的比例)：36% （即 36% 的指令是加载或存储操作。）

根据给定的数据：

  • 对于 I-cache，未命中导致的额外周期数为 0.02 * 100 = 2 个周期。
  • 对于 D-cache，考虑到只有 36% 的指令是加载或存储，所以未命中导致的额外周期数为 0.36 * 0.04 * 100 = 1.44 个周期。

将这些值加到基础 CPI 上，得到实际的 CPI:

  • Actual CPI = Base CPI + I-cache miss cycles + D-cache miss cycles
  • Actual CPI = 2 + 2 + 1.44 = 5.44

这意味着，在考虑缓存未命中的情况下，实际的 CPI 是 5.44，而没有缓存未命中时的理想 CPI 是 2。因此，由于缓存未命中，CPU 的实际速度比理想情况慢了大约 2.72 倍（5.44/2）。

关联缓存 (Associative Caches)

完全关联缓存 (Fully Associative Cache)
  • 允许一个给定的块存储在任何缓存位置。
  • 需要同时搜索所有条目以找到匹配项。
  • 每个条目需要一个比较器，成本较高。
N 路组相联缓存 (n-way Set Associative Cache)
  • 每个集合包含 n 个条目。
  • 块号决定其属于哪个集合。
  • 在给定集合内同时搜索所有条目。
  • 使用 n 个比较器，成本较低于完全关联缓存。
关联度对性能的影响
  • 增加关联度可以减少未命中率，但收益递减。
  • 例如，对于一个 64KB 的数据缓存（D-cache），使用 16 字的块大小，SPEC2000 基准测试显示：
    • 1 路：10.3% 的未命中率
    • 2 路：8.6%
    • 4 路：8.3%
    • 8 路：8.1%
标记位数与额外空间开销
  • 关联度越高，总的标记位数越多，导致额外的空间开销增加。
  • 对于 4096 个块、4 字块大小和 32 位地址的缓存：
    • 直接映射缓存：(4096 * (32 - 12 - 4) = $2^{12+4} = 2^{16}$ bit = 64) Kib 标记位
    • 2 路组相联：2048 个组，每个 tag 占 32 - 11 - 4 = 17 位，共 2048 * 2 * 17 = 68Kib
    • 4 路组相联：72 Kib 标记位
    • 完全关联：112 Kib 标记位

替换策略 (Replacement Policy)

  1. 直接映射缓存 (Direct Mapped Cache)： 无选择，因为每个块只能放置在一个特定的位置。

  2. 组相联缓存 (Set Associative Cache)：

    • 如果有无效条目，则优先选择无效条目。
    • 否则，在集合内的条目中进行选择：
      • 最近最少使用（LRU, Least-Recently Used）：
        • 选择最长时间未使用的条目。
        • 对于 2 路组相联简单，对于 4 路组相联仍然可管理，但对于更多路则变得复杂。
      • 随机选择 (Random)：
        • 提供与 LRU 相似的性能，特别是在高关联度时。

多级缓存 (Multilevel Caches)

  1. 多级缓存的结构：

    • 一级缓存 (L1 Cache)：直接连接到 CPU，特点是小而快。
    • 二级缓存 (L2 Cache)：服务于来自一级缓存的未命中请求，比一级缓存大但稍慢，仍然比主存快。
    • 三级缓存 (L3 Cache)：一些高端系统包括 L3 缓存，进一步服务来自 L2 缓存的未命中请求。

  2. 各级缓存的设计重点：

    • L1 缓存：
      • 专注于最小化命中时间，因为 L1 缓存直接影响 CPU 性能。
      • 通常较小且块大小也较小。
    • L2 缓存：
      • 专注于降低未命中率以避免访问主存，因为 L2 未命中会显著增加延迟。
      • 命中时间对整体性能的影响相对较小。
    • 结果：
      • L1 缓存通常比 L2 缓存小。
      • L1 块大小通常小于 L2 块大小。
多级缓存性能实例

  • 给定条件：

    • CPU 基本 CPI = 1
    • 时钟频率 = 4GHz
    • 每条指令的未命中率 = 2%
    • 主存访问时间 = 100ns

  • 仅有一级缓存的情况：

    • 缺页惩罚 100ns,即 100ns / 0.25ns = 400 个周期
    • 实际 CPI = 1 + 0.02 × 400 = 9

  • 添加二级缓存后的情况：

    • L2 缓存访问时间 = 5ns
    • 全局主存未命中率 = 0.5%

  • L1 未命中但 L2 命中的情况：

    • 惩罚 = 5ns / 0.25ns = 20 个周期

  • L1 和 L2 都未命中（即主存访问）的情况：

    • 额外惩罚 = 400 个周期

  • 综合计算：

    • CPI = 1 + 0.02 × 20 + 0.005 × 400 = 3.4
    • 性能提升比例 = 9 / 3.4 ≈ 2.6

根据课件中的内容，以下是关于高级 CPU 的交互、软件的交互以及通过阻塞进行软件优化的知识点总结：

与高级 CPU 的交互 (Interactions with Advanced CPUs)

  • 现代 CPU 特性：能够在缓存未命中期间继续执行其他不依赖于未命中数据的指令。
  • 机制：挂起的内存访问停留在加载/存储单元中；依赖这些访问结果的指令在保留站（reservation stations）等待；独立的指令则继续执行。
  • 效果：由于程序数据流的影响，缓存未命中对性能的影响变得难以预测和分析。
  • 工具：通常使用系统模拟来评估这种复杂行为。

与软件的交互 (Interactions with Software)

  1. 未命中依赖性：

    • 缓存未命中率取决于内存访问模式，包括算法行为和编译器优化后的内存访问模式。

  2. 影响因素：

    • 算法设计：不同的算法可能导致不同的内存访问模式，从而影响缓存效率。

    • 编译器优化：编译器可以通过优化内存访问顺序来提高缓存利用率。

    • 示例：矩阵乘法 (DGEMM, Double precision GEneral Matrix Multiply)：

      • 原始代码：

        1
2
3
4
5
6

        for(int j = 0; j < n; ++j) {
    double cij = C[i + j * n];
    for(int k = 0; k < n; k++)
        cij += A[i + k * n] * B[k + j * n];
    C[i + j * n] = cij;
}

      • 改进后的版本：

         1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

        #define BLOCKSIZE 32
void do_block(int n, int si, int sj, int sk, double* A, double* B, double* C) {
    for(int i = si; i < si + BLOCKSIZE; ++i)
        for(int j = sj; j < sj + BLOCKSIZE; ++j) {
            double cij = C[i + j * n];
            for(int k = sk; k < sk + BLOCKSIZE; k++)
                cij += A[i + k * n] * B[k + j * n];
            C[i + j * n] = cij;
        }
}
void dgemm(int n, double* A, double* B, double* C) {
    for(int sj = 0; sj < n; sj += BLOCKSIZE)
        for(int si = 0; si < n; si += BLOCKSIZE)
            for(int sk = 0; sk < n; sk += BLOCKSIZE)
                do_block(n, si, sj, sk, A, B, C);
}

        这种方法通过限制每次处理的数据块大小，使得更多操作可以在缓存中完成，减少了主存访问频率，从而提高了整体性能。

可靠性与可用性

可靠性 (Dependability)

  • 平均无故障时间（MTTF, Mean Time To Failure）。

  • 平均修复时间（MTTR, Mean Time To Repair）。

  • 平均故障间隔时间（MTBF, Mean Time Between Failures）：

    • MTBF = MTTF + MTTR。

  • 年故障率（AFR, Annual Failure Rate）：

    • 对于给定的 MTTF，一年内预期会失败的设备百分比。
    • 当 MTTF 非常大时，AFR 能提供更好的直觉理解。

  • 示例：磁盘的 MTTF vs. AFR

    • 某些现代磁盘声称有 1,000,000 小时的 MTTF。
    • 1,000,000 小时相当于约 114 年，看似几乎不会出问题。
    • 在大规模数据中心（如拥有 50,000 台服务器，每台服务器 2 个磁盘），每年会有大约 876 个磁盘失效，即每天平均超过 2 个磁盘失效。

可用性 (Availability)

  1. 定义：
    • Availability = MTTF / (MTTF + MTTR)。
  2. 提高可用性的方法：
    • 增加 MTTF：通过故障避免、容错和预测。
    • 减少 MTTR：改进诊断和修复工具及流程。
  3. “9”的概念：
    • 表示每年的可用性级别：
      • 一个 9：90% -> 每年 36.5 天的修复时间。
      • 两个 9：99% -> 每年 3.65 天的修复时间。
      • 三个 9：99.9% -> 每年 5.26 分钟的修复时间。
      • 四个 9：99.99% -> 每年 52.6 秒的修复时间。
      • 五个 9：99.999% -> 每年 5.26 秒的修复时间。

汉明码 (Hamming Code)

汉明距离： 两个比特模式之间不同比特的数量。

  • 最小距离=2 提供单比特错误检测。
  • 最小距离=3 提供单比特错误纠正和双比特错误检测。
奇偶校验法

使 0 和 1 的位数均为奇数/偶数

  • Hamming 距离 d=2：两个数若有奇数位不同，则它们相应的校验位就不同；若有偶数位不同，则虽校验位相同，但至少有两位数据位不同。因而任意两个编码之间至少有两位不同。
  • 只能发现奇数位出错，不能发现偶数位出错：例如一个字节传输时有两个位出错了，就无法发现错误。
  • 不能确定发生错误的位置，不具备纠错能力。
  • 开销小，适用于校验 1 字节长的代码，常用于存储器读写检查或按字节传输的数据校验。
SEC 编码

  • 对于 SEC 编码，最小汉明距离为 3，这意味着可以检测到最多 2 个比特的错误，并且可以纠正单个比特的错误。

  • 校验位的位置通常是 2 的幂次位置（例如：1, 2, 4, 8, …），其余位置则用于存储实际的数据位。

  • 计算校验位：

    • 每个校验位覆盖一组特定的数据位。具体来说，第 i 个校验位（从左起编号为 1 开始）会覆盖所有二进制表示中含有第 i 位为 1 的数据位。
    • 例如：
      • 第 1 位校验位（P1）检查所有奇数位（1, 3, 5, 7, …）。
      • 第 2 位校验位（P2）检查所有包含二进制位 0010 的位置（2, 3, 6, 7, …）。
      • 第 4 位校验位（P4）检查所有包含二进制位 0100 的位置（4-7, 12-15, …）。
      • 以此类推。

  • 示例

    假设我们有一个 8 位的数据值 10011010。

    1. 准备数据：留出校验位的位置，得到 12 位模式 _ _ 1 _ 0 0 1 _ 1 0 1 0。

    2. 计算校验位：

    • P1 (第 1 位) 检查 1, 3, 5, 7, 9, 11 位：_ + 1 + 0 + 1 + 1 + 1 = _ + 4（偶数），因此 P1 = 0。
    • P2 (第 2 位) 检查 2, 3, 6, 7, 10, 11 位：_ + 1 + 0 + 1 + 0 + 1 = _ + 3（奇数），因此 P2 = 1。
    • P4 (第 4 位) 检查 4, 5, 6, 7, 12 位：_ + 0 + 0 + 1 + 0 = 1（奇数），因此 P4 = 1。
    • P8 (第 8 位) 检查 8, 9, 10, 11, 12 位：_ + 1 + 0 + 1 + 0 = 2（偶数），因此 P8 = 0。
    1. 最终编码结果：
    • 将计算好的校验位填入相应位置，得到最终的 12 位汉明码 011100101010。

  • 错误检测与纠正

    假设在传输过程中，第 10 位发生了翻转，变成了 011100101110。

    1. 重新计算校验位：

      • P1: 0 + 1 + 0 + 1 + 1 + 1 = 4（偶数），正确。
      • P2: 1 + 1 + 0 + 1 + 1 + 1 = 5（奇数），错误。
      • P4: 1 + 0 + 0 + 1 + 0 = 2（偶数），正确。
      • P8: 0 + 1 + 1 + 1 + 0 = 3（奇数），错误。

    2. 定位错误：发现 P2 和 P8 的校验失败，根据它们的位置（2 和 8），将这两个位置相加，得到 10，表明第 10 位有错。

    3. 纠正错误：翻转第 10 位，恢复原始数据 011100101010。

SEC/DED 编码
  • 最小汉明距离为 4：这意味着在任意两个合法的代码字之间至少有 4 个不同的比特。这使得 SEC/DED 编码可以：
    • 检测并纠正单个比特错误。
    • 检测但不纠正两个比特的错误。
  1. 标准汉明码校验位：
    • 如同普通的 SEC 编码，使用若干个校验位（通常位于 2 的幂次位置），这些校验位覆盖特定的数据位以确保汉明距离为 3。
  2. 额外的整体奇偶校验位（Overall Parity Bit, P）：
    • 在所有数据位和标准汉明码校验位的基础上添加一个整体奇偶校验位 P，以确保整个编码的汉明距离为 4。
    • 这个额外的校验位用于覆盖所有其他比特（包括其他校验位），从而提高错误检测能力。

  • 错误情况处理

    1. H 是偶数且 P 是偶数：没有错误。
    2. H 是奇数且 P 是奇数：发生了可纠正的单比特错误，根据 H 的值确定并纠正错误比特。
    3. H 是偶数且 P 是奇数：整体奇偶校验位 P 本身发生了单比特错误。
    4. H 是奇数且 P 是偶数：发生了双比特错误，虽然无法纠正，但可以检测到。
校验码的位数

数据位数与校验码位数的关系：

  • 数据位数为 d，校验码位数为 p，则必须满足关系式 $2^p \geq d + p + 1$。
  • 例如：
    • 数据长度为 8 位时，$d=8$，则 $2^p \geq 8 + p + 1$，因此 $p=4$。
    • 数据长度为 16 位时，$p=5$；32 位时，$p=6$；64 位时，$p=7$。

虚拟机 (Virtual Machines)

概念与优势

  1. 概念：

    • 主机计算机模拟客户操作系统和机器资源。

  2. 优势：

    • 改进隔离性：多个客户机之间的资源得到更好的隔离，避免安全性和可靠性问题。
    • 资源共享：有助于在多租户环境中有效共享资源。

  3. 性能影响：

    • 尽管虚拟化会带来一定的性能开销，但对于现代高性能计算机来说是可行的。

  4. 例子：

    • IBM VM/370（1970 年代技术）
    • VMware
    • Microsoft Virtual PC

虚拟机监控器 (Virtual Machine Monitor, VMM)

  1. 功能：
    • 映射虚拟资源到物理资源（如内存、I/O 设备、CPU）。
  2. 运行模式：
    • 客户代码以用户模式在原生机器上运行。
    • 在遇到特权指令或访问受保护资源时触发陷阱，转向 VMM 处理。
  3. 灵活性：
    • 客户操作系统可以不同于主机操作系统。
    • VMM 负责管理实际的 I/O 设备，并为客户操作系统提供通用的虚拟 I/O 设备仿真。

示例：计时器虚拟化 (Timer Virtualization)

  1. 本地机器上的计时器中断：
    • 操作系统暂停当前进程，处理中断，选择并恢复下一个进程。
  2. 带有 VMM 的情况：
    • VMM 暂停当前虚拟机，处理中断，选择并恢复下一个虚拟机。
  3. 虚拟计时器需求：
    • 如果虚拟机需要计时器中断，VMM 会模拟一个虚拟计时器，并在物理计时器中断发生时为虚拟机生成相应的中断。

指令集支持 (Instruction Set Support)

  1. 模式区分：

    • 用户模式和系统模式：特权指令只能在系统模式下使用，在用户模式下执行这些指令会触发陷阱。

  2. 物理资源访问：

    • 所有物理资源（如页表、中断控制、I/O 寄存器）只能通过特权指令访问。

  3. 当前指令集架构（ISA）的适应性：

    • 现代指令集架构（如 x86）正在调整以更好地支持虚拟化。

  4. 增强功能：

    • 提供额外的指令和机制来简化虚拟化的实现，提高效率，减少虚拟化带来的性能损失。

虚拟内存 (Virtual Memory)

概念与管理

  1. 定义：

    • 使用主存作为次级存储（磁盘）的“缓存”，由 CPU 硬件和操作系统（OS）共同管理。

  2. 目的：

    • 程序共享主存，每个程序获得一个私有的虚拟地址空间，用于存放频繁使用的代码和数据。
    • 保护程序不被其他程序干扰。

  3. 机制：

    • CPU 和 OS 负责将虚拟地址翻译成物理地址。

    • VM 中的“块”称为页，VM 翻译未命中称为页错误（page fault）。

      • 耗费大量时钟周期：从磁盘读取页面需要数百万个 CPU 时钟周期，这会导致显著的延迟，严重影响程序执行速度。

        • 磁盘访问速度远慢于主存，因此每次页错误都会带来巨大的时间开销。

        • 目标： 尽量减少页错误率（Minimize Page Fault Rate）,因为每次页错误都会导致显著的性能损失，所以优化的目标是尽可能减少页错误的发生频率。

        • 优化策略：

          • 全关联放置（Fully Associative Placement）：

            • 全关联缓存允许一个页面被放置在任何可用的物理页面框中，而不是限制在特定位置。
            • 这种方法可以提高命中率，从而减少页错误的发生。

          • 智能替换算法（Smart Replacement Algorithms）：

            • 使用更智能的页面替换算法来决定哪些页面应该被移出物理内存，以腾出空间给新页面。

  4. 固定大小页面（如 4KB），有助于简化管理和提高效率。

地址翻译 (Address Translation)

  1. 页表：

    • 存储放置信息，数组形式，索引为虚拟页号。
    • 页表寄存器指向物理内存中的页表。

  2. 页表条目（Page Table Entry,PTE）：

    • 如果页面在内存中，PTE 存储物理页号和其他状态位（如引用位、脏位等）。
    • 如果页面不在内存中，PTE 可以指向下交换空间中的位置。

  3. 页表大小：

    • 对于 32 位虚拟地址、4KB 页面和每 PTE 4 字节，总页表大小为 $2^{32} / 2^{2+10} \times 4 = 4MiB$。多个进程运行时，每个进程都有自己的页表，可能会占用大量内存。

  • 减少页表内存开销的方法

    • 限制寄存器：限制页表大小。
    • 双页表和双限制寄存器：分段页表，从高地址和低地址分别增长。
    • 反向页表：使用哈希函数减少页表大小。
    • 多级页表：允许页表本身也被分页。
快速地址翻译 (Fast Translation)与 TLB

  1. TLB 概念：

    • TLB 是 CPU 内的快速缓存，用于存储最近使用的 PTE。
    • 典型配置：16–512 个 PTE，0.5–1 个周期的命中时间，10–100 个周期的未命中时间，0.01%–1%的未命中率。

  2. TLB 缺失处理：

    • 如果页面在内存中：
      • 加载 PTE：从内存中加载页表条目（PTE），然后重试指令。
      • 硬件处理：可以在硬件中处理，但对于更复杂的页表结构可能会变得复杂。
      • 软件处理：触发特殊异常，使用优化的处理器来处理。
    • 如果页面不在内存中（页错误）：
      • 操作系统处理：OS 负责从磁盘读取页面，并更新页表。
      • 重启故障指令：处理完成后，重新启动导致故障的指令。

  3. 缓存与 TLB 交互 (TLB and Cache Interaction)

    1. 物理地址标签：如果缓存标签使用物理地址，则需要先进行地址翻译才能查找缓存。

    2. 虚拟地址标签：可以直接使用虚拟地址作为缓存标签，但需解决别名问题（同一物理地址对应多个虚拟地址）。

不同缺失组合（TLB PageTable Cache）的效果 最佳情况：命中、命中、命中，不需要访问主存。 次佳情况：命中、命中、缺失 和 缺失、命中、命中，只需访问主存一次。 中等情况：缺失、命中、缺失，不需访问磁盘，但至少访问主存两次。 最坏情况：缺失、缺失、缺失，需访问磁盘一次，至少访问主存两次。

内存保护

  • 任务共享虚拟地址空间的部分：
    • 需要防止错误访问。
    • 需要操作系统的协助。
    • 硬件支持操作系统保护机制，如特权监督模式（内核模式）、特权指令、只能在监督模式下访问的页表和其他状态信息。

理解程序性能

  • 页面交换（Thrashing）：

    • 如果程序持续在内存和磁盘之间交换页面，会导致非常慢的执行速度。
    • 应该重新审视算法和数据结构，以改善局部性，减少同时使用的页面数量，即工作集。

  • 常见的问题是 TLB 缺失：

    • 由于 TLB 通常只处理 32–64 个页面条目，程序可能会看到较高的 TLB 缺失率。
    • 使用更大的页面大小可以减少 TLB 缺失，因为更大页面意味着可以直接访问更多内存。

  • 现代计算机架构支持可变页面大小：

    • 例如，除了标准的 4KiB 页面外，MIPS 硬件还支持 16KiB, 64KiB, 256KiB, 1MiB, 4MiB, 16MiB, 64MiB, 和 256MiB 页面。
    • 使用大页面可以减少 TLB 缺失，因为单个 TLB 条目可以覆盖更多的内存区域。

内存层次结构 (The Memory Hierarchy)

共同原则

  1. 基于缓存概念：

    • 内存层次结构的每一层都遵循缓存的基本原理，包括块放置、查找块、缺失时替换策略和写入策略。

  2. 通用框架：

    • 每一层内存都涉及四个主要方面：块放置、查找块、替换策略和写入策略。

块放置 (Block Placement)

  • 关联性决定：

    • 直接映射（Direct Mapped）：每个块只能放置在一个特定位置。
    • n 路组相联（n-way Set Associative）：每个块可以在一组内的 n 个位置中选择。
    • 全关联（Fully Associative）：每个块可以放置在任何位置。

  • 影响：

    • 较高的关联性可以减少未命中率，但会增加复杂性、成本和访问时间。

查找块 (Finding a Block)

  • 硬件缓存：

    • 减少比较次数以降低成本。

  • 虚拟内存：

    • 使用完整表查找使全关联变得可行，从而降低未命中率。

  • 标签比较次数：

    • 直接映射：1 次
    • n 路组相联：n 次
    • 全关联：所有条目数次

替换策略 (Replacement)

  • 选择替换项：
    • 最近最少使用（LRU, Least Recently Used）：选择最长时间未使用的块进行替换。对于高关联性，实现复杂且成本高。
    • 随机（Random）：接近 LRU 的效果，但更容易实现。
    • 虚拟内存中的 LRU 近似：通过硬件支持实现。

写入策略 (Write Policy)

  • 直写（Write-through）：
    • 同时更新上层和下层内存。简化替换逻辑，但可能需要写缓冲区。
  • 回写（Write-back）：
    • 只更新上层内存；当块被替换时才更新下层内存。需要保持更多状态信息。
    • 对于虚拟内存，由于磁盘写入延迟，通常只采用回写策略。

缺失来源 (Sources of Misses)

  • 强制缺失（Compulsory Misses）：
    • 第一次访问块时发生。
  • 容量缺失（Capacity Misses）：
    • 由于有限的缓存大小导致。被替换的块再次访问时也会产生缺失。
  • 冲突缺失（Conflict Misses）：
    • 在非全关联缓存中，由于对组内条目的竞争而发生。在相同总大小的全关联缓存中不会发生。

缓存设计权衡 (Cache Design Trade-offs)

  • 增大缓存大小：

    • 效果：减少容量缺失。
    • 负面影响：可能增加访问时间。

  • 增加关联性：

    • 效果：减少冲突缺失。
    • 负面影响：可能增加访问时间。

  • 增加块大小：

    • 效果：减少强制缺失。
    • 负面影响：增加缺失惩罚。对于非常大的块大小，可能会因为污染而导致未命中率上升。

缓存一致性问题 (Cache Coherence Problem)

  • 假设：两个 CPU 核心共享同一物理地址空间。
  • 示例时间线：
    • 步骤 0：初始状态，CPU A 和 CPU B 的缓存及内存中 X 的值均为 0。
    • 步骤 1：CPU A 读取 X，其缓存中 X 的值为 0。
    • 步骤 2：CPU B 读取 X，其缓存中 X 的值也为 0，内存中的 X 仍为 0。
    • 步骤 3：CPU A 将 X 写入 1，此时 CPU A 的缓存中 X 的值为 1，而 CPU B 的缓存中 X 的值仍为 0，内存中的 X 更新为 1。

一致性定义

  • 非正式定义：读操作返回最近写入的值。

  • 正式定义：

    • 如果处理器 P 写入 X，随后 P 读取 X（在此期间没有其他写入），则读取应返回写入的值。
    • 如果处理器 P1 写入 X，随后处理器 P2 读取 X（足够晚的时间后），则读取应返回写入的值。
    • 如果处理器 P1 和 P2 都写入 X，则所有处理器看到的写入顺序相同，最终得到相同的 X 值。

  • 在步骤 3 之后，CPU B 读取 X 时应返回最新的值 1，而不是旧值 0。这体现了缓存一致性的要求。

缓存一致性协议 (Cache Coherence Protocols)

这些协议确保在多处理器系统中缓存的一致性：

  1. 数据迁移：

    • 将数据迁移到本地缓存以减少共享内存带宽需求。

  2. 读共享数据复制：

    • 复制读共享的数据以减少访问竞争。

  3. 窥探协议（Snooping Protocols）：

    • 每个缓存监控总线上的读写操作。

    • 无效化窥探协议：

      • 当缓存需要写入一个块时，它获得对该块的独占访问权。
      • 广播一个无效化消息到总线上，使其他缓存中的该块失效。
      • 其他缓存后续读取时会缺失，由拥有最新值的缓存提供更新后的值。

      示例时间线

      • 步骤 0：CPU A 读取 X，缓存缺失，从内存加载 X=0。
      • 步骤 1：CPU B 读取 X，缓存缺失，从内存加载 X=0。
      • 步骤 2：CPU A 将 X 写入 1，广播无效化消息，CPU B 的缓存中 X 失效。
      • 步骤 3：CPU B 读取 X，缓存缺失，由 CPU A 的缓存提供最新的 X=1。

  4. 基于目录的协议（Directory-Based Protocols）：

    • 缓存和内存记录块的共享状态在一个目录中，用于跟踪哪些处理器缓存了哪些块。

内存一致性模型 (Memory Consistency)

  • 写操作何时被其他处理器看到：

    • “看到”意味着读操作返回写入的值。
    • 不可能是即时的，存在延迟。

  • 假设条件：

    • 写操作只有当所有处理器都看到它时才完成。
    • 处理器不会重新排序写操作与其他访问操作。

  • 后果：

    • 如果处理器 P 先写入 X 再写入 Y，则所有看到新 Y 值的处理器也必须看到新的 X 值。
    • 处理器可以重新排序读操作，但不能重新排序写操作。

冗余磁盘阵列 (RAID)

概述

  • 定义：RAID（Redundant Arrays of Inexpensive Disks）通过将多个独立操作的磁盘按某种方式组织成磁盘阵列，以增加存储容量、提高数据传输速度和增强系统可靠性。
  • 技术原理：
    • 利用类似于主存中的多体交叉技术，将数据存储在多个磁盘上，使这些磁盘并行工作来提高数据传输速度。
    • 使用冗余磁盘技术进行错误检测和恢复，以提高系统的可靠性和容错能力。

RAID 级别

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

    • 特点：
      • 数据被分割成块，并分布在多个磁盘上。
      • 提供较高的 I/O 响应能力和数据传输率。
      • 如果两个 I/O 请求访问不同磁盘上的数据，则可并行发送，减少排队时间。
      • 同一 I/O 请求的不同数据块可以并行传送，适用于视频编辑和播放系统等对速度要求高的非关键数据存储场合。
    • 优点：高读写性能。
    • 缺点：无冗余，单个磁盘故障会导致整个阵列失效。

  2. RAID 1（镜像）

    • 特点：
      • 实现 1 对 1 的数据镜像冗余。
      • 读取时可以从任一磁盘获取数据，选择定位时间较短的磁盘提供服务。
      • 写入时必须同时更新两个磁盘，写性能受限于较慢的一次写操作。
      • 数据恢复简单，当一个磁盘损坏时，可以从另一个磁盘读取数据。
    • 优点：高可靠性。
    • 缺点：成本较高，因为需要两倍的磁盘空间。
    • 应用场景：用于对可靠性要求极高的场合，如系统软件存储、金融和证券系统。

  3. RAID 5（分布式奇偶校验）

    • 特点：
      • 奇偶校验块分布在所有磁盘中，避免了使用专门校验盘可能带来的 I/O 瓶颈。
      • 独立存取技术提供了较高的 I/O 响应速度。
      • 成本效益好，既提高了性能又增强了可靠性。
    • 优点：高效率和良好的容错性。
    • 缺点：写入性能相对较低，因为每次写入都需要更新奇偶校验信息。
    • 应用场景：广泛应用于各种服务器和存储系统中，平衡了性能与成本。

  4. 其他 RAID 级别

    • RAID 10：结合了 RAID 0 和 RAID 1 的优点，先做镜像再做条带化，提供高性能和高可靠性。
    • RAID 30：结合了 RAID 0 和 RAID 3 的特点，适用于特定应用环境。
    • RAID 50：结合了 RAID 0 和 RAID 5 的优点，进一步提升了性能和可靠性。

输入输出系统

外设发展与分类

  • 交互方式：
    • 人-机交互设备：信息是人可读的，如键盘、鼠标、显示器等。
    • 机器可读设备：信息为机器可读格式，人无法直接读取，例如网络接口、D/A 转换器、磁盘等。
  • 功能行为：
    • 输入/输出设备：用于信息的输入和输出，通常处理字符型数据，如键盘、打印机。
    • 外部存储设备：用于信息的长期存储，通常处理块数据，如磁盘、光盘。

外部设备的通用模型

  • 设备通过电缆与计算机内部 I/O 接口进行数据、状态和控制信息的交换。该模型包含缓冲器、变换器、控制逻辑，以及设备数据和环境之间的通信路径。
  • 描述了电缆中的三种信号线：控制信号、状态信号、数据信号。

键盘(Keyboard)

  • 基本单位：字符，使用 ASCII 码表示。
  • 输入过程：
    • 按键后，通过行扫描法或线反转法查出按下的键。 行扫描的基本做法：按行扫描、接地检查，以确定哪个键被按下。
    • 将按键位置信息转换为 ASCII 码并保存到计算机中。
    • 编码键盘直接提供 ASCII 码给 CPU，而非编码键盘仅提供行列矩阵。
  • 类型：编码键盘和非编码键盘。
  • 键盘连接：5 芯 PS2 接口或 USB 接口。

系统总线

  • 包括控制线、数据线和地址线，负责同步、初始化、请求和确认等信号的传输。

  • 系统总线通常由一组控制线、一组数据线和一组地址线构成，有时地址信息可通过数据线传送，称为数据/地址复用。

  • 主板上的扩展插槽都是总线插座，支持额外的硬件添加。

  • 总线性能指标

    • 宽度、工作频率、传送方式（非突发传送、突发传送）、带宽。
    • 总线宽度决定了每次能同时传输的信息位数；工作频率可能等于总线时钟频率或其倍数；传送方式影响效率；带宽反映了最大数据传输率。
    • 对于同步总线，总线带宽计算公式： B=W×F/N W-总线宽度；F-总线时钟频率；N-完成一次数据传送所用时钟周期数 F/N 实际上就是总线工作频率

I/O 接口

  • 功能：数据缓冲、错误或状态检测、控制和定时、数据格式转换、主机与设备间的通信。

  • 结构：不同 I/O 模块在复杂性和控制外设的数量上存在差异。

  • 通过命令字、状态字、数据交换来与设备通信，并将这些寄存器称为 I/O 端口。

  • 寻址方式

    • 统一编址方式：将主存空间的一部分分配给 I/O 端口编号。
    • 独立编址方式：创建一个独立的 I/O 地址空间。

  • 数据交换的三种基本方式

    • 程序直接控制方式：无条件传送（简单外设定时）、条件传送（轮询）。

    • 中断驱动 I/O 方式：当外设需要 CPU 干预时，发送中断请求。

      • 基本思想：当外设准备好时，便向 CPU 发中断请求，CPU 响应后，中止现行程序的执行，转入一个“中断服务程序”进行输入/出操作，实现主机和外设接口之间的数据传送，并启动外设工作。“中断服务程序”执行完后，返回原被中止的程序断点处继续执行。此时，外设和 CPU 并行工作。
      • 异常发生时，处理器关闭中断，保护断点和程序状态，然后识别异常事件并转到具体的异常处理程序执行。

    • DMA 方式：高速外设直接与内存交换数据，由 DMA 控制器管理。

      • 在高速外设和主存之间直接传输数据，通过专门硬件（DMA 接口）控制总线访问，减少 CPU 干涉。

      • DMA 适用于成批数据交换，且数据间隔时间短。

Licensed under CC BY-NC-SA 4.0