Ch13 计算与操作系统 · 闪卡 (Anki 导出)¶

100 张卡,涵盖 5 节核心。Anki Deck: Ch13 计算与操作系统

Section A: 离散数学基础¶

Card 1¶

Front: 集合 \(S\) 的幂集 \(|\mathcal{P}(S)|\) 大小? Back: \(|\mathcal{P}(S)| = 2^{|S|}\)。每个元素可选在或不在子集中。

Card 2¶

Front: 排列 \(P(n, k)\) 公式? Back: \(P(n, k) = \frac{n!}{(n-k)!}\)。\(P(5, 3) = 60\)。有序。

Card 3¶

Front: 组合 \(C(n, k)\) 公式? Back: \(C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}\)。\(C(5, 3) = 10\)。无序。

Card 4¶

Front: 大 O 记号定义? Back: \(T(n) = O(f(n))\) 当 \(\exists c > 0, n_0: T(n) \leq c f(n), \forall n \geq n_0\)。上界。

Card 5¶

Front: 大 Ω 记号? Back: \(T(n) = \Omega(f(n))\) 下界。\(T(n) = \Theta(f(n))\) 紧界。

Card 6¶

Front: 鸽巢原理? Back: \(n\) 个鸽巢, \(n+1\) 只鸽子, 至少一巢有 ≥ 2 只。

Card 7¶

Front: 命题逻辑符号? Back: \(\land\) 与, \(\lor\) 或, \(\neg\) 非, \(\to\) 蕴含, \(\leftrightarrow\) 等价。

Card 8¶

Front: 数学归纳法两步? Back: (1) 基础: \(P(1)\) 成立; (2) 归纳: \(P(k) \to P(k+1)\)。

Card 9¶

Front: P 类问题定义? Back: 多项式时间内可解。\(P \subseteq NP\)。

Card 10¶

Front: NP 完整问题举例? Back: SAT, 旅行商 (TSP), 团问题 (Clique), 子集和。互为多项式归约。

Section B: 计算机架构¶

Card 11¶

Front: 默写 CPU 时间公式。 Back: \(T_{\text{CPU}} = IC \times CPI \times T_{\text{cycle}}\)。IC 指令数, CPI 每指令周期, \(T_{\text{cycle}}\) 周期时间。

Card 12¶

Front: 冯诺依曼架构组件? Back: CPU (ALU + CU) + 内存 + 总线 + 输入/输出。存储程序 (stored-program)。

Card 13¶

Front: 内存层级 (从快到慢)? Back: 寄存器 (~1 ns) → L1 (~1 ns) → L2 (~10 ns) → L3 (~30 ns) → DRAM (~100 ns) → SSD (~100 μs) → HDD (~10 ms)。

Card 14¶

Front: 缓存命中率公式? Back: \(h = N_{\text{hit}} / N_{\text{total}}\)。L1 95% 命中 → 平均访问 ~1.45 ns。

Card 15¶

Front: 流水线 CPI 公式? Back: \(\text{CPI}_{\text{pipeline}} = \text{CPI}_{\text{ideal}} + N_{\text{stall}}/N_{\text{inst}}\)。

Card 16¶

Front: DRAM 与 SRAM 区别? Back: SRAM 快但贵 (寄存器缓存), DRAM 慢但密 (主存)。SRAM 用触发器, DRAM 用电容刷新。

Card 17¶

Front: CPU vs GPU 核心差异? Back: CPU 少核 (8-64) 高频率, 控制逻辑复杂; GPU 多核 (数千) 低频率, SIMT 适合并行。

Card 18¶

Front: GPU FLOPS 公式? Back: \(\text{FLOPs} = N_{\text{SM}} \times \text{cores/SM} \times F \times 2\)。H100 ~1000 TFLOPS (FP16)。

Card 19¶

Front: 内存墙 (Memory Wall)? Back: CPU 算力增长 >> 内存带宽增长, 性能被内存带宽限制。

Card 20¶

Front: SIMT 是什么? Back: Single Instruction Multiple Threads — GPU 同一指令, 多数据流 (NVIDIA 术语)。

Section C: 操作系统¶

Card 21¶

Front: 进程 vs 线程差别? Back: 进程独立地址空间, 线程共享。线程轻量 (~1 MB stack), 进程重 (~10 MB)。

