第 17 章：动态 Shape 编译（一）

大纲

17.1 开篇：动态 Shape 的挑战与机遇

动态 Shape 的定义与场景
编译时未知维度的处理
与静态 Shape 编译的本质区别
在自动驾驶和具身智能中的应用

17.2 符号形状推导

符号维度表示
符号算术系统
形状传播算法
约束求解器设计

17.3 Shape 函数与约束

Shape 函数的定义与作用
约束表达式语言
约束传播机制
冲突检测与解决

17.4 动态内存管理

运行时内存分配策略
内存池的动态扩展
碎片管理
峰值内存预测

17.5 桶化策略

桶化的基本原理
桶边界选择算法
多维桶化
性能与内存权衡

17.6 本章小结

17.7 练习题

17.8 常见陷阱与错误

17.9 最佳实践检查清单

17.1 动态 Shape 的挑战与机遇

动态 Shape 编译是现代 AI 编译器面临的核心挑战之一。不同于传统的静态 Shape 场景，动态 Shape 允许张量的某些维度在编译时未知，只有在运行时才能确定。这种灵活性在自动驾驶的变长序列处理、具身智能的多模态输入融合等场景中至关重要，但也给编译优化带来了巨大挑战。

动态 Shape 的典型场景

在自动驾驶系统中，激光雷达点云数据的点数会随环境复杂度变化，每帧可能包含 10,000 到 200,000 个点不等。类似地，目标检测后的 RoI (Region of Interest) 数量也是动态的。具身智能机器人需要处理不定长的自然语言指令，同时融合数量可变的传感器输入。这些场景都要求编译器能够高效处理动态 Shape。

编译时的核心问题

动态 Shape 给编译器带来三个核心问题：

内存规划的不确定性：无法在编译时确定准确的内存需求，静态内存规划算法失效
优化决策的困难：许多优化（如循环展开、向量化）依赖于具体的维度信息
调度的复杂性：无法预先确定最优的并行策略和任务分配

符号化处理方法

解决动态 Shape 的核心思想是引入符号维度（symbolic dimension）。我们用符号变量表示未知的维度，建立符号算术系统进行形状推导。例如，批次大小用符号 $N$ 表示，序列长度用 $L$ 表示，则自注意力机制的计算复杂度可表示为 $\mathcal{O}(N \cdot L^2 \cdot D)$，其中 $D$ 是特征维度。

编译策略概览

动态 Shape 编译采用分阶段策略：

编译时：符号分析 → 约束提取 → 模板生成 → 特化准备
运行时：形状具体化 → 快速特化 → 执行优化代码

这种方法在编译时完成尽可能多的分析和准备工作，运行时只需要快速填充具体数值并执行。

17.2 符号形状推导

符号形状推导是动态 Shape 编译的理论基础，它将编译时的形状分析从具体数值域扩展到符号域，使得编译器能够在维度未知的情况下进行正确性验证和优化决策。

17.2.1 符号维度表示

符号维度系统的核心是用代数表达式表示张量的每个维度。我们定义符号维度 $d$ 为：

$$d ::= n \mid s \mid d_1 + d_2 \mid d_1 \cdot d_2 \mid \lfloor d_1 / d_2 \rfloor \mid \max(d_1, d_2) \mid \min(d_1, d_2)$$ 其中 $n \in \mathbb{N}$ 是具体数值，$s$ 是符号变量。每个符号变量可以附加约束，如 $s \in [l, u]$ 表示 $s$ 的取值范围。

17.2.2 符号算术系统

符号算术系统需要支持基本运算的符号化：

加法规则：

$(a + b) + c = a + (b + c)$ （结合律）
$a + 0 = a$ （单位元）
$n_1 + n_2 = n_3$ 其中 $n_3$ 是具体数值的和

乘法规则：

$(a \cdot b) \cdot c = a \cdot (b \cdot c)$ （结合律）
$a \cdot 1 = a$ （单位元）
$a \cdot (b + c) = a \cdot b + a \cdot c$ （分配律）

除法规则（整数除法）：

$\lfloor a / 1 \rfloor = a$
$\lfloor n_1 / n_2 \rfloor = n_3$ 其中 $n_3 = \lfloor n_1 / n_2 \rfloor$
当 $a < b$ 且都为正时，$\lfloor a / b \rfloor = 0$

17.2.3 形状传播算法

形状传播算法通过数据流图传播符号形状信息。对于每个算子 $op$，我们定义形状传播函数 $f_{op}: Shape_{in} \rightarrow Shape_{out}$。

