从一次 AI 请求到整台计算机：数学、408 与推理系统的第一性原理

这篇笔记源于一个朴素的学习困惑：为什么同一条 AI 推理请求会同时牵涉线性代数、数据结构、CPU、操作系统和 TCP？为此，本文连续追踪同一份数据、同一组状态及其完成条件。

导言：从一道公式出发，建立一张可以反复使用的地图

在数学课上，$y=Wx$ 是矩阵乘法；在推理框架中，它是一个线性算子；在处理器上，它变成加载、乘加、写回等事件；在远程应用里，它只是用户发出请求后的一小段工作。每一种描述都成立，区别只在于观察的抽象层次。

割裂感来自按课程目录看待知识：线性代数谈空间与秩，数据结构谈树与图，计算机组成原理谈指令与 Cache，操作系统谈进程与页表，网络谈分组与 TCP，大模型推理又引入量化、KV Cache 与并发批处理。课程划分有利于深入，却也把一个真实任务拆到了不同书本里。

本文从应用视角向下追踪，再从硬件视角向上重建：选定一条假设的远程模型请求，依次追踪它的语义、位模式、数据结构、指令执行、资源所有权、网络消息与最终可观测结果。

贯穿全文的核心例子是一层线性变换：

模型的一层远比整个大模型简单，因此更容易建立可复核的推导：先说明计算结果的形状，再讨论权重用 FP32 还是 INT4，最后讨论它在硬件、内存和远程服务中如何执行。

一条请求的七个检查点

这七个检查点互相影响。一条模型权重的错误字节会穿过数值和执行层；一块过早复用的缓存可能表现为模型质量问题；一个过大的请求窗口可能表现为尾部延迟问题。 系统学习的意义，就在于能够沿着因果链定位问题。

这张表对应七个最基本的约束：语义明确、位宽有限、访问需要组织、指令依赖资源、共享需要同步、通信需要协议、结论需要证据。

一条共同的表达式可写作：

其中 $S_t$ 表示逻辑步骤 $t$ 的状态、$i_t$ 表示输入或事件、$o_t$ 表示输出。这个表达式不会替代算法、操作系统或协议的具体定义；它提醒我们，正确性属于状态转移及其前提，而不仅是最终一个数字。

用户请求（应用语义）
     │  序列化、编码、传输、解码
     ▼
请求对象与会话状态
     │  Tokenize、组批、调度
     ▼
计算图与张量语义 ───────→ 量化编码与字节布局
     │                            │
     └───────────┬────────────────┘
                 ▼
         指令、Cache、主存和设备
                 │
         完成事件与缓冲区生命周期
                 ▼
           Logits、采样与输出
                 │
       序列化、传输与客户端呈现
                 ▼
          正确性与实际性能

本系列的背景资料包括本站已有的科研数学笔记、操作系统状态机笔记和网络排障笔记。本文避免重写它们的目录，重点补足跨学科的连接条件与可复核的推导。

第一部分：自顶向下，追踪一条请求

1. 应用语义进入网络：文本被编码为协议字节

想象浏览器或客户端向一个假设的推理服务发起请求：

POST /generate HTTP/1.1
Host: model.example
Content-Type: application/json
Content-Length: 43

{"prompt":"请解释什么是 INT4 量化"}

这段 JSON 正文有 27 个字符，却占 43 个 UTF-8 字节：其中 19 个 ASCII 字符各占 1 字节，8 个汉字各占 3 字节，故 $19+8\times3=43$。这里不计正文末尾换行；即使只多出一个换行字节，Content-Length 也要随之变化。

HTTP/1.1 的 Content-Length 表示消息内容的字节数，不是用户看到的字符数。于是第一道跨层边界出现了：人看见的是文字，网络传输的是字节；只有先确定编码与消息边界，双方才能得到同一个 JSON 对象。

在网络上正确交付该请求，需要完成以下工作：

1. 定位目标地址：DNS 查询或已有缓存把服务名关联到可达的网络地址。
2. 建立传输：HTTPS 常见于 TCP+TLS，HTTP/3 基于 QUIC；HTTP 不必永久绑定 TCP。[R14]
3. 选择下一跳：同网段通常直接在本地链路寻址；跨网段通常交给下一跳路由器。
4. 界定消息边界：应用协议定义一条消息的编码和结束条件，不能把 TCP 的某次读取直接当成完整 HTTP 请求。
5. 记录结果状态：若连接超时，客户端只能确认未及时获得结果，不能据此断言服务端没有执行。

这就需要协议：双方共同约定如何解释字节、状态与事件。

2. 请求抵达进程：从网络栈到任务队列

网络数据通过网卡与内核网络栈进入系统。服务进程通过 socket 接口获得数据，解析请求并安排工作。典型流程可以抽象成：

网络输入 → 操作系统网络栈 → socket → 服务进程
                                       │
                                       ├─ 请求解析与鉴权
                                       ├─ 队列与调度
                                       ├─ 模型执行
                                       └─ 响应编码与发送

程序平时可以直接执行加法、读写合法的用户态内存；但创建 socket、进行某些文件和设备操作，通常需要通过操作系统提供的接口。不是每执行一行代码就发生一次系统调用。[R3]

服务处理并发请求时还需明确线程共享范围、等待条件、请求归属与队列容量。并发度的提高既可能改善设备利用率，也可能造成更长的排队。

这些不是数学公式 $y=Wx$ 能单独回答的。它们属于操作系统与服务系统的职责。

3. 模型前向计算：从 Token 到 Logits

对常见的自回归语言模型，一条请求大致会经过：

输入文本
  ↓ tokenizer：文本 → token ID
Embedding：token ID → 向量
  ↓
多层 Transformer 前向计算
  ↓
Logits：词表中各候选 token 的未归一化分数
  ↓ 选取下一个 token（贪心或采样等）
新 token → 继续生成

Logits 不是概率；softmax 可以将一组有限分数转换为概率分布：

通常为数值稳定性，先减去最大值 $m=\max_j z_j$：

由于分子、分母同乘 $e^{-m}$，在实数算术下结果不变；但在有限精度下，减最大值常能避免指数溢出。对“整行全被遮罩”的情况，还必须专门约定处理规则，不能直接让 $-\infty-(-\infty)$ 进入计算。[R17]

4. 自回归生成分成 Prefill 与 Decode

Transformer 的自注意力可以简写为：

在因果注意力中，遮罩 $M$ 阻止当前位置看到未来位置。对普通自回归生成，历史位置的 K、V 可以缓存，以避免每生成一个新 token 都重新计算历史前缀的这些投影。[R15]

• Prefill：处理已有输入序列，建立需要的状态并产出后续生成依据。
• Decode：在缓存帮助下继续生成，典型路径是每次推进一个位置并追加相关 KV 内容。

需要注意：KV Cache 不等于把整个历史 Attention 计算结果都缓存下来，也不意味着每步计算成本与历史长度无关。 在完整注意力中，新 Query 仍需访问越来越长的历史 K/V。

**这个区分还会在后面出现两次。**第 8.7.1 节用同一块权重计算 GEMV 与 GEMM 的算术强度；第 7.4.1、12.4 节则研究多条请求共享 Token 前缀时，哪些 KV 块能够合法复用。

上述过程给出了外部行为。下面从物理与形式约束反向建立内部机制，直到能够把一个 Token 的计算落实为比特编码、内存访问、指令执行和可检验的结果。

4.1 请求处理的最小时间线：状态、数据与完成条件

下面假定模型已加载、客户端使用普通 HTTPS 请求、服务端采用单进程事件循环加工作线程的简化结构。实际架构可能使用反向代理、多进程、GPU 异步队列和流式返回。

这个时间线将“数据已经存在”和“允许下一个阶段依赖它”分开。形式上，对一条需要等待的执行边 $A\to B$，正确性条件是：B 开始使用 A 的结果之前，A 已经按该接口定义完成。

这一条件会在后面以不同名字反复出现：拓扑依赖、流水线数据冒险、信号量同步、GPU 事件、TCP 按序交付。这些不是同一种实现，但都涉及状态的先后约束。

第二部分：从底层约束推导核心知识

5. 约束一：有限比特、数值范围和量化损失

5.1 $b$ 位编码的计数边界

$b$ 个二进制位有 $2^b$ 种模式。若要无歧义地区分 $N$ 个离散状态，必要条件是：

这只是基本的计数结论，却是所有数值编码的起点。

四位二进制有 16 种模式。把 1101 看成无符号整数，是 $13$；看成四位补码整数，就是 $-3$。解释规则不同，数值不同。对于 $b$ 位补码，范围是：

因此普通 INT4 补码可以编码 $[-8,7]$；某个对称量化算法可能主动只使用 $[-7,7]$，这属于算法约定，不能混为一谈。[R10]

5.1.1 从固定长度到平均长度：信息论与哈夫曼编码的联系

$b\ge\lceil\log_2N\rceil$ 约束的是用固定长度、无歧义区分 $N$ 种状态。如果符号出现频率很不均匀，允许变长且可唯一解码的编码，可以降低平均码长，而不能保证每个符号都更短。

若第 $i$ 种符号概率为 $p_i$，香农熵定义为：

例如四个符号概率为 $(1/2,1/4,1/8,1/8)$，其熵为：

可以构造对应码长为 $(1,2,3,3)$ 的前缀码，其平均长度恰好为 1.75 bit/符号。这里利用了分布不均匀和前缀可解码条件；不是说单个符号能存储小于一位。

从这一层可以把哈夫曼树和位宽联系起来：固定宽度编码保证直接定位，变长编码力争降低平均长度，二者交换的是访问简洁性、码长与解码成本。 量化则是另一类问题：允许数值近似以换取更少位数。不要把“无损熵编码”和“有损量化”混为一谈。[R6][R29]

5.2 FP32：一种有限精度的二进制科学记数法

IEEE binary32/FP32 由 1 位符号、8 位指数域、23 位小数域组成。对规格化有限数：

其中 $F$ 是 23 位小数域当作无符号整数的数值。由于规格化数的前导 1 被隐含，实际有 24 位二进制有效数字精度。[R9]

手算 $-6.5$：

• 符号位：1；
• 指数域：$2+127=129=10000001_2$；
• 小数域：10100000000000000000000。

最终是：

1 | 10000001 | 10100000000000000000000
十六进制位模式：0xC0D00000

指数域全 0 或全 1 时需要特殊解释：它们参与表示零、次正规数、无穷和 NaN，不能直接套用上面的规格化公式。

5.3 精度与范围不是同一件事