Card 22¶

Front: 进程地址空间布局? Back: 从低到高: 代码段 → 数据段 → 堆 (向上长) → 栈 (向下长)。共享库, 内核区。

Card 23¶

Front: 虚拟内存如何工作? Back: MMU 翻译虚拟地址 → 物理地址; 页表 VA → PA; TLB 缓存页表项。

Card 24¶

Front: Page fault 是什么? Back: 访问不在内存的页, OS 从磁盘换入 (ms 级)。

Card 25¶

Front: 死锁四条件? Back: (1) 互斥, (2) 占有并等待, (3) 不剥夺, (4) 循环等待。

Card 26¶

Front: 调度算法? Back: FCFS (先来先服务), SJF, RR (时间片), CFS (Linux 完全公平)。

Card 27¶

Front: 文件系统 inode 是什么? Back: 索引节点, 存储文件元数据 (权限/时间戳/数据块指针)。ext4 inode = 256 B。

Card 28¶

Front: 中断与异常区别? Back: 中断异步 (外设), 异常同步 (除 0 / 缺页)。

Card 29¶

Front: 系统调用是什么? Back: 用户态 → 内核态的入口。fork, exec, read, write 等。

Card 30¶

Front: fork vs exec? Back: fork 复制当前进程, exec 替换为新程序。fork+exec 是经典组合。

Section D: 并发并行¶

Card 31¶

Front: 默写 Amdahl 公式。 Back: \(S(n) = \frac{1}{(1-p) + p/n}\)。\(p\) 可并行比例。

Card 32¶

Front: 互斥锁 (mutex) 与信号量 (semaphore)? Back: mutex 二值 (一个线程进入), semaphore 计数 (N 个线程)。

Card 33¶

Front: 死锁 vs 活锁 vs 饥饿? Back: 死锁 = 互相等待 (永久); 活锁 = 不断让步 (忙等); 饥饿 = 某些线程长期得不到资源。

Card 34¶

Front: MapReduce 两阶段? Back: map: \((k, v) \to \text{list}(k', v')\); reduce: \((k', \text{list}(v')) \to \text{list}(v'')\)。

Card 35¶

Front: CUDA warp 大小? Back: 32 threads。1 block = 多 warp, 1 SM 调度多 block。

Card 36¶

Front: CUDA 内存类型? Back: Global (大, 慢), Shared (小, 快), Local (per-thread), Constant, Texture。

Card 37¶

Front: AllReduce vs Reduce-Scatter? Back: AllReduce 同步到所有节点; Reduce-Scatter 各节点拿不同分片。

Card 38¶

Front: CAP 定理三选二? Back: 一致性 (C), 可用性 (A), 分区容忍 (P)。分布式系统最多三选二。

Card 39¶

Front: 一致性哈希? Back: 节点 / 数据映射到 0-2^32 环, 顺时针找最近节点。增删节点只影响邻居。

Card 40¶

Front: NCCL 是什么? Back: NVIDIA Collective Communications Library, GPU 集合通信 (AllReduce 等)。

Section E: 编程语言¶

Card 41¶

Front: Lambda 演算基本元素? Back: 变量 \(x\), 抽象 \(\lambda x. e\), 应用 \(e_1 e_2\)。Church 数: \(c_n = \lambda f. \lambda x. f^n(x)\)。

Card 42¶

Front: 静态类型 vs 动态类型? Back: 静态: 编译期检查 (Java, C++); 动态: 运行期检查 (Python, JS)。

Card 43¶

Front: 强类型 vs 弱类型? Back: 强: 严格类型转换 (Python); 弱: 隐式转换 (JS, "1" + 2 = "12")。

Card 44¶

Front: Hindley-Milner 类型推导? Back: ML 语言风格, 无需显式类型即可推导。let polymorphism。

Card 45¶

Front: 编译流程 5 阶段? Back: 词法 → 语法 → 语义 → 中间代码 (IR) → 目标代码。每阶段用不同数据结构。

Card 46¶

Front: JIT 编译? Back: Just-In-Time, 运行时编译热点代码 (HotSpot, V8 TurboFan)。

Card 47¶

Front: GC 三大算法? Back: 引用计数, 标记-清除 (mark-sweep), 复制 (copying)。

Card 48¶