矩阵乘法的形状传播：

给定输入形状 $A: [M, K]$ 和 $B: [K, N]$，输出形状为 $C: [M, N]$。当维度是符号时，需要添加约束 $K_A = K_B$。

卷积的形状传播：

对于 2D 卷积，输入 $X: [N, C_{in}, H_{in}, W_{in}]$，卷积核 $K: [C_{out}, C_{in}, K_h, K_w]$，输出形状为： $$Y: [N, C_{out}, H_{out}, W_{out}]$$ 其中： $$H_{out} = \lfloor \frac{H_{in} + 2p_h - K_h}{s_h} \rfloor + 1$$ $$W_{out} = \lfloor \frac{W_{in} + 2p_w - K_w}{s_w} \rfloor + 1$$ $p_h, p_w$ 是 padding，$s_h, s_w$ 是 stride。

17.2.4 符号简化与规范化

符号表达式需要简化以提高效率和可读性。简化规则包括：

常量折叠：$2 + 3 \rightarrow 5$
代数简化：$a + a \rightarrow 2a$，$a - a \rightarrow 0$
约束传播：如果 $a \in [1, 10]$ 且 $b \in [5, 15]$，则 $a + b \in [6, 25]$
符号消除：$\lfloor a \cdot b / a \rfloor \rightarrow b$ （当 $a > 0$）

17.2.5 约束求解器设计

约束求解器负责验证符号约束的可满足性。我们使用 SMT (Satisfiability Modulo Theories) 求解器处理整数线性约束。

约束类型：

相等约束：$d_1 = d_2$
不等约束：$d_1 \leq d_2$, $d_1 < d_2$
整除约束：$d_1 \mod d_2 = 0$
范围约束：$l \leq d \leq u$

约束求解算法：

输入：约束集合 C = {c_1, c_2, ..., c_n}
输出：可满足性判定及符号变量赋值

1. 将约束转换为标准形式
2. 构建约束图，节点为符号变量，边为约束关系
3. 使用 Bellman-Ford 算法检测负环（不可满足）
4. 若可满足，使用线性规划求解可行域
5. 返回可行解或报告冲突

17.3 Shape 函数与约束

Shape 函数是动态 Shape 编译中的关键抽象，它显式地描述了算子的输入输出形状关系，并生成相应的约束条件。这种机制使得编译器能够在符号层面验证程序的正确性，并为后续优化提供依据。

17.3.1 Shape 函数的定义

Shape 函数 $\mathcal{S}$ 是一个从输入形状到输出形状的映射，同时生成约束集合： $$\mathcal{S}: \text{Shape}^n \rightarrow \text{Shape}^m \times \text{Constraints}$$ 其中 $n$ 是输入张量数量，$m$ 是输出张量数量。每个 Shape 函数都必须满足：

确定性：相同输入产生相同输出
单调性：输入维度增大时，输出维度不减小
可组合性：多个 Shape 函数可以串联

17.3.2 Shape 函数的表示语言

我们定义一个专门的 DSL (Domain Specific Language) 来表示 Shape 函数：

shape_func ::= λ(inputs) → (outputs, constraints)
inputs ::= tensor_shape*
tensor_shape ::= [dim_expr*]
dim_expr ::= symbol | constant | binary_op(dim_expr, dim_expr)
constraints ::= constraint*
constraint ::= dim_expr rel_op dim_expr
rel_op ::= = | ≤ | < | ≥ | > | ≡ (mod n)

17.3.3 常见算子的 Shape 函数

广播机制的 Shape 函数：

广播是动态 Shape 中最复杂的操作之一。给定两个张量 $A$ 和 $B$，广播后的形状计算如下：

broadcast_shape(A: [d₁, d₂, ..., dₙ], B: [e₁, e₂, ..., eₘ]) → C, constraints
其中：
  rank_C = max(n, m)
  对于 i = 1 to rank_C:
    if dᵢ exists and eᵢ exists:
      if dᵢ = eᵢ: Cᵢ = dᵢ
      elif dᵢ = 1: Cᵢ = eᵢ
      elif eᵢ = 1: Cᵢ = dᵢ
      else: 添加约束 dᵢ = eᵢ 或 dᵢ = 1 或 eᵢ = 1
    elif only dᵢ exists: Cᵢ = dᵢ
    elif only eᵢ exists: Cᵢ = eᵢ

Reshape 的 Shape 函数：