FP16 在 1 附近刻度更细；BF16 的指数范围大得多，接近 FP32 的量级范围。BF16 不等于“FP16 的更高精度版本”。

浮点精度不是“小数点后固定几位”。例如 FP32 在 $[2^{24},2^{25})$ 范围内相邻可表示整数的间隔已经是 2；按常见最近偶数舍入，$2^{24}+1$ 不能以 FP32 原样保存。这与 FP32 可以表示非常大的数并不矛盾：范围宽，不代表任意尺度都有同样细的刻度。

浮点数也不具有严格实数代数中的所有性质。例如有限精度下，$(a+b)+c$ 与 $a+(b+c)$ 可能不同。编译器重排、SIMD 分组归约、GPU 计算模式等，都可能改变舍入路径。[R9]

5.4 以 scale 将连续权重映射到有限整数编码

模型权重往往是小数，INT4 编码不能直接表示任意实数。对称线性量化可以选择：

这里假设组内至少有非零元素，使用明确的舍入语义；全零组需要单独选择合法 scale 并让编码为零。

精确可手算的例子：

原始值：[-7, -3,  7, -14, 6]
分组大小：3
第一组：[-7, -3, 7]   scale = 1
第二组：[-14, 6]      scale = 2
编码值：[-7, -3, 7, -7, 3]

按四位补码，偶数下标放低四位、奇数下标放高四位。第一个字节的形成过程是：

-7 → 4 位补码 1001 → 0x9 → 低四位
-3 → 4 位补码 1101 → 0xD → 高四位

     高四位  低四位
       1101    1001  = 0xD9（不是 0x9D）

三个载荷字节依次为：

[-7, -3]  → 0xD9
[ 7, -7]  → 0x97  ← 同一个字节中的两个元素使用不同量化组的 scale
[ 3, pad] → 0x03  ← 奇数个元素，尾部高四位补 0

因此，五个 INT4 元素的打包载荷为 3 字节，此外还有两个独立保存的 scale。0xD9 的高低半字节顺序属于打包约定，不是直接由机器大小端决定。分组边界与字节边界可以相互错开，跨组测试因此不能省略。[R10]

5.4.1 四种不同的“位置”：位、字节、张量和物理地址

同样一个逻辑权重 $W_{ij}$，在不同层面的坐标可能是：

1. 数学坐标：第 $i$ 行第 $j$ 列，定义算子语义；
2. 逻辑元素序号：行优先连续布局中 $k=i\cdot n+j$；
3. 编码后字节位置：FP32 是 $4k$ 字节偏移，连续 INT4 载荷是 $\lfloor k/2\rfloor$ 字节偏移并根据奇偶选择 nibble；
4. 实际访存地址：缓冲区基址加上存储偏移，之后再由地址转换机制映射到实际存储。

例如上节量化载荷 D9 97 03 的第三个量化整数 $q_2=7$ 位于第二个字节的低四位；它属于第一组 scale。第四个量化整数 $q_3=-7$ 位于同一个字节的高四位，却属于第二组 scale。字节边界与量化组边界因此彼此独立。

再看 FP32 位模式。$-6.5$ 的数值位模式是 0xC0D00000。假设采用 8 位字节、小端字节序，把该 32 位字存入连续字节地址时顺序通常是：

低地址 → 高地址：00 00 D0 C0
按数值书写的 32 位十六进制位模式：C0D00000

这没有改变浮点数的值，只是规定多字节对象放进内存时的排列方式。位模式、内存字节序、压缩打包方式和张量布局属于不同层次的约定，不能相互代用。[R9][R10]

5.5 量化的多对一映射与不可逆性

例如 scale 为 $0.1$ 时，某些彼此不同的小数会被映射为同一整数 $q=2$。只知道 $(q,s)$，无法知道原数是哪一个。反量化得到的是代表值 $\hat x=qs$，不是恢复丢失的信息。

这和线性代数里“不同输入落到同一个输出”有共同的不可逆性问题，但注意：量化一般不是线性映射，不能直接用矩阵的秩分析量化器。

5.5.1 同样叫“4 位”，不代表可以互换：FP4、NF4 与 TF32

量化工程中，除了整数 INT4，还会遇到其他名字：

例如 ONNX FLOAT4E2M1 定义了自己的数值编码和可表示值；QLoRA 提出 NF4 用于针对权重分布的量化；NVIDIA 明确将 TF32 描述为计算模式，并说明它并非新的通用存储类型。[R19–R21]

因此在讨论“模型用什么精度”时，务必区分：文件编码、内存中的张量格式、算子输入格式、乘法与累加模式。

5.6 存储位宽、乘法位宽和累加位宽要分开

W4A16 一般表示权重采用四位量化存储、激活采用十六位表示；它不保证“整个矩阵乘法都用四位算术完成”。某些实现会边读取边解包、反量化，再以 FP16/BF16 等精度计算，以 FP32 累加。[R11]

判断一个算子时，应分别问：

1. 权重和激活的存储格式与字节排布；
2. 实际乘法使用的表示与硬件通路；
3. 中间求和的累加精度；
4. 输出的舍入规则与存储格式。

这四件事并不总相同。

本节最重要的结论：数值类型首先规定“位模式如何解释”；量化则是在存储成本与信息损失之间做约定。文件更小不等于计算更快，低精度也不等于低质量——两者都需要具体测试。

6. 约束二：线性代数给出计算语义和可证明关系

6.1 “矩阵是数字表格”只是第一层理解

从线性代数看：

意味着把 $n$ 维输入变换成 $m$ 维输出。既可以按行理解为多次点积，也可以按列理解为输入系数对列向量的线性组合：

其中 $w_j$ 为 $W$ 的第 $j$ 列。MIT 18.06 一直强调列空间、零空间、秩和方程组之间的联系，而不仅是矩阵乘法的机械步骤。[R5]

从计算机科学的角度，这给出了一个更重要的边界：算法与硬件可以改变计算顺序和存储方法，但不能未经许可改变算子的数学语义。

6.2 秩、可逆性和“被压掉的信息”

对 $n$ 阶方阵，以下条件等价：

其中 “方阵”不可省略。若秩不足，零空间可能包含非零向量 $v$，使 $A(x+v)=Ax$；这样的映射丢失了区分 $x$ 与 $x+v$ 的信息。

考研练习：

第二列是第一列的两倍，$\operatorname{rank}(B)=1$；$(-2,1)^\top$ 属于零空间。故 $B$ 不可逆。不要只看“行列式为零”就误断秩一定是 $n-1$：零空间维数可能更大。

6.3 线性方程组：增广矩阵决定有没有解

对 $Ax=b$：

• $\operatorname{rank}(A)<\operatorname{rank}([A\mid b])$：无解；
• 二者秩相等且等于未知数个数：唯一解；
• 二者秩相等但小于未知数个数：无穷多解。

举一个含参数的系统：

相减得到 $(a-1)x_2=c-1$。不能未经讨论就除以 $a-1$。

• $a\ne1$：唯一解；
• $a=1,c=1$：两式重复，无穷多解；
• $a=1,c\ne1$：矛盾，无解。

这其实是在训练一种严谨的条件意识：每次变形之前，先核对操作的合法前提。这种习惯在算法正确性证明、数组边界检查和协议状态转换中同样重要。

6.3.1 从最小二乘到反向传播：正交条件与梯度为何共享 $A^\top$

设 $A\in\mathbb R^{m\times n}$，目标向量 $b\in\mathbb R^m$。当 $Ax=b$ 无精确解时，最小化残差平方：

记 $r=Ax-b$。从几何角度，最优的 $Ax$ 是列空间中距离 $b$ 最近的点，残差应与列空间正交，因此：

从微积分角度，同一个目标函数的梯度是：

令梯度为零，得到正规方程：

这不是两个巧合的公式。几何中的“残差与所有可调方向正交”，正是优化中的“一阶变化为零”。更重要的是，在线性层 $y=Ax$ 的反向传播中，上游梯度 $g=\partial L/\partial y$ 经过输入端时产生 $A^\top g$；同一个转置算子连接了求解方程、优化算法与神经网络训练。

数值求解仍有边界：若 $A$ 列不满秩，$A^\top A$ 不可逆；在满列秩且采用二范数条件数时，$\kappa_2(A^\top A)=\kappa_2(A)^2$，正规方程会放大病态程度。工程上通常优先考虑 QR 或 SVD，避免显式构造 $(A^\top A)^{-1}$。[R5]

训练与推理的资源账本由此分开：推理主要进行前向计算并维护生成状态；训练还要保存或重算用于求梯度的激活、执行反向传播并维护优化器状态。可延伸阅读本站优化算法笔记。

6.4 特征值、SVD 和低秩近似是不同工具

如果 $Av=\lambda v$，那么 $v$ 是特征方向；它可以帮助分析线性系统 $x_{t+1}=Ax_t$ 沿某个方向的重复变换。

对实对称矩阵，可进行正交对角化；二次型 $x^\top Ax$ 的正定性可以由全部特征值为正判断。二次型的合同变换 $C^\top AC$，与一般相似变换 $P^{-1}AP$ 不应随意混用。[R5]

奇异值分解则是：

用前 $r$ 个奇异值构建的截断近似 $W_r$ 满足 Eckart–Young–Mirsky 定理对应的低秩最优性条件（例如对 Frobenius 范数或谱范数而言）。它可以作为研究低秩压缩的理论基础，但参数个数减少不代表模型整体质量一定保持。

6.5 误差：把“近似正确”变成可测量的约定

对 $y=Wx$，若仅量化权重得到 $\hat W=W+E$，在精确算术中有：

但真实浮点实现还会产生舍入误差；在深层网络中，误差会经过多个非线性和线性变换，不能只靠单层的这个不等式证明完整模型质量。

数值验证至少要分清以下层次：

• 比特级规则：nibble 顺序、页号、整数编码等必须精确；
• 浮点近似：使用事先规定的绝对/相对容差，并考虑输入尺度；
• 模型层质量：使用代表性数据集与目标指标；
• 端到端性能：测总响应时间，而非孤立算子时间。

常见的浮点比较准则形如：

这里 $b$ 是参考结果；$\mathrm{atol},\mathrm{rtol}$ 必须由具体算子、精度、误差预算决定，不能为了让测试通过随意调大。

这一层的连接：线性代数给出变换与误差的参照，数值表示限定可用数值集合。算子优化前明确数学语义、舍入和容差，性能结果才有可比性。

7. 约束三：数据结构组织访问关系和状态不变量