Front: Curry-Howard 对应? Back: 程序 ≡ 证明, 类型 ≡ 命题。Haskell 类型系统是逻辑证明系统。

Card 49¶

Front: 命令式 vs 函数式? Back: 命令式: 状态 + 赋值 (C, Java); 函数式: 表达式 + 不可变 (Haskell, Lisp)。

Card 50¶

Front: Rust 所有权 (Ownership)? Back: 每个值一个所有者, 离开作用域 drop; 借用检查 (borrow checker) 防止 use-after-free。

Section F: 现实应用¶

Card 51¶

Front: PyTorch 后端是什么? Back: C++ + CUDA + ATen (tensor library) + autograd。C++ 调度, CUDA 计算。

Card 52¶

Front: CUDA 加速 PyTorch 训练原理? Back: GPU kernel 处理 element-wise / matmul / conv, CPU 处理数据加载。

Card 53¶

Front: PyTorch DDP 通信原语? Back: AllReduce 同步梯度, 每次 backward 后。NCCL 后端。

Card 54¶

Front: vLLM PagedAttention? Back: 把 KV cache 像 OS 虚拟内存一样分页, 减少显存碎片。

Card 55¶

Front: Triton 是什么? Back: OpenAI 推出的 Python-like GPU kernel DSL, 自动调优, 易写 CUDA。

Card 56¶

Front: Flash Attention 核心优化? Back: 把 attention 计算分块, 不存中间结果到 HBM, 减少 IO。

Card 57¶

Front: LLM 推理 latency 瓶颈? Back: Memory bound — 加载模型权重 (~70 GB for 70B) 主导时间。

Card 58¶

Front: 量化 (Quantization) 如何工作? Back: FP16 → INT8 / INT4, 减少显存 ~2-4×, 轻微精度损失。

Card 59¶

Front: Docker 容器与虚拟机区别? Back: 容器共享 OS 内核 (轻量), VM 自带内核 (重)。cgroups + namespaces。

Card 60¶

Front: 为什么需要 GPU 集群? Back: 单卡显存有限 (~80 GB H100), 大模型需要多卡 / 多机并行。

Section G: 历史¶

Card 61¶

Front: 图灵机起源? Back: Turing, 1936, "On Computable Numbers"。

Card 62¶

Front: 冯诺依曼架构起源? Back: 1945 年 EDVAC 报告, 存储程序概念。

Card 63¶

Front: Unix 起源? Back: Ken Thompson, Dennis Ritchie, 1969-1971, Bell Labs。

Card 64¶

Front: C 语言起源? Back: Dennis Ritchie, 1972, 写 Unix 用。

Card 65¶

Front: LISP 起源? Back: John McCarthy, 1958, 第一个函数式语言。

Card 66¶

Front: Amdahl 定律起源? Back: Gene Amdahl, 1967, AFIPS 会议论文。

Card 67¶

Front: CUDA 起源? Back: NVIDIA, 2007, 让 GPU 通用计算。

Card 68¶

Front: MapReduce 起源? Back: Google, Jeffrey Dean & Sanjay Ghemawat, OSDI 2004。

Card 69¶

Front: Spark 起源? Back: Matei Zaharia, 2014, 加州大学伯克利分校。

Card 70¶

Front: Transformer 起源? Back: Vaswani et al., NeurIPS 2017, "Attention is All You Need"。

Section H: 工程¶

Card 71¶

Front: 优化 Python 程序常用手段? Back: 矢量化 (NumPy), Cython, JIT (Numba), 并行 (multiprocessing)。

Card 72¶

Front: PyTorch 加速方法? Back: torch.compile (Triton), mixed precision, DDP, FSDP。

Card 73¶

Front: CUDA stream 是什么? Back: GPU 命令队列, 不同 stream 可并行执行。

Card 74¶

Front: pin memory 在 PyTorch 的作用? Back: 把 CPU tensor 锁页, 加速 CPU→GPU 传输。

Card 75¶

Front: NCCL vs Gloo? Back: NCCL GPU 优化 (NVIDIA), Gloo CPU 通用 (Meta)。

Card 76¶

Front: ZeRO 三阶段优化? Back: - ZeRO-1: 优化器状态分片 - ZeRO-2: 加梯度分片 - ZeRO-3: 加参数分片