Reshape 操作需要保持元素总数不变：

reshape(X: [d₁, d₂, ..., dₙ], target: [e₁, e₂, ..., eₘ]) → Y: target, constraints
约束：∏dᵢ = ∏eⱼ
特殊情况：当 target 中存在 -1 时，该维度计算为 ∏dᵢ / ∏(eⱼ where eⱼ ≠ -1)

动态 Slice 的 Shape 函数：

slice(X: [d₁, ..., dₙ], start: [s₁, ..., sₙ], end: [e₁, ..., eₙ]) → Y, constraints
Y: [min(e₁-s₁, d₁-s₁), ..., min(eₙ-sₙ, dₙ-sₙ)]
约束：∀i: 0 ≤ sᵢ < dᵢ, sᵢ ≤ eᵢ ≤ dᵢ

17.3.4 约束表达式语言

约束表达式需要支持复杂的逻辑关系：

基本约束类型：

线性约束：$a₁x₁ + a₂x₂ + ... + aₙxₙ ≤ b$
乘积约束：$x₁ \cdot x₂ = c$
整除约束：$x \mod n = 0$
条件约束：$\text{if } p \text{ then } q \text{ else } r$

约束的逻辑组合：

合取：$c₁ \land c₂$ （两个约束都必须满足）
析取：$c₁ \lor c₂$ （至少一个约束满足）
蕴含：$c₁ \Rightarrow c₂$ （如果 $c₁$ 满足则 $c₂$ 必须满足）

17.3.5 约束传播机制

约束传播通过数据流图将局部约束扩展为全局约束：

前向传播算法：

1. 初始化：将输入张量的约束加入约束集 C
2. 对于拓扑排序的每个节点 n:
   a. 获取 n 的输入形状（可能包含符号）
   b. 应用 n 的 Shape 函数，生成输出形状和新约束
   c. 将新约束加入 C
   d. 简化 C 中的约束

3. 返回最终约束集 C

反向传播算法（用于推断输入约束）：

1. 从输出开始，已知输出形状约束
2. 对于反向拓扑排序的每个节点 n:
   a. 根据输出约束和 Shape 函数，推断输入约束
   b. 传播约束到前驱节点

3. 验证推断的输入约束与实际输入约束的兼容性

17.3.6 冲突检测与解决

约束冲突是动态 Shape 编译中的常见问题：

冲突类型：

直接冲突：$x = 5 \land x = 10$
传递冲突：$x < y \land y < z \land z < x$
域冲突：$x \in [1, 5] \land x > 10$

冲突检测算法：

1. 构建约束依赖图
2. 检测负环（使用 Bellman-Ford）
3. 使用 SMT 求解器验证可满足性
4. 如果不可满足，提取最小不可满足核心（MUC）

冲突解决策略：

放松约束：将硬约束转为软约束，允许一定误差
插入转换：自动插入 reshape、pad 等操作消除冲突
分支特化：为不同约束条件生成不同代码路径
运行时检查：将约束检查延迟到运行时

17.4 动态内存管理

动态 Shape 带来的最大挑战之一是内存管理的不确定性。传统的静态内存规划在这里不再适用，需要设计新的动态内存管理机制，既要保证正确性，又要优化性能。

17.4.1 运行时内存分配策略

动态内存分配需要在效率和灵活性之间权衡：

分配策略分类：

即时分配（Eager Allocation）： - 每个张量在创建时立即分配内存 - 优点：简单直接，易于调试 - 缺点：内存峰值高，可能导致 OOM
延迟分配（Lazy Allocation）： - 推迟到首次使用时才分配 - 优点：减少不必要的分配 - 缺点：增加运行时开销
预分配池（Pre-allocated Pool）： - 预先分配大块内存池 - 优点：避免频繁的系统调用 - 缺点：可能浪费内存

自适应分配算法：

输入：张量请求 T，历史统计 H
输出：内存块 M

1. 估算大小范围：
   size_min = eval_min(T.shape_constraints)
   size_max = eval_max(T.shape_constraints)

2. 查询历史模式：
   pattern = H.find_pattern(T.op_type, T.shape_pattern)
   size_likely = pattern.percentile(95)

3. 选择分配策略：
   if size_max - size_min < threshold:
     M = allocate_fixed(size_max)  // 差异小，直接分配最大
   elif pattern.variance < threshold:
     M = allocate_fixed(size_likely)  // 历史稳定，按经验分配
   else:
     M = allocate_growable(size_min, size_max)  // 可增长分配