抽象模型中的张量、请求、缓存块和工作队列，都需要在真实系统中组织起来。选择数据结构，首先要根据访问模式设计表示。

7.1 一个公平比较：数组与链表

数组的随机访问优势来自可由基址与偏移直接定位；链表的局部修改优势来自显式链接。“链表插入是 $O(1)$”必须包含已经定位到插入位置的前提。[R6]

手算行优先数组偏移：$A$ 的形状为 $[2,3]$，元素长度 4 字节，存储连续且零基下标。则 $A[1][2]$ 的元素偏移为 $1\times3+2=5$，字节偏移为 $20$。如果改成带 stride 的转置视图，形状可以改变而底层字节不必复制；算子必须尊重 stride，而不能仅凭 shape 猜测布局。

7.2 栈、队列与环形缓冲区维护访问顺序

• 栈 LIFO：递归调用栈、表达式处理、深度优先搜索；
• 队列 FIFO：广度优先搜索、待处理任务队列、缓冲区；
• 环形队列：在固定缓冲区中重复使用位置。

常见“浪费一个槽位”的环形队列模型：容量数组大小为 $N$、front 指队头、rear 指下一次插入位置：

元素数是 $(rear-front+N)\bmod N$，但该模型最多只存 $N-1$ 个元素。其他环形队列模型可以使用计数器或不同指针语义，不可直接混用公式。[R6]

7.3 树与堆：把操作需要的约束写清楚

二叉搜索树 BST：大小关系约束整个子树。左子树的所有节点都必须落在当前节点的左侧取值范围，右子树同理。因此：

      10
     /
    5
     \
      12   ← 违反 BST：12 在 10 的左子树中

递归检查 BST 必须传递祖先施加的取值范围；仅比较父子结点会遗漏祖先约束。

堆：最大堆保证父节点的键不小于子节点，并通常保持完全二叉树形状，却不要求左子树的所有元素小于右子树。堆顶查询 $O(1)$，插入与删除堆顶为 $O(\log n)$；自底向上建堆可做到 $O(n)$；不能机械地把每个节点的最坏下沉层数都乘上 $n$。[R6]

哈夫曼树用于最小化给定符号权重下的带权路径长度。本文第 5.1.1 节已给出信息论视角；第 17.3 节保留 408 的手算例题。这里不再重复构造过程，转而连接与真实推理请求更直接相关的前缀匹配。

7.4 哈希与 B+ 树不是互相取代的“万能索引”

哈希通过键映射到桶或槽位，平均效率与散列函数、装载因子、冲突处理等有关；遇到有序范围查询时，哈希一般不能天然保持键的全序。B+ 树则借助多路结构和叶层组织适合磁盘/页式索引及范围访问。[R6]

因此选择数据结构，要先问：

1. 等值查找或有序范围访问的比例；
2. 插入、删除与有序遍历的需求；
3. 工作集大小、内存容纳程度与页面访问成本；
4. 允许的索引空间和维护开销。

同一个“查找”需求，在不同约束下会有不同最优选择。

7.4.1 从文本前缀到 KV 物理块：字符串、树、哈希和链表进入同一条请求

设两个请求共享一段系统提示词：

请求甲：共同前缀 A B C D E F G H + 后续 X…
请求乙：共同前缀 A B C D E F G H + 后续 Y…

这条请求在进入模型前、进入模型后，各有一类不同的“前缀”问题。

第一类是文本与 Token 序列的匹配。 分词器维护词表和合并规则，可能使用哈希表定位词项或相邻候选；一部分 BPE 实现用优先队列维护下一次合并的候选。Trie/AC 自动机适合词典匹配和多模式匹配，KMP 适合单模式字符串匹配。具体分词器算法与数据结构需以实现为准，不能断言所有 Tokenizer 都一定由 Trie 或堆驱动。[R35]

第二类是已经计算过的 Token 前缀能否复用 KV。 因果模型对完全相同且配置兼容的历史 Token 前缀，可以复用这段前缀对应的缓存。不同推理框架对此采用了不同数据结构：

以 vLLM 的公开设计为例：缓存管理器维护块哈希映射、请求到块的关系、引用计数及空闲块双向链表；当空间不足时，可按规定顺序淘汰闲置缓存块。SGLang 的 Radix Cache 则以压缩前缀路径组织可复用状态。前缀树和块哈希不是互相矛盾的“唯一正确结构”，它们是不同工程方案。[R30][R31]

这里不能仅比较用户看到的文字。实际共享判断应基于相同的 Token ID 前缀及影响模型计算的必要配置：模型/权重版本、位置处理、适配器与多租户隔离等。缓存策略设计既要考虑命中率，也要保证缓存数据没有被错误跨请求修改或泄漏。

于是 408 中的字符串、树、哈希、链表与队列不再只是课堂例子。它们分别解决匹配、索引、共享、释放和调度的问题，并共同影响一次请求的 TTFT、内存与正确性（第 12 节继续追踪）。

7.5 图：关系就是另一种数据

设有向图邻接矩阵 $A_{ij}\in\{0,1\}$，其中 $A_{ij}=1$ 表示存在 $i\to j$。那么：

统计从 $i$ 到 $j$ 的长度为 2 的游走数量（允许重复顶点或边，不能直接称为简单路径数）。这是一条真正的跨学科联系：图关系可以通过矩阵代数分析。

但图算法的目标各有不同：

最小反例：$S\to A$ 长度 2，$S\to B$ 长度 5，$B\to A$ 长度 $-4$。Dijkstra 首先确定 A 的距离 2，但经 B 可得到距离 1。负边破坏了“确定后不会再变小”的前提。[R6]

计算图中的节点依赖同样组成 DAG；拓扑序约束了哪些运算必须先完成，实际 CPU/GPU 调度还要额外处理资源冲突与异步完成。

7.6 二分查找：复杂度不如不变量重要

找有序数组中第一个满足 a[i] >= target 的位置。维护左闭右开未知区间 [left,right)：

#include <cstddef>
#include <vector>