Card 77¶

Front: Tensor Parallel vs Pipeline Parallel? Back: TP 切单层 (Megatron), PP 切深度 (层间流水线)。

Card 78¶

Front: Mixed precision 训练? Back: FP16 前向 + 反向, FP32 累积, ~2× 加速, ~50% 显存。

Card 79¶

Front: Gradient checkpointing? Back: 不保存中间 activation, 反向时重计算。节省显存 ~5×, 时间 +30%。

Card 80¶

Front: torch.compile vs TorchScript? Back: torch.compile 基于 Triton (Python 风格), TorchScript 静态图。

Section I: 跨章¶

Card 81¶

Front: Ch01 集合与 Ch13 离散数学的关系? Back: Ch01 是初等, Ch13 §01 加入组合 + 复杂度 + 证明。

Card 82¶

Front: Ch03 梯度下降与 Ch13 GPU 的关系? Back: GPU 让矩阵运算并行, 训练从 CPU 几天变 GPU 几小时。

Card 83¶

Front: Ch07 Transformer 与 Ch13 分布式? Back: GPT-3 训练 1024 A100 用 1 个月, Megatron-LM 处理 tensor parallelism。

Card 84¶

Front: Ch12 GNN 与 Ch13 内存墙? Back: GNN 邻居加载是 memory bound, Ch13 §02 内存层级给出优化方向。

Card 85¶

Front: Ch11 SLAM 与 Ch13 GPU? Back: SLAM 实时要求高, GPU 并行加速特征提取 / 光流。

Card 86¶

Front: Ch05 概率与 Ch13 调度? Back: 操作系统随机调度是 Markov 过程, Ch05 概率给出分析工具。

Card 87¶

Front: Ch06 RL 与 Ch13 分布式? Back: IMPALA / R2D3 用分布式 actor, Ch13 §04 给出基础设施。

Card 88¶

Front: Ch08 CNN 与 Ch13 CUDA? Back: cuDNN 是 NVIDIA 的 CNN 库, 高度优化的 CUDA kernel。

Card 89¶

Front: Ch10 多模态与 Ch13 异构计算? Back: 多模态需要 CPU (数据预处理) + GPU (模型) 协同, 异构调度是热点。

Card 90¶

Front: Ch14 数据结构与 Ch13 离散数学? Back: 数据结构的正确性证明用数学归纳法, Ch13 §01 教基础。

Section J: 错误避免¶

Card 91¶

Front: 常见的并发错误? Back: 竞态条件, 死锁, 活锁, 优先级反转, ABA 问题。

Card 92¶

Front: GPU 内存泄漏常见原因? Back: tensor 不释放 (del 缺), 循环引用, 大 batch。

Card 93¶

Front: PyTorch DDP 常见 bug? Back: 端口冲突, 初始化顺序错, 不同步 batch_norm, world_size 不一致。

Card 94¶

Front: CUDA 内存访问对齐? Back: 32 字节对齐效率最高, 否则多次访问。

Card 95¶

Front: 分布式训练死锁? Back: NCCL bucket 满 / hang, 用 NCCL_DEBUG=INFO 调试。

Section K: 进阶¶

Card 96¶

Front: 定理证明助手 Coq / Lean? Back: 基于 Curry-Howard, 证明即程序。Lean 4 用于数学形式化。

Card 97¶

Front: 量子计算与经典计算? Back: 量子用 qubit 叠加, 经典用 bit。Shor 算法破解 RSA。

Card 98¶

Front: 神经架构搜索 (NAS) 的计算成本? Back: 一次 NAS 训练 1000 GPU-days (NASNet), 用 Ch13 集群优化。

Card 99¶

Front: LLM 训练能源消耗? Back: GPT-3 训练 ~1287 MWh, 训练单个模型碳排放 ~500 吨 CO₂。

Card 100¶

Front: 一句话总结 Ch13。 Back: 计算与操作系统 = AI 的基础设施。覆盖 5 节 — §01 离散数学 (集合/逻辑/复杂度), §02 计算机架构 (CPU/GPU/内存墙), §03 操作系统 (进程/虚拟内存/死锁), §04 并发并行 (Amdahl/CUDA/分布式), §05 编程语言 (类型/范式/编译)。是 AI 工程师的"系统栈"课。