4. 更新统计：H.update(T, actual_size)

17.4.2 内存池的动态扩展

内存池需要支持动态扩展以适应变化的需求：

分层内存池设计：

┌─────────────────────────────────────┐
│         L0: 小对象池 (<1KB)          │ ← 高频分配
├─────────────────────────────────────┤
│         L1: 中对象池 (1KB-1MB)       │ ← 常规张量
├─────────────────────────────────────┤
│         L2: 大对象池 (1MB-100MB)     │ ← 大型激活
├─────────────────────────────────────┤
│         L3: 巨对象池 (>100MB)        │ ← 模型参数
└─────────────────────────────────────┘

动态扩展策略：

指数增长：每次扩展为当前大小的 2 倍
线性增长：每次增加固定大小
自适应增长：根据使用率和预测需求调整

内存池扩展算法：

扩展决策：
growth_factor = 1.0 + min(0.5, allocation_rate / deallocation_rate)
new_size = current_size * growth_factor

扩展时机：

- 可用内存 < 总量的 20%
- 连续分配失败次数 > 阈值
- 预测未来 N 步需求超过当前容量

17.4.3 碎片管理

动态分配容易产生内存碎片，需要专门的管理策略：

碎片类型：

内部碎片：分配的内存大于实际需求
外部碎片：空闲内存被分割成小块

碎片度量： $$\text{碎片率} = \frac{\text{总空闲内存} - \text{最大连续空闲块}}{\text{总空闲内存}}$$ 反碎片化策略：

伙伴系统（Buddy System）： - 将内存分成 2^n 大小的块 - 合并相邻的空闲块 - 碎片率控制在 50% 以内
内存压缩（Memory Compaction）： - 定期移动活跃内存块 - 创建大的连续空闲区域 - 需要更新所有引用
分离适配（Segregated Fit）： - 不同大小类别使用不同的空闲列表 - 减少大小不匹配导致的碎片

17.4.4 峰值内存预测

准确预测峰值内存对于避免 OOM 至关重要：

静态分析方法：

基于符号形状的最坏情况分析： $$M_{peak} = \max_{t \in [0, T]} \sum_{v \in \text{live}(t)} \text{size}_{max}(v)$$ 其中 $\text{live}(t)$ 是时刻 $t$ 的活跃张量集合，$\text{size}_{max}(v)$ 是张量 $v$ 的最大可能大小。

动态预测方法：

使用历史数据和机器学习模型：

特征提取：

- 输入形状的统计特征（均值、方差、最大值）
- 算子类型和参数
- 历史执行的内存使用模式

预测模型：
peak_memory = α * input_size + β * model_complexity + γ * history_pattern + ε

其中系数通过在线学习持续更新

17.4.5 内存共享与别名

动态 Shape 下的内存共享需要更谨慎的分析：

共享条件：

生命周期不重叠
内存布局兼容
大小约束可满足

动态别名分析：

can_alias(T1, T2):
  // 检查生命周期
  if overlaps(T1.lifetime, T2.lifetime):
    return false

  // 检查大小兼容性
  if T1.size_max > T2.allocated_size:
    return false

  // 检查 stride 兼容性
  if not compatible_stride(T1.stride_pattern, T2.stride):
    return false

  return true

17.4.6 异常处理机制

动态内存管理需要健壮的异常处理：

OOM 预防策略：

早期检测：在分配前检查可用内存
渐进式回收：逐步释放缓存和临时数据
优雅降级：切换到更节省内存的算法

恢复机制：

处理 OOM：

1. 触发垃圾回收
2. 压缩内存池
3. 卸载非关键数据到磁盘
4. 如果仍然失败，触发重新编译（使用更保守的内存策略）

17.5 桶化策略

桶化（Bucketing）是处理动态 Shape 的实用技术，通过将连续的形状空间离散化为有限的桶，在编译时生成多个特化版本，运行时选择最合适的版本执行。这种方法在保持性能的同时，避免了完全动态带来的开销。

17.5.1 桶化的基本原理

桶化的核心思想是将无限的形状空间 $\mathcal{S}$ 划分为有限个互不相交的子空间（桶）： $$\mathcal{S} = \bigcup_{i=1}^{n} B_i, \quad B_i \cap B_j = \emptyset \text{ for } i \neq j$$ 每个桶 $B_i$ 对应一个编译后的特化版本，运行时根据实际形状选择对应的桶。

桶的表示：