// a 非递减，返回第一个 >= target 的位置；不存在返回 a.size()。
std::size_t lower_bound_index(const std::vector<int>& a, int target) {
    std::size_t left = 0, right = a.size();
    while (left < right) {
        std::size_t mid = left + (right - left) / 2;
        if (a[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

不变量：[0,left) 中的元素均小于 target，[right,n) 中的元素均大于等于 target。每轮缩小未知区间，最终交界点即答案。[R6]

它不仅是 $O(\log n)$ 算法，更是设计 → 维护不变量 → 证明终止的微型范例。

7.6.1 把循环不变量写成前置条件与后置条件

对任何可复用算法，建议把接口契约写成三段：

前置条件：输入数组非递减；索引范围合法。
循环不变量：[0,left) 全部 < target；[right,n) 全部 >= target。
后置条件：返回值 p 在 [0,n]，前面全部 < target，后面全部 >= target。

形式化方法常用 Hoare 风格的 $\{P\}\;C\;\{Q\}$ 表达“满足前置条件 $P$ 的状态执行程序 $C$ 后，若正常终止则满足后置条件 $Q$”。它本身不自动证明程序会终止，因此还需要诸如 right-left 严格下降这样的终止论证。

这个思想可以迁移到系统代码：函数 decode_int4 的前置条件包含编码格式、载荷长度和 scale 数；后置条件包含输出元素数和误差性质。到了异步设备接口，后置条件则必须区别“提交已接受”和“设备执行已完成”。

7.7 复杂度还要区分单次最坏与摊还成本

动态数组每次装满容量翻倍，某次扩容复制可能是 $O(n)$；但连续追加 $n$ 个元素，扩容复制总量：

因此 $n$ 次追加总成本 $O(n)$，均摊每次 $O(1)$。均摊分析约束的是整个操作序列的成本，不涉及概率意义上的“平均运气”。

这一层的连接：数据结构决定定位成本，算法不变量决定合法操作的边界。KV 块表、请求队列、缓存淘汰与 TCP 重组，都必须同时说明数据结构和状态更新规则。

8. 约束四：计算机组成原理把程序落实为物理事件

8.1 从布尔代数到逻辑门、ALU 和 CPU

一台数字计算机可以由逻辑门与状态元件构造。组合逻辑根据当前输入决定输出；时序逻辑不仅看当前输入，还与已保存的状态有关。[R1]

例如，一个一位全加器计算两个二进制位 $a,b$ 与进位 $c_{in}$：

把这些单元串接，就可以在更宽的字长上做整数加法。当然，真实高速加法器不一定使用最朴素的串行进位结构：加速进位传播也是硬件设计的代价交换。

寄存器保存状态，组合逻辑执行状态转换；控制逻辑决定下一步做什么。Nand2Tetris 用从逻辑门、ALU 到机器语言和简易操作系统的构造路径，把这些抽象串成一条可操作的学习路线。[R1]

8.2 高级语言不是 CPU 直接“理解”的语言

一段代码：

sum += a[i] * b[i];

可能经过：

源代码
  ↓ 编译器与优化
指令序列
  ↓ 指令集架构 ISA
机器指令解码
  ↓
载入数据、乘加、更新寄存器/内存

这里的 ISA（指令集架构），可以理解为软件与处理器之间约定的可见接口：包括指令语义、寄存器、寻址方式等。微架构则是某个 CPU 怎样实现这些 ISA 行为；同一 ISA 可有不同的流水线、Cache 与执行单元设计。[R2]

这解释了：

• 编译通过只说明满足了一系列编译条件，不说明数值结果正确；
• 同一程序可以在不同微架构上得到不同速度；
• 指令数少不必然更快，尤其若访存和等待变得更严重。

8.2.1 源代码、机器指令、数据通路之间的三层约定

以循环中的 sum += a[i] * b[i] 为例，概念上会涉及以下三层：

编译器可以向量化、展开循环或重排部分独立操作，但必须遵守所处语言模式和优化选项对可观察行为的约束。浮点重关联常依赖额外的优化许可，并非在任何编译设置下都合法。即使机器指令个数减少，因缓存失效或依赖增加，实际运行时间仍可能变长。[R2]

这层区分是组成原理与高级语言、算法之间的主要桥梁：ISA 定义能执行什么，微架构决定怎样执行，算法决定需要执行什么结构的操作。

8.3 补码加法、溢出与浮点舍入是不同语义

在 $w$ 位补码机器上，若只保留低 $w$ 位，普通二进制加法符合模 $2^w$ 运算；但有符号数发生溢出后，编程语言如何定义程序行为必须看语言规范。不能把硬件低位截断，直接当成 C/C++ 任意有符号溢出的合法语义。

例如四位补码：

  0111  (+7)
+ 0001  (+1)
------
  1000  (-8 按四位补码解释)

在这个固定四位的按位运算示例里，结果出现符号溢出；这不代表数学上的 $7+1=-8$。程序若想正确处理更大的数学结果，就要选择足够位宽或显式做溢出检查。

浮点又不同：它需要对阶、有效数字运算、规格化、舍入及特殊数处理。对 FP32、BF16、TF32 等，存储格式与某一具体乘法/累加通路的精度可以不同。[R9]

8.4 CPU 流水线把吞吐提升与执行依赖放在一起

把教学 CPU 的指令过程抽象为：

取指 IF → 译码 ID → 执行 EX → 访存 MEM → 写回 WB

实际 CPU 可能复杂得多，且不一定采用这五级。流水线的目的，是让不同指令的不同阶段在时间上重叠，提高单位时间完成的指令数量。

但会遇到几类约束：

• 结构冒险：两条指令同时争用一个不可同时使用的硬件资源；
• 数据冒险：后一条指令要读取前一条尚未产生的结果；
• 控制冒险：分支方向尚未确定，后续取指路径不确定。

例如：

I1: r1 = r2 + r3
I2: r4 = r1 * r5

I2 对 I1 存在真实数据依赖；硬件可以转发、等待或通过其他方式处理，但不能在缺少合法的数值依据时假装依赖不存在。

流水线提高吞吐，不意味着单条指令的延迟必然按级数成比例下降。也不意味着源代码中独立的所有操作都能无限并行：依赖、端口、寄存器、缓存均可能成为约束。

8.5 Cache：既要算位置，也要算为什么命中

考虑一个纯教学的32 位地址、32 KiB 数据缓存、64 字节块、4 路组相联的例子：

因此：

• 块内偏移需要 $\log_2 64=6$ 位；
• 组索引需要 $\log_2 128=7$ 位；
• 剩余 Tag 为 $32-6-7=19$ 位。

32 位地址：
[ Tag 19 位 | Set index 7 位 | Block offset 6 位 ]

这只是给定地址与缓存映射规则的题型分析，不意味着所有真实 CPU 的缓存都直接用物理地址按这个形式索引。实际缓存可能采用更复杂的虚实地址组织、替换策略、预取以及多级结构。[R2]

Cache 有效的主要依据，是程序访问常具有：

• 时间局部性：刚用过的数据，短期可能再用；
• 空间局部性：用了某个地址，附近地址可能接着被访问。

这也解释了数据结构为何影响硬件表现：连续数组的遍历容易被缓存块和预取机制利用；高度分散的链表可能产生大量指针追逐。

8.6 AMAT：不能把一次 TLB 未命中当成缺页

常见 Cache 教学模型用平均访存时间：

但要小心具体题目有没有把“命中时间”包含在未命中路径、是否还有多级缓存等。

TLB 缓存的是虚拟页到物理页的地址转换，并非普通数据缓存。举一个明确的教学模型：

单级页表；无缺页；TLB 查找 10 ns
一次内存访问 100 ns；TLB 命中率 90%
TLB 先查，查找与后续访问不重叠

命中：$10+100=110\;\mathrm{ns}$。未命中但页面在内存：$10+100+100=210\;\mathrm{ns}$。平均：

TLB 未命中不等于缺页。前者可能只是地址转换不在小型缓存里；后者是虚拟页面映射或驻留情况需要操作系统处理。[R3]

8.7 性能上限：计算能力不是唯一上限

设某个计算需要 $F$ 次浮点运算、跨所分析的存储边界搬运 $Q$ 字节；机器对这类运算的有效上限为 $C$ FLOP/s，对该边界带宽上限为 $B$ B/s。在可以重叠的理想下界模型中：

算术强度：

这是一种 Roofline 思路；真实时间还受启动、依赖、非算术指令、缓存行为、调度、同步等影响。[R12]

对 $W\in\mathbb R^{4096\times4096}$，FP32 权重主体为：

矩阵向量乘需要约 $2\times4096^2\approx3.36\times10^7$ 次浮点运算（乘和加分别计一次）。假设这次权重必须从所研究的存储层读取一次、带宽 100 GB/s、计算能力 5 TFLOP/s：

• 计算能力下界约 $0.00671$ ms；
• 权重搬运下界约 $0.67109$ ms。

这组数字的单位换算也值得单独检查：$64\,\mathrm{MiB}=64\times2^{20}=67\,108\,864\,\mathrm{B}$，而 $100\,\mathrm{GB/s}=100\times10^9\,\mathrm{B/s}$，所以 $67\,108\,864/(100\times10^9)\,\mathrm{s}\approx0.67109\,\mathrm{ms}$。MiB 使用 $2^{20}$，GB/s 使用 $10^9$；不能在计算中混用名称而不统一单位。

根据示例机器的计算/带宽比，理想平衡点是：

矩阵向量乘的算术强度约为 $0.5\,\mathrm{FLOP/B}$，远低于平衡点。这是关于这一层 GEMV 的分析，不是具体 CPU/GPU 的实测成绩，更不是 LLM 的 token/s。

若 INT4 两值一字节、每 128 个权重保存一个 FP32 scale：

合计 $8.5$ MiB；相同带宽下，单看载荷与 scale 读取下界约 $0.08913$ ms。但解包、scale 读取、反量化与算子实现可能增加工作，因此不能把内存压缩倍数当成实际加速倍数。

8.7.1 同一线性层的两种形态：Decode 是 GEMV，Prefill 是 GEMM

第 4 节区分了 Prefill 和 Decode。现在使用同一矩阵 $W$ 和同一台假设机器计算二者的资源账本，便能把推理阶段和计算机组成原理直接接起来。

单请求逐 Token Decode 时，简化成 $y=Wx$。对于 $4096\times4096$ FP32 权重：

而处理 $T$ 个位置的 Prefill 线性投影，可写成矩阵乘矩阵：

理想情况下，$W$ 可以在分块计算中被反复使用。若对所研究的主存边界只计读取一次权重、读取一次输入、写入一次输出，则：

取 $T=512$，矩阵乘法约需 $17.18\times10^9$ FLOP；权重 64 MiB、输入 8 MiB、输出 8 MiB，共计 80 MiB 的理想边界流量。于是 $I=204.8\,\mathrm{FLOP/B}$。在前述 5 TFLOP/s、100 GB/s 的理想上限下，计算下界约 3.436 ms，而这部分流量的搬运下界约 0.839 ms，计算能力成为这个局部模型的主要约束。[R12][R36]

由此可见，同一权重矩阵在逐 token 的单请求 Decode 和大批位置同时处理的 Prefill 中，算术强度可能截然不同。Continuous Batching 试图让多个请求同一轮的计算共享权重访问、形成更有效的批处理，也是这一资源逻辑的应用之一。

这里的矩阵分析不等于给完整 Transformer 下了通用结论：真实 Prefill 还包含 Attention、归一化、数据准备等，实际主存流量取决于缓存、分块与算子融合；并发 Decode 也可能变成大批 GEMM。真正应测的是目标工作负载的算术强度、设备资源占用与端到端延迟。“Prefill 常更容易形成计算密集的 GEMM，单请求 Decode 常面临权重带宽压力”是有条件的工程规律，不是不可改变的分类标签。

8.8 总线、设备控制器、中断与 DMA 数据搬运

CPU 访问存储、网络和外设，需要由总线、互连、控制器等协作完成。设备可以用中断通知事件，DMA 机制可以在符合设备和平台约束的情况下搬运数据，减少 CPU 逐字节参与数据复制的需求。

但 DMA 不等于“完全没有 CPU 开销”，更不意味着传输一旦被提交就已经完成。提交、进行中、完成、可安全复用是不同的事件阶段；设备驱动、缓存一致性与 DMA 可见性也需要清楚约定。

这一层的连接：数值格式决定字节流量，数据结构决定访问模式，编译器和 ISA 决定可执行指令，存储层级决定一部分主要延迟。

9. 约束五：操作系统管理资源、并发和持久性

OSTEP 用三个词组织操作系统：虚拟化、并发、持久化。这比简单把“进程、内存、文件”堆成目录，更能回答为什么需要 OS。[R3]

9.1 虚拟化在逻辑地址空间与物理内存之间建立映射

操作系统向程序提供进程、地址空间、文件等抽象。单个进程看到自己的虚拟地址布局；实际物理内存可能被多个进程和内核以受控方式使用。[R8]

对大小为 $2^{12}=4096$ 字节的页面：

虚拟地址 0x3123 = 虚拟页 3 + 页内偏移 0x123

假设页表把虚拟页 3 映射到物理页框 9：

物理地址 = 0x9000 + 0x123 = 0x9123

程序的地址可以逻辑连续而对应物理页离散；换页框不应迫使所有高层算法重新改写索引。注意页表由操作系统建立、硬件地址转换机制执行，用户态不能凭自己定义一个数组就改写真实的 CPU MMU。

9.2 进程、线程与系统调用不是同义词

• 程序：磁盘等介质上保存的代码及相关数据；
• 进程：一次执行实例及其地址空间、资源与执行上下文；
• 线程：进程内部的执行流，线程通常共享进程地址空间，但有自己的执行位置、寄存器与栈；
• 系统调用：进程请求内核提供受控服务的接口。

一次系统调用可能返回同一个进程；它不意味着必然发生进程切换。用户态/内核态是执行权限层次，进程切换是另一种事件。

9.3 CPU 调度与响应、周转、等待指标

典型就绪/运行/阻塞状态可以描述资源等待：

就绪  --得到 CPU--> 运行
运行  --时间片用尽或被抢占--> 就绪
运行  --等待 I/O/条件--> 阻塞
阻塞  --等待事件完成--> 就绪

给出 FCFS 简化例题，忽略切换开销：

0 ─── P1 ─── 4 ── P2 ── 6 ─ P3 ─ 7

周转时间 $T_i=C_i-a_i$，分别为 $4,5,5$，平均为 $14/3$。在无额外 I/O 等待的简化模型中，P2 等待 CPU 的时间 $5-2=3$。对时间片轮转、SJF 等，应根据各自规则重新画事件时间线。

9.4 并发：正确性不是“每个线程单独都正确”

两个线程共享 counter，若都把 counter++ 理解为“读—加—写”的不可分操作就会出错。共享变量可能被交错读写而丢失更新；在 C/C++ 或 Rust 等具体语言中，未正确同步的数据竞争还可能违反语言内存模型，不能直接用一种确定的交错结果描述全部后果。

同步工具解决的问题不同：

• 锁 Mutex：保护临界区，管理互斥；
• 信号量 Semaphore：计数许可并可表达条件同步；
• 条件变量：配合互斥保护的条件谓词等待状态改变；
• 原子操作：按特定内存模型进行单次原子读写/读改写，不自动解决任意复合业务不变量。

生产者–消费者是最值得手写的 408 同步模型。设有 $N$ 个缓冲位置：

empty = N; full = 0; mutex = 1

生产者：
  生产数据
  P(empty)
  P(mutex)
  写入缓冲区
  V(mutex)
  V(full)

消费者：
  P(full)
  P(mutex)
  取出数据
  V(mutex)
  V(empty)
  消费数据

如果缓冲区已满，生产者先拿 mutex 再等待 empty，它可能持锁阻塞消费者腾位置，从而造成死锁。PV 顺序是正确性的一部分，不是格式细节。[R3]

9.5 死锁与银行家算法：资源够分不等于分后安全

死锁涉及互斥、占有并等待、不可剥夺、循环等待四个必要条件。银行家算法通过分配前的安全性检查，避免系统进入不安全状态。

核心向量关系：

给一个两类资源的教学例子，初始 Available=(1,1)：

先假设 P0 完成，资源变为 (2,1)；再 P1 完成，变为 (2,2)；最后 P2 完成。因此存在安全序列 P0→P1→P2。

若此时 P1 要求 (1,0)，表面可分配，但试分配后 Available=(0,1)，三者剩余需求都至少需要一个第一类资源，无法找到可保证完成的第一个进程。该次试分配会进入不安全状态，应拒绝或暂缓。

不安全不等于此刻已经死锁；它表示在所采用的最大需求模型下，无法保证所有进程都能安全完成。[R3]

9.6 分页、TLB、缺页与页面置换是四个不同问题

TLB miss 不必然产生 page fault；page fault 也不必然意味着程序非法。 按需载入文件页面、匿名内存首次写入等，都可能触发可处理的缺页。[R8]

FIFO、LRU、OPT 页面置换关注不同的信息：进入顺序、最近访问历史、未来访问情况。OPT 是理想离线比较基准，不是系统总能实时知道未来。

9.6.1 地址转换与真实数据布局是两类不同映射

应用在计算 W[i][j] 时，先根据张量的行列形状或 stride 得到虚拟地址偏移；之后处理器根据当前地址空间的有效映射得到可访问的物理位置。这两件事互不替代：

行列索引 → 张量 stride 与 dtype → 用户态虚拟地址
                                      ↓
                       TLB/页表与访问权限检查
                                      ↓
                         实际物理页和页内偏移

如果数组布局错误，即使 TLB 全部命中，也会访问错误的逻辑元素；如果地址没有权限，即使形状数学上正确，也不能合法访问。

这还解释了 mmap、共享 Arc<[u8]>、GPU 设备缓冲的边界：共享字节视图不代表磁盘文件已经按需映射；文件映射也不意味着 GPU 可以零成本读取设备主存；GPU 设备指针不应按普通 CPU 指针任意解引用。每一次“零拷贝”优化，都必须注明究竟避免了哪一段复制。[R8]

9.7 文件系统与 mmap：从“逻辑文件”到实际页面

文件系统把文件名、目录、文件偏移与实际存储组织起来。读取文件时，操作系统页缓存可能保留数据，提高后续访问性能；使用 mmap 可以把文件区域映射进进程地址空间。[R8]

但：

• 建立映射不等于文件已经全部读进 RAM；
• 进程“拿到虚拟地址”不等于对应页面已经驻留；
• mmap 不等于 GPU 能直接零成本读取磁盘；
• 普通写操作返回不必然等于故障后数据已经持久化。

对模型加载而言，需要区分逐张量复制、共享字节视图、文件内存映射、GPU 传输。这些实现能在不同边界减少复制，但“零拷贝”必须说明究竟消除了哪一段复制。

9.8 预分配与零分配热路径的成立条件

某些推理内核希望把输出区、Scratchpad、页池提前配置好，让单步执行不再动态申请堆内存。这有利于控制某类延迟毛刺，但不意味着系统不用堆、不发生缺页、不受调度影响。

预分配与运行时不新增分配不同；即使没有 malloc，一个异步设备尚未完成读取的缓冲区也不能立刻复用。需要把代码作用域、实际读写完成事件和内存所有权统一考虑。

这一层的连接：操作系统提供地址空间与资源控制，线程同步建立合法的执行先后关系，文件系统与持久性机制决定状态在进程或机器重启后还能保留什么。

10. 约束六：计算机网络在独立主机之间建立协议语义

网络让彼此独立的主机依靠约定的消息和状态机交换信息。另一台机器可能慢、可能断开，也可能已经处理了请求但无法返回结果。

10.1 分层协议的功能边界与责任划分

常见五层教学模型：

这里的五层是教学抽象，OSI 七层会进一步区分表示层、会话层；真实协议边界还会出现 QUIC 这样的跨传统分类的设计。[R4][R14]

10.1.1 从 IP 包到应用消息：边界并不天然一致

传统 TCP 提供有序字节流，它不保留应用层每次 write 的消息边界。应用可能把一条请求拆成几次读取，也可能一次读取获得多条消息的字节片段。应用层必须根据 HTTP 的长度、分块、帧或其他编码规则进行重组。[R13][R14]

例如发送端连续写入两个长度为 4 的应用记录：ABCD、EFGH，接收端的 TCP 读取完全可能先得到 ABC，再得到 DEFGH。这不是传输错误；如果应用按“每次读取就是一条完整记录”解析，才会出错。

分层实现由此引入一种严格的接口边界：数据链路帧、IP 数据报、TCP 字节流和应用层消息，不是同一个计数单位。 后续计算 MTU、TCP MSS、ACK 和 Content-Length 时，必须先确定计算对象。

10.2 发送时延和传播时延完全不同

分组长度 $L$ bit、线路速率 $R$ bit/s、距离 $d$ m、传播速度 $v$ m/s：

例如：1500 B 数据以 100 Mb/s 发送，经 2000 km、信号传播速度 $2\times10^8$ m/s 的链路（忽略其他开销）：

从开始发送到最后一个比特到达，约 $10.12$ ms。提高带宽能缩短发送时间，不能直接消除传播距离。

若采用存储转发、同速的 $K$ 条链路、$P$ 个等长分组，忽略处理和排队，分组发送流水化时：

这里的条件非常重要；不同速率、不同长度、拥塞或中继实现，必须重新画时间线。

10.3 奈奎斯特、香农：带宽 Hz 和速率 bit/s 不一样

在理想无噪声、带限基带的教学模型中，$M$ 种不同信号状态、信道频率带宽 $B$ Hz，可得奈奎斯特型上限：

在带限加性白高斯噪声模型中，香农容量：

例如 $B=3000$ Hz、$M=4$，上述无噪声奈奎斯特模型得到 $2\times3000\times\log_2 4=12000$ bit/s。这不是“所有 3 kHz 信道永远只能传 12 kb/s”，因为它还依赖每符号的状态数和信道模型。

若给信噪比的单位是 dB，需要先换算：

例如 30 dB 对应的功率比是 $1000$，不能直接把 $30$ 当成 $S/N$ 填进去。这两类上限基于不同假设，不要不分条件地代入同一题。

10.4 链路层：CRC 检错不等于端到端正确

CRC 把数据与生成多项式看作 GF(2) 上的多项式；校验时用异或进行模 2 除法。它能检测符合其检错能力范围的某些错误，但CRC 余数为零不代表绝对无错，也不是身份认证。

同样，链路层某一跳收到一帧，不代表远端应用已经收到完整请求：路由、传输、应用各有独立的处理状态。

CRC 手算练习：数据 1101，生成多项式位串 1011（三次），先补三个零得到 1101000，用异或做模 2 除法，余数是 001，所以发送 1101001。检查者用同一生成多项式得到零余数，代表“没有检测出这类差错”，不是绝对无错。

10.5 IP 地址、子网与最长前缀路由

IPv4 地址由 32 位组成。CIDR 前缀 192.168.10.77/26 中，前 26 位是网络前缀，余下 6 位是主机部分。掩码最后一字节为 11000000，也就是 192：

地址 77 的最后一字节：01001101
掩码 192：             11000000
按位与：               01000000 = 64

得到：

• 网络地址 192.168.10.64；
• 普通广播子网的广播地址 192.168.10.127；
• 常规可用主机地址 .65～.126，共 $2^6-2=62$ 个。

“减 2”需要对应常规广播子网场景，不能机械套到 /31、/32 等特殊用途。

路由器按最长前缀匹配查表。如果 192.168.10.0/24 与 192.168.10.64/26 都匹配目标 .77，则 /26 更具体，应优先选它。[R4]

一台主机访问远端网络时，当前以太网帧的目的 MAC 往往属于本地下一跳网关，而 IP 报文的目的地址仍指向最终远端主机（不考虑 NAT 等改写）。IP 地址、MAC 地址、端口各自描述不同层的定位语义。

10.6 MTU、TCP MSS 和 IPv4 分片不能混用

在下面这个明确的教学例子中：

原 IPv4 数据报总长度 2100 B（含 20 B 首部）
MTU = 1000 B；允许分片；没有 IP 选项

原载荷 $2100-20=2080$ B。每个非末尾分片理论可装 $1000-20=980$ B，但 IPv4 的分片偏移以 8 B 为单位，非末尾分片载荷需按 8 B 对齐，因此：

这正好说明：MTU 是包含 IP 首部的链路承载上限之一，不是每个 IP 分片可装载的数据字节数。TCP MSS 则描述 TCP 段数据部分上限，仍是另一个概念。[R4]

10.7 TCP：端到端顺序靠“字节序号和状态”维护

TCP 向应用提供可靠有序字节流，序号按字节计数，不按应用调用次数计数。累计 ACK 为 $X$，表示此前从已确认前缀开始到 $X-1$ 的字节都已收到并接受；不是“已收到的最大编号”。[R13]

例如：

段 1：SEQ=1001，数据 1000 B → 字节 1001～2000
段 2：SEQ=2001，数据 1000 B → 字节 2001～3000，丢失
段 3：SEQ=3001，数据 1000 B → 字节 3001～4000，已到并缓存

即使段 3 已到，累计 ACK 仍可能是 2001，因为中间有缺口。若随后缺失段到达，且后续连续字节都已缓冲，ACK 可以一次跃迁到 4001。

这与计算图的依赖是一种有用的类比：后面的数据已存在，不代表此前必须满足的连续前缀已经完成。

TCP 三次握手的序号也可以精确追踪。若客户端初始序号为 100、服务端为 8000，在不携带应用数据的简化握手中：客户端发送 SYN SEQ=100；服务端返回 SYN+ACK SEQ=8000 ACK=101；客户端回 ACK SEQ=101 ACK=8001。这里 SYN 本身占用一个序号，不能只把“握手成功”理解成三次随意对话。[R13]

10.8 滑动窗口与“序号绕回”中的歧义

停止等待每发送一帧就等 ACK，长传播距离下可能闲置大量带宽。滑动窗口允许多个未确认分组同时在途；窗口太小，链路无法持续填满。

考虑：

链路 10 Mb/s；每帧 1000 B
单程传播 10 ms；立即确认
ACK 发送时间、处理与排队时间忽略

每帧发送 $0.8$ ms。第一帧的 ACK 从“开始发”到返回需：

要不停顿地发送，窗口至少满足：

序号是有限的。若使用 $m$ 位序号，在经典模型中：

因此要支持 $W=26$：GBN 至少需 5 位，等窗口 SR 至少需 6 位。

SR 的窗口限制更严格，是因为序号绕回时，过大的接收窗口可能把旧帧的重传误认为新一轮同号帧。窗口约束是为了消除新旧数据的歧义，而非单纯节省内存。[R4][R7]

10.9 流量控制、拥塞控制与应用限流并不是一回事

• 流量控制：防止发送端超出接收方允许接受的范围（TCP 接收窗口 rwnd 等）；
• 拥塞控制：防止过量在途数据给网络带来拥塞（cwnd 等）；
• 应用限流/排队：服务端管理业务请求，防止超出应用和计算资源能力。

在简化的一致窗口基准下，TCP 允许的在途数据受 $\min(rwnd,cwnd)$ 约束，还能新发多少，需要扣除已发送未确认数据。窗口大小不是“现在可以再发这么多字节”。

网络能持续接受数据，也不等于 GPU 能持续完成同样数量的请求。数据到达速率和服务速率若长期失衡，就会积压。

10.10 DNS、TLS、HTTP 与 QUIC：一次成功请求包含多个保证

DNS 提供名字到记录的解析，不仅仅是“域名换 IP 的一次 UDP 查询”。HTTPS 可能使用 TCP+TLS，也可能使用 HTTP/3 over QUIC；TLS 负责所协商连接的机密性、完整性和身份相关机制，HTTP 规定应用的请求/响应语义。[R14]

一个非常重要的端到端区分：

TCP 确认字节已经接收
≠ 应用已经解析并完成请求
≠ 数据库操作已持久化
≠ 客户端已经看见完整回答

请求超时尤其如此：“没收到结果”不等于“服务端没执行”。如果操作有副作用，重试可能需要请求 ID、幂等键、去重状态或状态查询，不能简单重复提交。

10.11 流式生成：一个 Token 从算出到显示，还要经过几个缓冲区

普通 HTTP 响应可以等全部文本生成后一次返回。实时模型服务常采用流式响应：模型一旦产生可发送的内容，就尽早把增量结果传到客户端。在 Web 场景中，Server-Sent Events（SSE） 是常见选择，数据类型为 text/event-stream，事件以空行分隔：[R32]

响应头声明 Content-Type: text/event-stream。SSE 正文可以连续发送：

data: {"delta":"你"}

data: {"delta":"好"}

这是应用层事件流的正文，不是 HTTP 原始分块或 TCP 抓包；事件以空行作为分隔。HTTP/1.1 中，未知长度的流式消息可使用 Transfer-Encoding: chunked 来界定传输块；SSE 事件边界与 chunk 边界彼此独立。HTTP/2 使用自身的 DATA 帧，HTTP/3 使用 QUIC 流，不能把 Transfer-Encoding: chunked 当作所有 HTTP 流式响应的共同前提。[R32][R33]

从模型到页面上的一个新字符，至少可以依次追踪：

GPU/CPU 产生结果并确认可读
  → 采样与分词结果解码
  → 应用构造一条 SSE 事件
  → Web 框架与反向代理缓冲区
  → HTTP/TLS/传输层发送
  → 网络到达与客户端读取
  → SSE 解析并触发界面更新

这里每一段都有可能增加 ITL（Token 间可见延迟）。应用层写入成功不等于包已上网，更不等于浏览器已经渲染。

在 TCP 上反复写很短的增量数据时，Nagle 算法可能推迟新的小段发送，接收端延迟确认又可能放大这种等待；但该现象需要存在特定的未确认数据与 ACK 时序，不能仅凭一次 40 ms 卡顿就断定是 Nagle。TCP_NODELAY 可以作为针对性实验项，其效果仍需测量。[R34]

诊断时应按时间戳逐段定位：应用生成事件时间、调用写入时间、框架 flush 时间、内核发送时间、代理转发时间、客户端接收与渲染时间。如果应用尚未 flush，网络层根本无从及时发送；如果流量经过 HTTP/2 或 QUIC，窗口和缓冲机制又不同。第 14.3 节将这些事件纳入 TTFT / ITL 的测量定义。

这一层的连接：地址决定投递位置，序号决定字节流的位置，窗口限制允许在途的数据量，消息边界由 HTTP/SSE 等上层协议定义；最终用户看到结果的时间，还包括应用和客户端的处理。传输层完成和应用层完成始终需要分别判断。

第三部分：把跨学科联系变成可推导的工程问题

11. 贯穿案例：4096 维线性层从文件走到计算单元

前面逐层学习，现在反向把它们重新合并。选一个严格限定的案例：

假设权重最初存在磁盘上的一个文件里；一位用户通过网络请求服务器执行这个运算；服务器按请求选择 CPU 或 GPU 执行。本例用一个局部算子展示跨层协作，讨论范围限于这一层的执行。

一份权重的完整坐标履历

为了避免概念停留在抽象层，跟踪矩阵中的 $W_{1,2}$，假设零基下标、$W$ 连续行优先、没有额外 header，且原始权重全部以 FP32 保存。

• 数学：$W_{1,2}$ 参与 $y_1$ 的加权求和项 $W_{1,2}x_2$。
• 元素索引：$k=1\times4096+2=4098$。
• 文件/缓冲区字节偏移：$4k=16392$ B，即 0x4008，前提是该矩阵缓冲区从偏移 0 开始。
• 虚拟地址：若映射起始虚拟地址为 base，则目标地址是 base+0x4008；base 必须符合该缓冲区真实的映射与对齐条件。
• 页与 Cache：若矩阵缓冲区起始地址按 4 KiB 页面边界对齐，则 0x4008 落在相对第 4 页、页内偏移 8 的位置。若 base 不按页对齐，则必须先将它与偏移相加，再计算实际虚拟页号及页内偏移；只有进一步给出页表/Cache 条件，才能分析相应映射。
• 计算：CPU/GPU 读取到的应是符合 dtype 与字节序的数，再按算子约定完成乘加。

如果权重改成 INT4，数学坐标和元素编号保持不变，但载荷字节偏移改为 $\lfloor4098/2\rfloor=2049$ B，同时需要定位 scale 并确认打包顺序。改变编码时，应更新解码契约，并保持数学语义不变。

11.1 从文件字节到张量含义：解析不是计算

一个权重文件并不因为里面有 $4096^2$ 个数，就自动具有“矩阵乘法”的语义。调用方至少需要知道：

张量名、shape、dtype、编码方式、字节范围、数据布局
模型结构：这份权重在运算图中的位置

如果有 64 MiB 的 FP32 数据，你还需要检查其字节数是否与 shape、dtype 对应；若是量化权重，则应分别解读打包载荷与 scale 等元数据。文件读取器正确并不等于模型执行器正确。

11.2 内存所有权体现在计算接口中

先实现一个对连续行优先 FP32 数据工作的安全、朴素、同步计算：

// 教学示例：不是 StarLight 已公开的正式算子接口。
fn gemv_into(
    weights: &[f32],
    rows: usize,
    cols: usize,
    x: &[f32],
    out: &mut [f32],
) -> Result<(), &'static str> {
    let expected = rows.checked_mul(cols).ok_or("shape overflow")?;
    if weights.len() != expected || x.len() != cols || out.len() != rows {
        return Err("dimension mismatch");
    }

    for i in 0..rows {
        let row = &weights[i * cols..(i + 1) * cols];
        let mut acc = 0.0f32;
        for j in 0..cols {
            acc += row[j] * x[j];
        }
        out[i] = acc;
    }
    Ok(())
}

这个接口首先要做到契约清楚：

• 只接受连续行优先布局，不假装支持任意 stride；
• 对输入形状做了显式检查；
• 输出缓冲由调用者准备；
• 本函数没有主动创建一个新的 Vec 输出；
• 返回时 CPU 计算完成，没有异步设备生命周期问题；
• 数值精度为普通 f32 累加，不宣称与高精度参考逐位一致。

真正上 GPU 后，可能需要额外规定提交、完成与资源回收事件。用一个 Result 返回“提交成功”不能冒充“计算已完成”。

11.3 量化以后，算子接口不能保持原样而不加说明

若权重改为 INT4，weights: &[f32] 这个输入契约就不再代表文件的实际编码。你需要一个新的对象或描述符：

PackedData：载荷字节
QuantizationFormat：INT4 编码约定
Scales：每组缩放系数
GroupSize：每组元素个数
OriginalShape：逻辑矩阵形状
Layout：权重排布方式

如果盲目把打包字节“reinterpret”为浮点切片，不仅数学错误，还可能违反内存对齐、有效值与别名要求。

量化算子可能有两条执行路径：

预先反量化 → 高精度矩阵乘

或：

边读边解包/反量化 → 融合计算

两条路径有不同的时间与内存成本。后者看似“做了更多事”，却可能省掉巨大的中间张量写回与再次读取；是否更快，需要通过性能测量判断。

11.4 算法上的 O(1) 访问，也可能在硬件上昂贵

同样是读取 weights[k]：

• 地址计算可能是常数时间；
• 但真实访问可能命中 L1，也可能需要经过更远存储层级；
• 页面翻译可能命中 TLB，也可能需要页表访问；
• 在 GPU 上还可能受访存合并、对齐与数据排布影响。

所以，算法的渐近时间复杂度和硬件性能不是相互替代的指标。

从第一性原理出发，应先找出真实任务中关键且可控制的成本。

12. KV Cache：数组索引、分页映射与并发生命周期的交点

12.1 KV Cache 的内存规模推导

以常见 Transformer 的 KV 缓存组织为教学模型，设：

• $L$：层数；
• $B$：同时缓存的序列条数；
• $T$：每条序列有效缓存位置数（为便于计算先假设相同）；
• $H_{KV}$：每层 K/V 的 KV 头数；
• $d_h$：每头维度；
• $b$：每个 KV 元素字节数。

忽略块填充、页表及元数据，KV 数据体积：

前面的 2 分别对应 K 与 V。

例如：

L = 32 层，B = 1，T = 8192
H_KV = 8，d_h = 128，b = 2 字节

则：

这还不包括模型权重、计算中间区、碎片、页表、框架及通信占用。 并非所有注意力结构都符合这个简单公式；还要区分 MHA、GQA/MQA、滑动窗口等具体组织。

12.2 分页块把逻辑序列与物理存储解耦

假设每个块可容纳 16 个 token，用户序列在位置 35 时：

块表记录逻辑块 2 对应哪个实际块。这样可以把“逻辑连续的序列”与“实际分散的 KV 存储块”区分开来。PagedAttention 的设计确实明确借鉴虚拟内存与分页，并通过灵活管理共享/复用 KV 缓冲块改善服务端内存利用。[R18]

但KV 块不是 CPU 的真实物理页；对具体后端而言，KV 页表可能只是 GPU Kernel 会读取的普通数组或描述符。

12.3 最容易出现的三个错误

错误 1：把缓冲容量当成有效长度。 预分配 1024 个位置，但只写入 17 个，读取前 1024 个当历史上下文可能读到无效数据。

错误 2：页块被两个请求共享，却没有明确所有权与可写规则。 一个请求改写仍被另一请求读取的共享块，会破坏隔离；共享/写时复制需要被明确设计。

错误 3：算子返回就立刻复用块，而异步设备实际还在读取。 调用结束不等于设备完成。

这三个问题分别依赖：数据结构的索引不变量、操作系统式的资源归属与隔离、异步执行的时序约束。

12.4 前缀缓存不是“只要文字看着一样就能复用”

设缓存块能容纳 4 个 Token ID，两个请求为：

请求 A：[A, B, C, D] [E, F, G, H] [I, J, …]
请求 B：[A, B, C, D] [E, F, G, X] [Y, Z, …]

以只缓存完整块的简单块级策略为例，第 1 块完全一致，若此前缓存仍有效就能够命中；第 2 块在最后一位不同，不能把 A 的整块 KV 当成 B 的正确结果。这让匹配粒度和命中率直接联系起来。实际系统可能还有部分块处理、不同注意力布局与更复杂的匹配规则，必须按后端语义确定。[R30]

vLLM 公开设计将块的内容与前缀历史纳入哈希身份，在 KV Cache Manager 中追踪块引用计数和空闲列表；SGLang 的 Radix Cache 用压缩前缀树组织共享路径。重复提示词对应的字面文本相同尚不足以保证缓存可复用：需要比较分词后的 Token ID、模型配置，以及可能改变计算结果的上下文与适配器状态。[R30][R31]

共享带来新的不变量：可复用的历史块必须在使用期间保持正确的只读/共享语义；要写入不同分支时，不得改写仍被别的请求使用的共享结果。 缓存命中、物理块释放、引用归零、GPU 任务完成，都是不同事件。缓存测试应同时检查冷启动与热命中的数值一致性、请求隔离和显存回收，而不能只统计命中率。

这一节把**数据结构（Trie / 哈希 / 链表）、操作系统（所有权与生命周期）、线性代数（因果前缀结果）、性能（少算 Prefill）**放回同一个请求。前缀缓存不仅是速度优化，也是一套有正确性约束的状态复用协议。

13. Attention 同时受矩阵语义、浮点误差与 IO 成本约束

设序列长度为 $T$，单头维度为 $d$：

对全序列注意力，朴素中间分数矩阵：

当 $T$ 很大时，若把这个分数矩阵完整物化并写入较远的设备内存，就会产生显著存储和搬运成本。

数学上精确计算 Attention，并不要求一定把整个 $T\times T$ 中间矩阵写回 HBM。 FlashAttention 的关键思想之一是用分块与在线 softmax 组织读取和累计，减少 GPU 不同存储层级之间的数据移动；其“exact attention”指未采用近似稀疏筛除来改变注意力数学定义，但具体有限精度实现仍需讨论数值误差。[R16]

因此，真正重要的联系是：

1. 线性代数给出 Attention 的矩阵形状与公式；
2. 数值分析给出稳定 softmax 的实现原则；
3. 算法设计决定是否物化巨大中间对象；
4. 硬件体系结构决定 SRAM/HBM 的成本差距；
5. 缓存与并发管理决定请求上下文怎样被保存和复用。

这体现了“算法 × 系统”的协同设计，涉及数学、数值、存储与执行方式的共同优化。

14. 从局部算子到端到端性能的三个约束

14.1 Amdahl 定律：局部加速的上限

若总时间有比例 $p$ 可被加速 $s$ 倍，其他部分不变，则整体加速比：

假设某算子占总响应时间 10%，即使算子快 10 倍：

整体只快约 9.9%。因此优化前应先做剖析，不应把孤立 Kernel 的倍数宣传为端到端倍数。

14.2 Little 定律：吞吐、延迟、系统内任务数之间的关系

对满足统计稳定、边界一致等条件的系统：

这里 $N$ 是系统内平均任务数，$\lambda$ 是长期平均完成率，$T$ 是平均停留时间。例如每秒完成 100 个请求，平均停留 0.2 秒，则 $N=20$。

这不是调参建议“并发越大越好”。当服务能力已被用满，增加队列长度常常只是提高等待时间；Little 定律本身没有告诉我们怎样改变计算能力。

与网络带宽—时延积的形式相似：要让长 RTT 的链路持续有数据在途，需要一定的在途字节数量。但“在途窗口”和“服务队列”不应被视为同一个控制器。

14.3 推理性能指标要分开

• TTFT（Time to First Token）：请求发出或服务器接收后到第一个可见 token 的时间，必须明确起点；
• ITL/TPOT（Inter-Token Latency / Time Per Output Token）：后续 token 的间隔或平均生成时间，统计方法需明确；
• 吞吐：每秒完成多少请求或生成多少 token；
• 内存：权重、KV、工作区与运行时各占多少；
• 质量：量化、近似与调度是否改变目标模型行为。

服务端 TTFT 与 客户端首事件到达时间并非同一测量边界。在流式响应下，可以用时间戳记录：请求到达、开始 Prefill、首次结果就绪、事件被 flush、首个事件到达客户端及被渲染。后两项包含了第 10.11 节的网络与缓冲成本，因此一次 40 ms 的额外 ITL 可能根本不在 GPU Kernel 内。

还要区分“模型生成一个 token”“SSE 传出一个事件”“页面显示几个字符”：分词器生成的 Token ID 和人看见的字符不是一一对应，多个 token 也可能被合并成一次可见更新。

一次测试应同时给出硬件、模型、输入长度、输出长度、并发数、精度、采样设置、预热与计时范围，并说明 TTFT/ITL 是客户端还是服务器侧记录。否则同一个“100 token/s”几乎没有比较意义。

14.4 训练和推理对应不同的资源账本

推理主要做前向运算并维护生成状态；训练还需要反向传播、梯度、优化器状态以及参数更新。训练显存不能只用“参数量×位宽”估计；推理也不能只算权重而忽略 KV Cache。

可以用统一的资源核算方法，但必须根据实际算法加入不同项。

14.5 性能诊断采用时间分解与资源证据

数值正确的算子也可能在系统中表现为高延迟。性能分析首先分清测量边界。一次请求的总耗时在某种串行化教学模型中可以拆成：

真实服务的传输、计算和排队可能重叠，因此这些分项不能无条件相加；这里用它们定位发生延迟的阶段。对每个阶段记录起止事件，避免一个“总延迟”同时包含互相重叠的区间而重复计时。

Brendan Gregg 的 USE 方法按 利用率（Utilization）—饱和（Saturation）—错误（Errors） 检查资源；RED 方法按 请求速率—错误—耗时（Rate, Errors, Duration） 观察服务。[R26] 可以把二者结合：

P99 是延迟分布的第 99 百分位，不能由平均值直接推导。定位瓶颈时，先固定工作负载、精度、并发、输入输出长度和测量区间，再修改一个因素。改善了某个微基准并不构成端到端优化成功的证据。

一次完全可复核的性能假设推导

假设一条请求测得总计 100 ms，拆分为：排队 40 ms，准备 10 ms，GPU 计算 20 ms，返回与其他串行阶段 30 ms，且各部分不重叠。在这个假设下，即使 GPU 计算无限快，总耗时下界也是 80 ms，整体加速上限为 $100/80=1.25$。若 GPU 只加速 2 倍，新的总耗时为 90 ms，整体仅加速约 $1.111$ 倍。

相同结论也可用 Amdahl 定律推导。先有可归因的性能账本，优化收益才有可信的上限。

15. 端到端正确性：分层保证与最终业务结果

一条请求最终返回之前，可以经历：

（1）字节正确到达网络端点
（2）应用正确解析、校验并接受请求
（3）请求正确进入调度系统
（4）设备计算已经完成
（5）数值输出符合模型容差/质量要求
（6）客户端收到并正确解释结果

这些状态不能被任意合并。

例如：

• TCP ACK 不等于业务请求执行完成；
• 命令提交成功不等于 GPU Kernel 完成；
• 量化打包正确不等于模型准确率没下降；
• cargo check 通过不等于运行结果正确；
• 测到低平均延迟不等于尾延迟可接受；
• 一次成功不等于任意故障情形下都能重试而不重复执行副作用。

可以把验证拆为四类：

第一性原理之一就是责任边界：每一层只应该承诺自己真正能够验证的事情；更高层的正确性要在更高层验证。

15.1 将端到端参数拆成四份契约

给最小矩阵乘向量算子 gemv_into 写契约：

这四份契约连接抽象语义与实际代码。一个类型签名可以表达部分约束，例如只读/可变借用，却无法自动描述所有数学含义、设备完成与数值容差。接口文档与测试必须补齐类型系统未表达的条件。

15.2 超时与重试必须尊重业务语义

客户端超时只说明它在限定时间内未获得预期结果。服务端可能未收到请求、正在排队、已经完成但回复丢失，或已经执行了具有副作用的操作。若业务允许重试，应设计请求标识、幂等语义、去重或查询结果机制。TCP 能保证的传输顺序与字节确认，不会自动推导出应用层“恰好执行一次”。[R27]

这也是端到端原则的具体含义：某些目标只能由了解业务要求的端点最终验证，低层机制可以提供帮助，却不能承诺自己不了解的应用语义。

16. 回到 StarLight：模块化推理工程的学习与实现顺序

最初让我把这些知识连起来的契机，是阅读 SeekStarAI/StarLight 的架构设计。其规划是将模型格式、量化、图规划、设备接口、执行核心与服务调度拆成可替换的模块。

可以按职责理解其规划：

这里说的是模块职责与架构目标，不等于表中的全部功能都已经工程实现。理解项目时，要分别阅读 RFC、源代码与测试，避免把文档里的设计接口误当成已经存在的 API。

它提出的“机制/策略分离”有实际启发：同一个核心计算机制，可以由端侧应用或集群调度器以不同策略调用。但也要记住：模块化本身不证明零开销，不证明硬件无损可移植，也不证明吞吐更高。

对我而言，一条更可靠的参与路线是：

可手算的量化编码
   → Rust 安全切片与独立单元测试
   → 模型格式解析和数值校验
   → 小尺寸 CPU 参考算子
   → 静态计算图/内存规划器
   → 真实 KV Cache 与生命周期测试
   → CPU/GPU 后端与端到端推理

所有这些步骤，都可以逐个回答“正确性依据是什么、资源约束是什么、性能收益是否已测量”。这比一开始宣传“支持所有 GPU/NPU”更实在。

第四部分：重新组织考研四门课与数学知识

17. 第一性原理与考研大纲构成两套互补索引

第一性原理提供理解线索，考试大纲提供覆盖范围。前者不能替代后者。比如理解“缓存能降低重复成本”，不等于会算直接映射 Cache 的 Tag/Index/Offset；理解“信号量管理次序”，也不等于能写对复杂 PV；理解“路由是地址映射”，也不等于能做 IPv4 分片和 VLSM。

因此我会采用两张表：一张按学科考点防遗漏，另一张按跨学科桥梁防割裂。具体报考院校、考试年份与考试大纲应另行核对；下表是学习地图，不冒充当年官方逐条考纲。

17.1 按学科索引覆盖基础题型与知识边界

17.2 按“共同的根问题”重新连接

用这张表可以在复习时做两件事：做题前写清前提；学完一章后找到与其他学科最重要的连接，同时保持边界意识。

17.3 通过四个小题迁移不同学科的推导方法

KMP：利用已知前后缀，避免从头比较。

模式串 ABABAC，若采用“每个前缀的最长相等真前后缀长度”作为前缀函数定义，则有：

字符：A B A B A C
pi ：0 0 1 2 3 0

例如 ABABA 的最长相等真前后缀是 ABA，长度 3。失配时把已有匹配信息变成新的尝试位置；主串指针无需反复倒退，从而使经典 KMP 匹配与预处理总成本为 $O(n+m)$。注意教材里 next、nextval 和 pi 可能采用不同下标约定，不能直接混抄数列。[R6]

哈夫曼编码：有限信息如何用平均更短的前缀码表示。

设四个符号权重为 $5,7,10,15$。按权重最小的两棵树反复合并：

5+7=12；10+12=22；15+22=37

带权路径长度等于各次合并权重之和：

相应叶子码长可以是 $3,3,2,1$；以权重视为频数时，平均长度为 $71/37\approx1.919$ 比特/符号。前缀码保证一个码字不作为另一码字的前缀，便于无歧义解码；各码字的长度可以不同。这和固定宽度 INT4 是不同的编码目标。

文件多级索引：用页式组织降低磁盘定位成本。

假设文件系统块长 4 KiB、块号占 4 B，则一个完整索引块能容纳：

一级间接索引覆盖 $1024\times4096=4$ MiB 数据；二级间接索引理论覆盖 $1024^2\times4096=4$ GiB 数据。这里算的是被索引数据容量，未计索引块本身和其他文件大小限制。你会再次发现“逻辑文件偏移 → 多级索引 → 数据块”的映射思想，与页表类似但用途不同。

排序稳定性：复杂度相同，语义也未必相同。

原数据为 2甲、2乙、1，排序后若保持 2甲 在 2乙 之前，叫作稳定。普通堆排序和快速排序通常不稳定；归并排序可以用“相等时先取左侧元素”等规则保持稳定。稳定性描述相等关键字之间的原始相对次序，不描述运行时间是否有波动。比较排序的 $\Omega(n\log n)$ 下界，也不覆盖能利用有限关键字范围的线性排序算法。[R6]

18. 可复现实验：以手算参考和反例检查理解

要检验自己是否真的理解，不妨先不用大模型，不安装复杂 CUDA 环境。把问题缩到可手算、可断言、可故意制造反例的程度。

本教程附有 实验脚本 computer_systems_first_principles_labs.py，只依赖 Python 标准库。脚本不是完整推理器，也不是 GPU 或系统性能基准；它把本文最重要的数学值—字节编码—状态不变量—跨层边界变成可以断言的教学用例。

python computer_systems_first_principles_labs.py

运行内容包括七组相互独立的检查：

1. 数值编码：验证 -6.5 的 FP32 位模式 0xC0D00000，INT4 奇数分组的 D9 97 03 载荷及 scale。
2. 字节序与消息边界：验证小端内存中的 00 00 D0 C0，UTF-8 请求体的 43 字节长度，以及任意分片后重新组装应用消息。
3. 信息论：验证概率 (1/2,1/4,1/8,1/8) 的熵为 1.75 bit/符号，及一个对应的前缀码。
4. 线性代数与接口：运行行优先 GEMV 的手算用例，确认尺寸错误会触发拒绝，而非产生错误结果。
5. 结构与地址：将 lower_bound 与标准库比较；验证分页地址转换和 IPv4 的 976/976/128 字节分片。
6. TCP 与因果注意力：检查乱序 TCP 到达的累计 ACK 2001/2001/4001；比较全序列注意力与逐位置缓存注意力，并检验未来位置扰动不会影响历史输出。
7. 资源成本：复核 FP32 64 MiB、INT4+scale 8.5 MiB、KV Cache 1 GiB 和 Amdahl 的整体加速边界。

这些实验虽小，却刻意跨越了“数学定义 → 具体字节 → 状态结构 → 可检查的结果”这条路径。真正深入时，建议做两种测试：

正例：有合法输入时，结果符合明确的参考定义。

反例：故意删除因果遮罩、改错低/高 nibble 顺序、误读分页偏移等，测试确实会失败。

这叫做验证测试的辨错能力。两个实现互相比对并不绝对充分：如果它们共享同一个错误函数，可能一起得到相同的错误结果。最好组合手算值、独立参考、数学性质和边界测试。

18.1 如果用 C++ 或 Rust 练习，优先练四份契约

每做一个小算子，先写下：

四份契约尚未确定时，不适合贸然引入 SIMD、unsafe 或 CUDA 优化。

19. 十七道跨学科迁移练习与解析

正文已完整手算过一批基础例子。这里更换题目数值和部分边界条件，让复习从“复述正文”变成“独立重建推导”。前 15 题覆盖可计算知识；最后两题要求用跨层证据排障。建议先遮住答案，给每道题写出前提、计算、边界检查三行草稿。

题 1：同一位模式的两种数值含义

四位位串 1011 按 UINT4 和 INT4 补码分别是多少；其完整有符号编码范围是什么。

答：UINT4 为 11；补码 INT4 为 $11-16=-5$；完整范围 $[-8,7]$。即使某对称量化器只用 $[-7,7]$，也不改变这种数据类型的理论编码范围。

题 2：重新手算 IEEE FP32

将 $-13.25$ 转为 FP32 位模式。

答：$13.25=1101.01_2=1.10101_2\times2^3$。符号位为 1，存储指数 $3+127=130=10000010_2$，小数域为 1010100...，所以 32 位结果为 0xC1540000。位模式是数值写法；内存中字节顺序还取决于大小端。

题 3：改变数据后的跨组 INT4 打包

对 [-7,-2,7,-14,6] 使用对称 INT4，编码范围 $[-7,7]$，group size=3，偶数索引放低 nibble，求载荷。

答：两组 scale 是 1、2；量化整数 [-7,-2,7,-7,3]。第一字节低位 0x9、高位 0xE，得到 0xE9；第二字节为 0x97；最后为 0x03。载荷为 E9 97 03，另有两个 scale。

题 4：矩阵秩与零空间

求秩及一个非零 $Ax=0$ 的解。

答：第二行为第一行两倍，故秩为 1；$x=(-3,1)^\top$ 满足 $Ax=0$。非零零空间意味着不同输入能够得到同一个输出。

题 5：参数化正定二次型

求实数 $a$ 的正定区间。

答：对应实对称矩阵 $\begin{bmatrix}2&a&0\\a&3&0\\0&0&1\end{bmatrix}$，顺序主子式为 $2,6-a^2,6-a^2$，正定当且仅当 $-\sqrt6<a<\sqrt6$。

题 6：二分边界查找

在非递减数组 [-2,0,0,3,7] 中，求第一个 >=1 的下标及第一个 >=8 的下标。

答：分别为 3 和 5；下标 5 等于数组长度，表示不存在。左闭右开二分的后置条件要允许返回 $n$。

题 7：BST 祖先约束

根为 8，左孩子为 3，且 3 的右孩子为 9。这是否为合法的无重复键 BST。

答：不是。9 虽大于其父节点 3，却属于根 8 的左子树，违反祖先规定的“整棵左子树都小于 8”。

题 8：最短路对负边的敏感性

给定 $S\to A=3,S\to B=6,B\to A=-5$，求 $S$ 到 $A$ 的最短路径长度，并解释经典 Dijkstra 的限制。

答：经 $B$ 的路径长为 $6-5=1$，小于直接路径 3。非负边权条件被破坏，经典 Dijkstra 的永久标记步骤不再普遍正确。

题 9：Cache 的 tag/index/offset

48 位字节地址，64 KiB Cache、128 B 块、8 路组相联，求组数和三类位数。假设通常的按位索引模型，且地址宽度是题目要求拆分的宽度。

答：组数 $64\times1024/(128\times8)=64$，故 index 为 6 位，offset 为 7 位，tag 为 $48-6-7=35$ 位。