计算机组成原理
全局框架 - 全局框架 - 系统层次 -  - 核心矛盾：速度差 - CPU 运算快、内存慢、外设更慢 - 系统用层次结构（寄存器/Cache/内存/磁盘）和并行性（流水线/乱序/多核/DMA）来隐藏或者摊薄延迟 - 指令在 CPU 里按“取值-译码-执行-访存-写回“的数据通道运行 - 为了加速，做流水线把这 5 步重叠 - 内存访问通过 Cache 利用局部性降低平均延迟 - 虚拟内存通过 MMU/TLB 把程序看到的地址映射到物理内存 - I/O 慢是由于设备与总线带宽/延迟远弱于 CPU，因此依赖中断、缓冲与 DMA 来减少 CPU 参与 指令系统与数据表示 - 指令系统与数据表示 - 整数与位运算的数据表示 - 位、字节、字 - bit：0/1 - Byte：8bit - Word（字）：CPU 自然处理的宽度，与寄存器/ALU/地址宽度相关 - 为什么 byte 是最小编址单位：大多数现代机器按照字节编址，方便表示字符/结构体/网络数据等 - 原码/反码/补码 - 原码 - 表示方法：最高位符号位，剩下是绝对值 - 问题： - 有 +0 和 -0 两种零 - 加减法需要额外处理符号，硬件复杂 - 反码 - 正数同原码 - 负数：对正数位取反 - 问题 - 仍然有 +0 和 -0 - 加法需要回卷进位 - 补码 - 正数：与无符号相同 - 负数：按位取反 + 1 - 关键性质： - 只有一个 0（没有 -0） - 加减法统一为同一套加法器：a-b=a+(~b+1) - 符号扩展简单：高位补符号位即可 - 范围不对称 [-2^{n-1},2^{n-1}-1] - 快速转换 - 补码->十进制 - 最高位 0：按无符号直接算 - 最高位 1：取反 +1 得到绝对值，再加负号 - 十进制->补码 - 正数：直接写二进制，左侧补 0 - 负数：先写绝对值二进制 -> 取反+1 - 有符号/无符号加法与溢出判断 - 无符号溢出(Unsigned overflow) - 本质：结果超出 [0, 2^n-1] - 判定方法：看进位 Carry-out - 有符号溢出 - 本质：结果超出 [-2^{n-1},2^{n-1}-1] - 判断口径统一 - 同号相加，异号结果 => 溢出 - 异号相加不会溢出 - 等价位级判定 - 符号位的进位与最高位进位输出不同=>溢出 - 字节序：大端 vs 小端 - 对 32-bit 只 0x12 34 56 78 高位在左 - 大端 - 低地址存高字节 - 内存从低地址到高地址 12 34 56 78 - 直觉：与人类书写一致 - 小端 - 低地址存低字节 - 内存从低地址到高地址：78 56 34 12 - 直觉：低地址就是低位，做逐字节扩展/截断更自然 - x86 等主流架构长期使用小端 - 对齐与 Padding - 对齐 - 要求：某类型对象的地址必须是某个中的倍数(4/8) - 为什么要对齐 - 硬件访问效率：CPU/总线按照字/双字读写；未对齐可能需要两次内存读写再拼接 - Cache line 与内存访问粒度：对齐能减少跨行/跨 cache line 的概率 - Padding（填充） - 为了满足对齐，编译器会在结构体字段之间或末尾插入空字节 - 结构体大小通常是其最大对齐需求的倍数 - 浮点数(IEEE 754) 与误差本质 - IEEE 754 基本格式 - 浮点数表示 - S（符号位）：0 正 1 负 - E（指数/阶码）：带拍支 bias - F（尾数/小数部分）：有效数 significand 的小数部分 -  - 单精度 float（32-bit） - S: 1 位 - E: 8 位，bias = 127 - F: 23 位 - 双精度 double（64-bit） - S：1 位 - E: 11 位，bias=1023 - F: 52 位 - 规格化、非规格、0、INF、NaN - 规格化 - 指数 E 既不是全 0 也不是全 1 - 有隐含的 leading 1：1.F - 非规格化 - 指数 E 全 0，尾数 F 非 0 - 没有隐含 1：有效数是 0.F - 目的：渐进下溢，让非常接近 0 的数仍然能表示 - 0 - E 全 0，F 全 0 - 有 +0 和 -0 - Inf 无穷 - E 全 0，F 全 0 - 有 +0 和 -0 - NaN（非数） - E 全 1，F 非 0 - 来自非法操作：0/0 - NaN 会传播 - 0.1 + 0.2 != 0.3 - 十进制小数在二进制中往往是无线不循环小数 - 0.1 的二进制是 0.0001100111 - float/double 只能保存有限位尾数 - 存储时发生舍入，计算时再舍入，误差叠加 - 比较时用 ==，就可能不相等 CPU 执行与控制 - CPU 执行与控制 - 单周期 Datapath - 必备组件 -  - PC 当前指令地址寄存器 - Instruction Memory/I-Cache：根据 PC 取指令 - Register File （寄存器堆）：两读一写（rs1、rs2 读；rd 写） - Immediate Generator（立即数生成/符号扩展） - ALU：算数逻辑/比较/地址计算 - Data Memory/D-Cache：load/store 访问 - Adders： - PC + 4 - PC + imm （分支目标） - 关键 MUX（多路选择器） - ALUSrc：ALU 第二操作数是来自 rs2 还是 imm - MemToReg：写回 rd 的数据来自 ALU 还是内存 - PCSrc：下一 PC 来自 PC+4 还是分支目标 - Control Unit（控制器）：根据 opcode/funct 产生控制信号 - datapath = 一堆功能模块 + 多根线 + MUX 选路 - 四条指令在 datapath 里怎么走 - R 型算数：add rd, rs1, rs2 - 目标：rd = rs1 + rs2 - 数据流 - PC -> 取指令 - 寄存器堆读 rs1、rs2 - ALU 计算 ALUOut = rs1 + rs2 - 写回：rd <- ALUOut - PC 更新：PC <- PC + 4 - 关键控制 - RegWrite = 1 写寄存器 - ALUSrc = 0 第二操作数来自 rs2 - MemRead = 0, MemWrite = 0 - MemToReg = 0（写回来自 ALU） - Branch = 0（不分支） - ALUOp = R-type（由 funct 决定是 add/sub/and/or） - 访存读：lw rd, imm(rs1) - 目标：rd = Mem[rs1+imm] - 数据流 - 取指 - 读寄存器 rs1 (base)，rs2 通常也读但不用 - ALU 计算有效地址：ALUOut = rs1 + imm - 数据内存读：MemOut = Mem[ALUOut] - 写回：rd <- MemOut - PC <- PC + 4 - 访存写：sw rs2, imm(rs1) - 目标：Mem[rs1+imm] = rs2 - 数据流 - 取指 - 读 rs1（base） 和 rs2（要写入的数据） - ALU 算地址：ALUOut = rs1 + imm - 数据内存写：Mem[ALUOut] <- rs2 - PC <- PC + 4 - 条件分支：beq rs1, rs2, imm - 目标：如果 rs1 == rs2，则 PC <- PC + imm；否则 PC <- PC + 4 - 数据流 - 取指 - 读 rs1，rs2 - ALU 做比较：Zero = (rs1-rs2==0) - 同时计算目标分支：Target = PC + imm - PC 选择 - if Branch & Zero：PC <- Target - else: PC <- PC + 4 - 单周期 vs 多周期 - 单周期 - 每条指令都在一个周期完成 - 周期必须长到容纳最慢指令路径 - 结果：简单但浪费，端指令也被迫跑长周期 - 多周期 - 把一条指令拆分成多个步骤，每一步一个周期 - 不同指令用不同步骤数量 - 可以复用硬件 - 性能 - 性能公式 -  - IC：执行的指令条数 - CPI：平均每条指令需要多少周期 - Cycle Time：每周期多长时间 (=1/主频) - Amdahl 定律（优化上限） - 如果系统中某部分占比位 f，该部分加速 S 倍，总加速比 -  - IPC、吞吐、延迟 - 延迟：完成单个任务/单条指令/一次请求需要的时间 - 吞吐：单位时间完成多少任务 - IPC：每周期完成多少条指令 - 吞吐 = IPC x 频率 流水线与冒险 - 流水线与冒险 - 五级流水线核心内容 - 五段功能定义 - IF：取值；PC->I-Cache；计算 PC+4 - ID：译码；读寄存器；生成立即数 - EX：ALU 运算；地址计算；分支比较 - MEM：访问 D-Cache - WB：写回寄存器 rd - 流水线寄存器 - 为了让每段每周期独立推进，段与段之间插入寄存器 - IF/ID、ID/EX、EX/MEM、MEM/WB 它们保存上一段的输出给下一段用（包含数据与控制信号） - 理想吞吐与延迟 - 非流水：一条指令用 5 个周期，下一条等它结束 - 流水：启动后每周期完成 1 条 - 延迟：单条仍然=5 个阶段 - 吞吐：理想从 1/5 提升到 1 - 流水线的代价 - 需要通多寄存器与控制逻辑 - 分支错预测要清刷流水线 - 结构冲突要加资源或停顿 - 结构冒险 - 定义 - 同一周期内两个阶段需要同一个硬件资源 - 例子 - 单端口存储器：IF 要取值，MEM 要访存 - 同一周期冲突 -> 必须 stall 或改造硬件 - 解决方案 - 分离 I-Cache/D-Cache - 多端口存储器 - 数据冒险 - 三种依赖 - RAW(Read After Write)真依赖：后读依赖前写，最关键 - WAR(Write After Read)反依赖：后写不能早于前读 - WAW(Write After Write)输出依赖：两条写同一目的寄存器 - 为什么会 RAW：写回晚，读取早 - 读寄存器在 ID - 写回寄存器在 WB - Fowwarding （旁路/转发）机制 - 不等写回到寄存器堆，直接把产生的结果从后端绕回到前段使用 - 转发路径 - EX/MEM -> ID/EX（给下一条的 EX 用） - MEM/WB -> ID/EX （给下一条或下下条的 EX 用） - Stall(插泡)与 load-use hazard - load-use 典型序列 - lw r1, 0(r2) - add r3, r1, r4 - 原因 - lw 的数据到 MEM 末才可用 - add 需要在 EX 用到 r1 - 时间上赶不上，即使有 forwarding 也不够快 - 结论：需要插入一个 bubble - 实现 - 冻结 PC 和 IF/ID - 往 ID/EX 注入一个 NOP （控制信号清零）形成 bubble - 控制冒险 - 定义：PC 的下一值不确定：到底走 PC+4 还是分支目标 - 分支决定在哪里做决定 penalty - 如果分支在 EX 才能确定 - 在分支结果出来之前，流水线已经取了后续若干条 - 一旦发现分支 taken，就要把错路径指令 flush 掉 - 基础策略 - stall until branch resolved：等分支算出来再取后续 - predict not taken：默认不跳，先取顺序；若实际 taken -> flush - 动态分支预测：用分支历史表、2-bit 饱和计数器等降低错预测 - BTB：预测 taken 时快速给出目标地址 - 延迟槽 - penalty - 分支罚时：错预测或 taken 导致需要清空的阶段数 存储体系 - 存储体系 - 核心矛盾 - CPU 周期是纳秒级，DRAM 访问通常是几十到上百纳秒级，差一个数量级 - 解决思路：分层存储 + 局部性 - Cache 用更贵更快的 SRAM 缓存最近用过的数据块，依赖时间/空间局部性降低平均访存时间 - Cache 基础概念 - Cache line （缓存行） - Cache 以“行/块“位单位搬运数据 - CPU 读写某地址时，实际会把该地址所在的整条 cache line 搬到 Cache。 - 推论：顺序访问数组通常很友好；跨行访问容易 miss - Hit/Miss 与三大指标 - Hit time：命中时访问延迟 - Miss rate：未命中比例 - Miss penalty：未命中后去下一级/内存取回的代价 - 平均访存时间 AMAT - AMAT = Hit Time + Miss Rate * Miss Penalty - MISS 分类 - Compulsory miss（冷启动）：第一次访问必 miss - Capacity miss（容量）：工作集超过 Cache 容量 - Conflict miss（冲突）：映射/组相联导致不同块争同一行 - 映射方式：直接映射/全相联/组相联 - 前置数据 - Cache 总容量 (不含tag/元数据) = C bytes - Cache line 大小 = B bytes - 总行数 (lines) = L = C/B - 相联度 (ways) = A - 组数 (sets) = S = L/A - 直接映射 - 每个内存块只能映射到唯一一个 cache 行 - 优点：硬件简单、命中快 - 缺点：冲突 miss 多 - 全相联 - 任意内存块可放任意行 - 优点：几乎无冲突 miss - 缺点：需要对所有行比较 tag（实现复杂、命中更慢、耗能更高） - 组相联 - 内存块映射到某个 set，但可以放在 set 内任一 way。 - 折中方案 - 地址拆分 - 对于字节编址系统，地址通常拆分为：tag+index+block offset - offset 块内偏移 - 表示在一条 cache line 內的字节位置 - 位数 offset bits = log2(B) - index 组索引 - 选择 set - index bits = log2(S) - tag 标记 - 用于判断该 set 中某一 way 是否是想要的内存块 - tagbits = Address bits - index bits - offset bits - 替换策略 - LRU：替换最久没用的行 - Pseudo-LRU（伪 LRU）：用更少 bit 近似 LRU - FIFO：先进先出 - 写策略 - write-throught（写穿） - 写命中：同时写 Cache 和下一级 - 优点：下一级始终最新，实现简单 - 缺点：写流量大 - write-back（写回） - 写命中：只写 Cache，把该行标记为 dirty - 该行被替换时才写回下一级 - 优点：显著减少写带宽压力 - 缺点：一致性更复杂（多核） - 写不命中 write miss 的两种策略 - write-allocate（写分配）：先把整条 line 读入 Cache，再在 Cache 上写，与 write-back 搭配 - no-write-allocate（不写分配）：不把 line 加入 Cache，直接写下一级，常与 write-throught 搭配 - 多级 Cache 的 AMAT - L1/L2 两级 - AMAT=HitTime_L1+MissRate_L1×(HitTime_L2+MissRate_L2×MissPenalty_L2) - 多核：一致性 vs 一致性协议 - Cache Coherence（一致性） - 目标：对于同一内存地址 X，各核的 cache 中 X 的副本要看起来像一个指在变化，不能读各自的旧值 - 解决办法：一致性协议(MESI)保证写入能让其他核的副本失效/更新 - Memory Consistency（一致性模型，针对不同地址的顺序） - 目标：规定不同核对不同地址的读写在时间顺序上允许怎么样被观察到 - 是内存模型讨论的问题，涉及重排序与屏障。 - Coherence 解决同一地址副本一致，Consistency 解决不同地址操作的可见顺序，前者靠协议，后者靠内存模型和 fence。 - MESI 协议 - False Sharing - 定义 - 不同核访问的是不同变量，但是这些变量恰好落在同一条 cache line 里 - 其中一个核写它自己的变量，会把整条 line 的其他核副本失效，导致另一核反复 miss - 性能问题 - 引发 invalidation（整条 line 粒度） - 两个核交替写同一条 line 上不同字节 - line 在核之间反复迁移，带来大量一致性流量 虚拟内存 - 虚拟内存 - 要解决的问题 - 抽象：每个进程看到连续的虚拟内存空间（VA） - 保护：权限控制（R/W/X，用户态/内核态） - 共享：共享库/共享内存/页共享 - 扩展：按需分页 + 换入换出 - 页 - 虚拟页：进程看到的虚拟地址空间被切分成的固定大小块 - 物理页框：正式物理内存被切成同样大小的块 - 二者的大小相同，比如常见 4KB - 虚拟内存用虚拟页编号，物理内存用页框编号，页表负责把虚拟页号 -> 物理页框号 - 地址和页对应 - 页大小是 4KB - 4KB = 4096 字节 = 2^12 - 一个地址的低 12 位代表页内偏移 - 高位表示虚拟页号（VPN） - 地址转换链路 - VA -> TLB -> page table -> PTE -> PA -> Cache/Memory - 术语解释 - VA：进程发出的地址 - PA：真实内存地址 - VPN：虚拟页号 - VPO：页内偏移 - PPN：物理页框号 - PTE：页表项，记录 VPN -> PPN 的映射与权限等元数据 - TLB：页表项的高速缓存 - 页大小与地址拆分 - 页大小是 PageSize = 2^k 字节 - offsetBits = k - VPNBits = AddrBits - k - 转换过程 - CPU 产生 VA - MMU 用 VA 的 VPN 去查 TLB - TLB hit：直接得到 PPN + 权限 - 物理地址 PA = (PPN << offsetBits) | Offset - TLB miss：用 VPN 去查页表 - 拿到 PTE - 有效 -> 填入 TLB -> 形成 PA -> 继续访问 - 无效 -> 触发异常 - 页表结构 - PTE 包含什么 - PPN：物理页框号 - Present/Valid：是否在内存 - R/W/X：读写执行权限 - U/S：用户/内核权限 - Accessed/Referenced(A)：是否被访问过 - Dirty(D)：是否被写过 - 为什么需要多级页表 - 单级页表 - VA 空间大，VPN 组合数巨大 - 每个进程都有一张覆盖整个虚拟空间的大表 - 多级页表做法 - 把 VPN 再拆分成多端：VPN1/VPN2/.../VPNn - 顶层页表只在需要时为某个范围分配下一级页表 - 没用到的地址区间不分配页表 -> 按需分配页表 - 多级页表的 Page Walk - 先用 VPN 的高段索引顶层页表，取到二级页表的地址 - 再用下一段索引二级页表页 - 最终找到叶子 PTE 得到 PPN - 代价：要读多次内存 - TLB - 没有 TLB - 每次 load/store 都要走 page walk，可能是 4/5 级 - 意味着每次访问内存前都要额外多次访存 - TLB 的本质 - 缓存最近用过的 VPN -> PPN + 权限 - 命中时地址翻译几乎是常数空间 - 缺页异常 - 典型原因 - Demand paging（按需分页）：页还没加载到内存 - Swap out：页被换出到磁盘 - 权限违规：写只读页 - Copy-on-write：写共享只读页 - 缺页处理流程 - CPU 访问 VA，发现 PTE present = 0 或者权限不符合 - 触发异常，陷入内核（保存上下文，切换到内核栈） - 内核 fault handler 判断 fault 类型 - 是合法的按需页/非法地址 - 合法 - 找到磁盘位置 - 分配物理页框 - 发起 IO 把页读入内存 - 更新页表 PTE - 更新 TLB - 恢复进程执行 - 页面置换 - 当需要一个物理页框但是没有空闲页时，OS 必须选择一个牺牲页换出 - LRU - Clock/Second-Chance(近似 LRU) - 维护环形指针 - 每个页有 Accessed/Referenced 位 - 扫描时 - 若 A=0：淘汰 - 若 A=1：把 A 清 0，给第二次机会，指针继续走 - 共享与写时复制(COW) - 为什么需要 COW - fork 的语义：子进程得到父进程内存的副本 - 如果把所有页都复制一遍，成本极高 - COW - fork 后，父子进程的页表都指向同一批物理页框 - 把这些页的 PTE 权限改为只读 - 当父或子尝试写入某页 - 写入触发 page fault - 内核分配新物理页 - 复制旧页内容到新页 - 修改该进程页表让它指向新页，恢复写权限 - 另一个进程仍然指向旧页 IO 总线 - IO 总线 - IO 本质上慢 - 设备物理特性：SSD/网卡/磁盘的延迟远远高于 CPU - 路径长：系统调用、内核态切换、驱动、协议栈、队列管理 - 数据搬运：拷贝次数多、缓存一致性/同步开销高 - I/O 的基本硬件/软件组件 - 设备、控制器、驱动 - 设备：网络、磁盘、USB 设备等 - 控制器：设备侧的执行单元，负责 DMA、队列、寄存器接口等 - 驱动：内核中的软件，负责配置设备、提交请求、处理中断、管理队列 - 数据通路常见参与者 - CPU 核心 - Cache - 内存 - I/O 互联 (PCIe) - 设备控制器 - 设备介质 - 轮询 vs 中断 - 轮询 - 做法：CPU 不断读取设备状态寄存器 - 优点：实现简单、延迟可控 - 缺点：浪费 CPU、高并发/多设备会严重占用 CPU - 中断 - 设备完成后发中断信号，CPU 暂停当前执行，进入中断处理程序(ISR) - 优点： - CPU 不需要忙等->提升整体吞吐 - 缺点： - 有中断开销：恢复/保存上下文、切换栈、处理 ISR - 中断频繁造成抖动 - DMA - 不用 DMA 的程序搬运 - CPU 循环从设备寄存器读数据，再写入内存 - 缺点：CPU 被数据搬运绑死，带宽高、功耗高 - DMA 的本质 - DMA 让设备/控制器直接读写内存，CPU 只做设置与收尾 - CPU 配置 DMA 描述符：内存地址、长度、方向、队列位置 - DMA 引擎通过总线把数据直接写入/读出 DRAM - 完成后用中断通知 CPU（或写状态寄存器） - DMA 为什么更快 - 释放 CPU 周期 - DMA 更贴近总线/设备，能更高效做 burst 传输 - 配合 ring buffer/descriptor queue 能批量提交 - 内存映射 I/O 与端口 I/O - MMIO - 设备寄存器被映射到某段物理地址空间 - CPU 用普通的 load/store 指令读写这些地址，就等价于读写设备寄存器 - Port-mapped I/O - 使用专门的 IN/OUT 指令访问 I/O 端口空间 - 现代系统多以 MMIO 为主 - 零拷贝 - 传统读文件再发网络的拷贝路径 - read()：磁盘->内核页缓存->拷贝到用户缓冲区 - write()：用户缓冲区->再拷贝回内核 socket buffer -> 网卡 DMA 发走 - 至少需要两次 CPU 拷贝（内核<->用户，用户<->内核） - sendfile 思路 - 直接让内核把 page cache 中的文件页挂到 socket 发送队列 - 避免拷贝到用户态再拷回内核态 - 网卡通过 DMA 从内核缓冲直接发 - mmap 思路 - mmap 把文件映射进进程地址空间 - 应用像访问内存一样访问文件内容，缺页时 OS 按需把页载入 page cache - 适合随机访问，但是直接转发场景 sendfile 更适合