每个桶用一个多维区间表示： $$B = \{[l_1, u_1] \times [l_2, u_2] \times ... \times [l_d, u_d]\}$$ 其中 $[l_i, u_i]$ 是第 $i$ 维的范围。

17.5.2 桶边界选择算法

桶边界的选择直接影响性能和资源消耗：

等间隔划分：

简单地将每个维度等分：

对于维度 d ∈ [min_d, max_d]：
  桶边界 = {min_d + i * (max_d - min_d) / n | i = 0, 1, ..., n}

基于分布的划分：

根据历史数据的分布选择边界：

1. 收集历史形状数据 H = {s_1, s_2, ..., s_m}
2. 对每个维度 d：
   a. 构建累积分布函数 CDF_d
   b. 选择分位点作为边界：
      boundaries_d = {CDF_d^(-1)(i/n) | i = 0, 1, ..., n}

自适应划分算法：

使用聚类算法自动发现最优边界：

输入：历史形状集合 H，目标桶数 K
输出：桶边界集合 B

1. 初始化：使用 K-means++ 选择 K 个初始中心
2. 迭代优化：
   repeat:
     a. 分配：将每个形状分配到最近的桶
     b. 更新：重新计算每个桶的边界
     c. 评估：计算总体代价函数
   until 收敛或达到最大迭代次数

3. 后处理：合并过小的桶，分裂过大的桶

代价函数设计： $$\text{Cost} = \alpha \cdot \text{CompilationOverhead} + \beta \cdot \text{RuntimeOverhead} + \gamma \cdot \text{MemoryUsage}$$ 其中：

CompilationOverhead = 桶数量 × 单个版本编译时间
RuntimeOverhead = 平均填充率 × 执行时间
MemoryUsage = 桶数量 × 平均代码大小

17.5.3 多维桶化

处理多个动态维度时，需要考虑维度间的相关性：

独立桶化：

每个维度独立划分，总桶数为各维度桶数的乘积：

总桶数 = ∏(每个维度的桶数)

优点：简单直接缺点：桶数量呈指数增长

联合桶化：

考虑维度间的相关性，减少总桶数：

1. 构建维度相关性矩阵：
   Corr[i,j] = correlation(dim_i, dim_j)

2. 识别强相关维度组：
   使用谱聚类将维度分组

3. 对每组联合桶化：
   组内维度一起考虑，组间独立

稀疏桶化：

只为常见的形状组合创建桶：

1. 统计形状组合频率
2. 选择累积频率达到阈值（如 95%）的组合
3. 为这些组合创建桶
4. 其余使用通用的动态版本

17.5.4 性能与内存权衡

桶化需要在多个目标间权衡：

性能模型： $$T_{total} = T_{dispatch} + T_{execution} + T_{padding}$$ 其中：

$T_{dispatch}$：选择桶的开销
$T_{execution}$：特化代码执行时间
$T_{padding}$：由于桶化导致的填充开销

内存模型： $$M_{total} = M_{code} \times N_{buckets} + M_{runtime}$$ 优化目标： $$\min_{B} \lambda_1 T_{total}(B) + \lambda_2 M_{total}(B)$$

受约束于：

$N_{buckets} \leq N_{max}$（桶数量上限）
$\text{Coverage}(B) \geq \theta$（覆盖率要求）

17.5.5 运行时桶选择

高效的运行时桶选择对性能至关重要：

决策树方法：

构建决策树快速选择桶：

       shape[0] < 128?
          /        \
        Yes         No
        /            \
   shape[1] < 64?   shape[1] < 256?
      /    \           /      \
   Bucket1 Bucket2  Bucket3  Bucket4

哈希表方法：

将形状映射到桶索引：

bucket_index = hash(quantize(shape)) % num_buckets

最近邻方法：

选择距离最近的桶中心：

min_distance = infinity
selected_bucket = null
for each bucket in buckets:
  distance = compute_distance(shape, bucket.center)
  if distance < min_distance:
    min_distance = distance
    selected_bucket = bucket

17.5.6 桶化的自动调优

使用机器学习自动优化桶化策略：

在线学习框架：

1. 初始化：使用默认桶化策略
2. 执行监控：
   - 记录每次执行的形状和性能
   - 统计桶的命中率和效率
3. 定期优化：
   - 识别性能瓶颈桶
   - 调整桶边界或增加新桶
4. 增量更新：
   - 只重新编译受影响的桶
   - 平滑切换到新策略

反馈驱动优化：

性能反馈循环：

1. 收集运行时统计：
   - 每个桶的使用频率
   - 填充开销
   - 实际执行时间

2. 分析优化机会：
   - 识别热点桶（需要细分）
   - 识别冷桶（可以合并）
   - 发现新的形状模式

3. 调整策略：
   - 重新分配编译资源
   - 更新桶边界
   - 调整特化策略

17.6 本章小结

本章深入探讨了动态 Shape 编译的核心技术，这是现代 AI 编译器必须解决的关键挑战。我们从符号形状推导开始，建立了处理未知维度的理论基础，然后通过 Shape 函数和约束系统实现了编译时的正确性验证。动态内存管理部分解决了运行时的资源分配问题，而桶化策略提供了实用的性能优化方案。

关键要点：

符号化是基础：通过符号维度和符号算术，将静态分析扩展到动态场景
约束是保障：Shape 函数和约束系统确保程序的正确性
内存管理需要自适应：动态场景下需要更智能的内存分配和管理策略
桶化平衡灵活性与性能：通过有限的特化版本覆盖无限的形状空间
运行时与编译时协同：将工作合理分配到编译时和运行时

核心公式回顾：

符号维度定义：$d ::= n \mid s \mid d_1 + d_2 \mid d_1 \cdot d_2 \mid \lfloor d_1 / d_2 \rfloor$
Shape 函数：$\mathcal{S}: \text{Shape}^n \rightarrow \text{Shape}^m \times \text{Constraints}$
峰值内存预测：$M_{peak} = \max_{t \in [0, T]} \sum_{v \in \text{live}(t)} \text{size}_{max}(v)$
桶化空间划分：$\mathcal{S} = \bigcup_{i=1}^{n} B_i, \quad B_i \cap B_j = \emptyset$
优化目标：$\min_{B} \lambda_1 T_{total}(B) + \lambda_2 M_{total}(B)$

17.7 练习题

基础题

练习 17.1 符号维度计算

给定两个张量 A: [N, 128, K] 和 B: [K, M, 256]，其中 N, K, M 是符号维度。计算以下操作的输出形状：

C = matmul(A, B)（对最后两维做矩阵乘法）
D = reshape(A, [N*128, K])
E = broadcast(A, B)（如果可能）

Hint: 考虑矩阵乘法的维度匹配要求和广播规则。

答案

C = matmul(A, B): - A 的形状调整为 [N, 128, K] - B 的形状为 [K, M, 256] - 批量矩阵乘法要求批次维度相同或可广播 - 这里需要广播，结果形状为 [N, K, max(128, M), 256] - 添加约束：最后一维的 K 必须相等
D = reshape(A, [N128, K]): - 直接重塑，输出形状为 [N128, K] - 约束：总元素数保持不变 N128K = N128K ✓
E = broadcast(A, B): - A: [N, 128, K] - B: [K, M, 256] - 无法直接广播，因为 A 的最后维度 K 与 B 的第一维度 K 位置不匹配 - 需要先进行维度对齐或转置

练习 17.2 约束求解

给定以下约束系统，判断是否可满足：

s1 + s2 = 100
s1 > 2 * s2
s2 ≥ 20
s1, s2 ∈ ℕ

Hint: 将不等式约束转换为等式形式，使用替换法求解。

答案

从约束系统：

s1 + s2 = 100
s1 > 2 * s2
s2 ≥ 20

从约束 1：s1 = 100 - s2 代入约束 2：100 - s2 > 2 * s2 100 > 3 * s2 s2 < 33.33

结合约束 3：20 ≤ s2 < 33.33

因此 s2 ∈ {20, 21, ..., 33} 对应 s1 ∈ {80, 79, ..., 67}

验证：当 s2 = 20, s1 = 80 时：

s1 + s2 = 100 ✓
80 > 40 ✓
20 ≥ 20 ✓

系统可满足。

练习 17.3 内存峰值计算

某模型有三个张量，生命周期如下：

T1: [N, 1024]，生命周期 [0, 5]
T2: [N, 2048]，生命周期 [3, 8]
T3: [N, 512]，生命周期 [6, 10]

假设 N ∈ [32, 128]，float32 类型，计算最坏情况下的峰值内存（MB）。

Hint: 找出所有张量同时活跃的时间点。

答案

分析各时间点的活跃张量：

t ∈ [0, 3): 只有 T1
t ∈ [3, 5]: T1 和 T2
t ∈ [5, 6): 只有 T2
t ∈ [6, 8]: T2 和 T3
t ∈ [8, 10]: 只有 T3

峰值出现在：

[3, 5]: T1 + T2 = N × (1024 + 2048) = N × 3072
[6, 8]: T2 + T3 = N × (2048 + 512) = N × 2560

最大值为 N × 3072，当 N = 128 时：峰值 = 128 × 3072 × 4 bytes = 1,572,864 bytes ≈ 1.5 MB

练习 17.4 桶化划分

给定序列长度的历史分布：

50% 的样本长度在 [64, 128]
30% 的样本长度在 [128, 256]
15% 的样本长度在 [256, 512]
5% 的样本长度在 [512, 1024]

设计一个 4 桶划分方案，使 95% 的样本能被覆盖。

Hint: 考虑使用不等间隔划分以优化常见情况。

答案

基于分布的 4 桶划分：

桶 1: [64, 96] - 覆盖短序列的前半部分（约 25%）桶 2: [96, 160] - 覆盖短序列后半和中等序列前半（约 40%）桶 3: [160, 384] - 覆盖中等序列后半和较长序列（约 25%）桶 4: [384, 768] - 覆盖长序列的大部分（约 5%）

这样可以覆盖 95% 的样本，同时对高频区间（64-256）提供更细粒度的划分。

超过 768 的样本（< 5%）使用通用动态版本处理。

挑战题

练习 17.5 符号简化系统设计

设计一个符号表达式简化系统，能够处理以下情况：

(N + M) × K - N × K → M × K
max(N, N + K) → N + K (当 K ≥ 0)
⌊(N × M) / N⌋ → M (当 N > 0)

描述你的简化规则和实现策略。

Hint: 考虑构建一个规则匹配和重写系统。

答案

符号简化系统设计：

规则表示：

Rule ::= Pattern → Replacement | Condition

核心规则集： - 分配律：(a + b) × c → a×c + b×c - 结合律：(a × b) × c → a × (b × c) - 消去律：a × b / a → b (when a ≠ 0) - 吸收律：max(a, a + b) → a + b (when b ≥ 0)
实现策略： - 构建表达式的 AST - 自底向上应用规则 - 使用规范形式避免循环 - 维护约束上下文
优化顺序： - 先展开（应用分配律） - 再合并（识别公因子） - 最后简化（消去和吸收）
约束传播： - 跟踪变量的范围约束 - 在简化时利用约束信息 - 生成新的约束

练习 17.6 自适应内存池设计

设计一个自适应内存池系统，要求：

支持不同大小类别的分层管理
能够根据使用模式自动调整池大小
最小化碎片率（目标 < 20%）

给出关键数据结构和算法。

Hint: 结合 slab allocator 和 buddy system 的思想。

答案

自适应内存池设计：

数据结构：

MemoryPool {
  layers: [SmallPool, MediumPool, LargePool]
  statistics: UsageStats
  predictor: SizePredictor
}

Layer {
  size_class: (min, max)
  free_lists: [FreeList]
  allocation_count: int
  fragmentation: float
}

分配算法：

1. 根据请求大小选择层
2. 在层内使用 best-fit 查找
3. 如果失败，触发扩展或压缩
4. 更新统计信息

自适应调整：

每 N 次分配后：

1. 计算各层的使用率和碎片率
2. 如果碎片率 > 20%：
   - 触发压缩
   - 调整大小类别边界
3. 根据历史预测未来需求
4. 预分配或释放内存

反碎片策略： - 延迟合并：批量处理释放操作 - 伙伴合并：相邻空闲块自动合并 - 迁移压缩：移动小对象创建大空闲块

练习 17.7 多维桶化优化

给定一个 Transformer 模型，batch_size ∈ [1, 128]，sequence_length ∈ [1, 2048]。设计一个桶化方案，要求：

总桶数不超过 16
覆盖 90% 以上的常见组合
最小化平均填充开销

Hint: 考虑 batch_size 和 sequence_length 的使用模式差异。

答案

多维桶化方案：

分析维度特性： - batch_size：通常是 2 的幂（1, 2, 4, 8, 16, 32, 64, 128） - sequence_length：集中在特定值（128, 256, 512, 1024, 2048）
相关性分析： - 小 batch 往往配大 sequence（推理） - 大 batch 往往配小 sequence（训练）
16 桶方案：

推理桶（6个）：
[1-2, 128-256], [1-2, 256-512], [1-2, 512-1024],
[1-2, 1024-2048], [4, 128-512], [4, 512-2048]

训练桶（8个）：
[8, 128-256], [8, 256-512], [16, 128-256], [16, 256-512],
[32, 128-256], [32, 256-512], [64, 128-256], [128, 128-256]

通用桶（2个）：
[2-8, 256-1024], [8-128, 512-2048]

填充开销优化： - 对 batch_size 使用向上取整到 2 的幂 - 对 sequence_length 使用向上取整到 64 的倍数 - 平均填充开销 < 15%

练习 17.8 约束冲突诊断

设计一个算法，当约束系统不可满足时，找出最小冲突集（Minimal Unsatisfiable Core）。

Hint: 使用二分搜索或增量方法。

答案

最小冲突集查找算法：

删除法（Deletion-based）：

输入：不可满足约束集 C
输出：最小冲突集 MUC

1. MUC = C
2. 对每个约束 c in C:
   temp = MUC - {c}
   if is_unsatisfiable(temp):
      MUC = temp

3. 返回 MUC

增长法（Growth-based）：

1. 二分搜索找到临界大小 k
2. 枚举所有大小为 k 的子集
3. 返回第一个不可满足的子集

优化策略： - 使用增量 SMT 求解器 - 缓存中间结果 - 启发式排序（优先检查相关约束）
诊断信息生成：

对于 MUC 中的每个约束：

1. 标注来源（哪个算子产生）
2. 分析冲突类型
3. 提供修复建议

示例输出： "约束冲突：矩阵乘法要求 K_A = K_B，但 reshape 操作导致 K_A = 2N 而 K_B = N+10"

17.8 常见陷阱与错误

1. 符号维度的过度泛化

陷阱：将所有维度都设为符号变量，导致优化机会丧失。

正确做法：

识别真正动态的维度（如 batch_size, sequence_length）
保持模型结构相关的维度为常量（如 hidden_size, num_heads）
使用部分特化技术

2. 约束求解的性能问题

陷阱：在关键路径上进行复杂的约束求解，导致编译时间爆炸。

正确做法：

缓存求解结果
使用增量求解技术
设置求解超时，失败时回退到保守策略

3. 内存分配的碎片累积

陷阱：频繁的动态分配释放导致严重的内存碎片。

正确做法：

使用内存池而非直接 malloc/free
定期进行碎片整理
实现内存重用机制

4. 桶边界选择不当

陷阱：等间隔划分桶，导致热点区域精度不足。

正确做法：

基于实际分布选择边界
使用自适应调整机制
为常见 case 提供专门优化

5. 符号简化的无限循环

陷阱：简化规则相互触发，导致无限循环。

正确做法：

定义规范形式
确保每次简化都向规范形式靠近
设置最大迭代次数

6. 动态 Shape 信息丢失

陷阱：在 IR 转换过程中丢失符号信息和约束。

正确做法：

在每个 IR 层保留 shape 标注
传播约束信息
验证转换的正确性

7. 运行时开销被忽视

陷阱：过于复杂的运行时决策逻辑，抵消了优化收益。

正确做法：

简化运行时检查
使用快速路径
预计算决策表

17.9 最佳实践检查清单

设计阶段

[ ] 明确区分静态和动态维度
[ ] 定义清晰的符号命名规范
[ ] 设计分层的 Shape 抽象
[ ] 规划约束的生命周期管理
[ ] 考虑与现有静态优化的兼容性

实现阶段

[ ] 实现高效的符号算术库
[ ] 构建可扩展的约束求解框架
[ ] 设计自适应的内存管理系统
[ ] 实现智能的桶化策略
[ ] 添加全面的 Shape 验证

优化阶段

[ ] 识别并消除冗余约束
[ ] 实施符号表达式简化
[ ] 优化运行时分发逻辑
[ ] 减少内存碎片
[ ] 平衡编译时和运行时开销

测试阶段

[ ] 覆盖边界情况（最小/最大维度）
[ ] 测试约束冲突处理
[ ] 验证内存管理正确性
[ ] 评估桶化效果
[ ] 进行性能回归测试

部署阶段

[ ] 收集运行时统计信息
[ ] 监控内存使用模式
[ ] 跟踪桶命中率
[ ] 分析性能瓶颈
[ ] 准备回滚方案

维护阶段

[ ] 定期更新桶化策略
[ ] 优化热点路径
[ ] 清理过时的约束
[ ] 更新文档
[ ] 分享最佳实践