关键词：内存复用 · 静态图 · 区间图着色 · 整数规划 · 贪心策略 · 碎片控制
📖 目录
-
1. 静态计算图与内存复用问题 -
2. 张量生命周期、峰值内存与冲突模型 -
3. 精确求解：混合整数线性规划模型 -
4. 从精确求解到启发式算法的必然过渡 -
5. 离线贪心：尺寸降序与最左适配 -
6. 在线贪心：时间推进、最佳适配与即时合并 -
7. 各类算法达到最优的充分条件 -
8. 对比实验与性能量化分析 -
9. 总结与未来方向
1. 🌐 静态计算图与内存复用问题
深度学习模型通常表示为 有向无环图（DAG），节点代表算子（卷积、矩阵乘法等），边代表张量数据流。编译器在运行前已知每个算子的执行顺序，因此能推导出每个中间张量的 产生时刻（算子输出时）和 最后使用时刻（被所有消费者使用完毕时）。这两个时刻构成张量的 生命周期。
🎯 核心优化目标：通过将生命周期互不重叠的张量分配到同一块内存地址，最小化 峰值内存占用，从而允许更大模型或更大批量尺寸，避免硬件显存溢出（OOM）。
以下是一个典型计算图结构示意（算子与张量数据流）：
-
• 该图展示了一个简单的前向传播路径，从输入到 Softmax 输出。 -
• 虚线箭头表示算子在执行过程中产生的中间张量，其形状标注在边上。 -
• 每个中间张量仅在其产生和最终使用之间存活，这为内存复用提供了机会。
2. ⏳ 张量生命周期、峰值内存与冲突模型
设张量集合为 。每个张量 具有：
-
• 尺寸 （以元素个数计） -
• 生命周期区间 ，左闭右开
💡 解释：这里 是张量占用的内存单元总数，等于各维度长度之积，例如形状
(3, 224, 224)的张量尺寸为 。生命周期左闭右开表示张量在时刻 被分配，在时刻 被释放，因此区间内任意时刻它都存活。
下图展示了三个张量在时间轴上的活跃区间（横轴为时间步）：
-
• 区间长度表示张量存活的时间跨度。 -
• 重叠部分表示在同一时刻两个张量同时存在，它们因此冲突，不能共享内存。 -
• 例如 T0 与 T1 在 [1,2) 重叠，T1 与 T2 在 [2,3) 重叠，而 T0 与 T2 在边界处不重叠（因为左闭右开）。
📈 峰值内存 是整个计算图运行过程中任意时刻已分配内存总量的最大值。它直接决定了模型能否在给定的硬件（如 GPU）上运行，因为硬件显存容量是硬约束。优化内存复用的核心就是 最小化 。
⚠️ 一个常见的误解是：峰值内存仅由同时存活张量的总大小决定。然而，如果没有合理的内存布局（即产生大量内存碎片），即使总存活量不大，也可能因为无法利用空闲空隙而导致被迫扩展池尾，最终使 显著增大。例如，若两个冲突张量之间产生了一个无法被其他张量利用的小空隙，系统可能不得不将新张量放在更靠后的位置，从而抬高了 。因此，碎片控制 与 压实（compaction） 是内存分配算法的关键课题。
🔗 冲突定义：两个张量 若满足 ，则它们同时存活，不能共用内存。
💡 解释：该条件等价于区间 与 有非空交集。由于区间是左闭右开的，边界相等（如 ）不算冲突，允许张量在释放时刻立即复用该内存，这是安全且高效的。
🧩 冲突图（Conflict Graph） 是一种将冲突关系可视化的有效工具。节点表示张量，若两个张量冲突，则在它们之间添加一条无向边。以下是对应上述生命周期示例的冲突图：
-
• 图中 T0 与 T1 有边（冲突），T1 与 T2 有边（冲突），而 T0 与 T2 之间用虚线断开表示 不冲突（因为它们在边界 2 处不重叠）。 -
• 该图清晰地展现了张量之间的冲突关系，帮助我们快速识别 最大团（maximum clique），即两两冲突的张量集合。最大团的总尺寸是峰值内存的一个下界（任何算法都无法低于该下界）。 -
• 在本例中，最大团为 {T0, T1} 和 {T1, T2}，其尺寸分别为 10+20=30 和 20+15=35，因此理论下界为 35。
📝 内存分配问题：为每个张量 寻找非负整数起始偏移 ，使得任意冲突对满足内存区间互斥：
目标是最小化峰值 。
💡 解释：该式是内存分配的核心约束。对于任意两个冲突的张量，它们的占用区间必须完全分离——要么 在 的左边（ ），要么 在 的左边（ ）。偏移量 是整数，表示从内存池起始地址算起的字节偏移（若元素大小为一）。目标函数 取所有张量右端最大者，也就是整个内存池所需的最小容量。
3. 🧮 精确求解：混合整数线性规划模型
我们采用 混合整数线性规划（MILP） 获得全局最优解，作为启发式算法的评价基准。
📌 决策变量：
-
• 连续整数 ：张量 的偏移 -
• 整数 ：峰值内存 -
• 二元变量 ，对每个冲突对 （ ），表示 是否排在 之前
💡 解释： 是辅助变量，用来在整数规划中表达“或”关系。若 ，意味着 在 左边；若为 0，则 在 左边。
🔒 约束：
-
1. 容量上界： -
2. 互斥约束（大M法）：令 ，对每个冲突对：
💡 解释：第一个约束保证所有张量都落在内存池内。第二个约束利用大常数 将逻辑关系转化为线性不等式：当 时，第一式变为 ，第二式变为 （宽松，因 足够大，基本无效），于是强制 在 左边；当 时效果相反。 取所有张量尺寸之和，确保它大于任何可能的偏移差，不会错误地截断可行解。
🎯 目标函数： 。
⚙️ 求解流程示意如下：
-
• 该流程将问题编码为标准的整数线性规划形式。 -
• 冲突矩阵从张量的生命周期区间预先计算。 -
• 求解器（如 CBC）通过分支定界法搜索最优整数解。 -
• 对于 的小规模问题，通常在几秒内可得最优解。
💻 核心实现：
def milp_allocate(tensors):
n = len(tensors)
sizes = [t.size for t in tensors]
M_big = sum(sizes)
conflicts = [(i,j) for i in range(n) for j in range(i+1,n)
if tensors[i].overlap(tensors[j])]
solver = pywraplp.Solver.CreateSolver('CBC')
x = [solver.IntVar(0, M_big, f'x_{i}') for i in range(n)]
peak = solver.IntVar(0, M_big, 'peak')
y = {}
for i,j in conflicts:
y[(i,j)] = solver.BoolVar(f'y_{i}_{j}')
for i in range(n):
solver.Add(x[i] + sizes[i] <= peak)
for i,j in conflicts:
solver.Add(x[i] + sizes[i] <= x[j] + M_big*(1-y[(i,j)]))
solver.Add(x[j] + sizes[j] <= x[i] + M_big*y[(i,j)])
solver.Minimize(peak)
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
return int(peak.solution_value()), [int(x[i].solution_value()) for i in range(n)]
raise RuntimeError("求解失败")
-
• 代码中定义了大常数 作为安全上界。 -
• 对每个冲突对引入顺序变量，通过大M法实现互斥。 -
• 求解器若返回最优，则直接得到最优峰值和偏移列表。
针对第2章示例的三个张量，该求解器返回峰值 35，分配方案为：T1 偏移 0，T2 偏移 20，T0 偏移 20（复用 T2 的空隙）。这一结果验证了 MILP 的全局最优性。
4. 🔄 从精确求解到启发式算法的必然过渡
上一节我们看到，MILP 能够为小规模问题提供 全局最优解，这让它成为评估其他算法性能的 黄金标准。然而，当张量数量超过 100 时，MILP 的求解时间从秒级骤增至数十分钟甚至数小时，这在实际编译场景中是不可接受的——模型加载和编译必须控制在 秒级以内。
与此同时，深度学习模型规模持续增长，GPT 类模型包含数千个中间张量，精确求解完全不可行。因此，工业界普遍采用 启发式算法：它们牺牲严格的最优性保证，换回 毫秒级的求解速度，且在大多数实际场景中能达到最优值的 95%~98%。
接下来的两章将介绍两种代表性的贪心策略：
-
• 离线贪心（第 5 章）利用全局生命周期信息，通过 尺寸降序 + 最左适配 实现高效压实。 -
• 在线贪心（第 6 章）模拟运行时分配器，仅依赖当前时刻信息，通过 Best‑Fit + 即时合并 控制碎片。
两者共同揭示了 信息完备性 与 优化质量 之间的权衡关系。下表从三个维度对它们进行初步对比：
5. 🚀 离线贪心：尺寸降序与最左适配
5.1 📋 算法步骤
-
1. 将所有张量按尺寸 从大到小排序。 -
2. 依次处理每个张量： -
• 收集所有已分配且与其冲突的张量的占用区间 。 -
• 合并这些区间为不相交的“已占用”集合。 -
• 从左向右扫描，找到第一个能容纳 的空隙，放置于此；若不存在，则放置在当前池尾（即峰值位置）。 -
3. 记录偏移并更新峰值。
5.2 📐 形式化表达
处理序列 满足 ，对张量 定义可行偏移集合
其中 为已分配集合。选择 。
💡 解释：该公式刻画出所有不会与已有冲突张量重叠的偏移位置。 中记录的是已经放置好的张量的偏移和大小。对于每个已分配且冲突的 ， 必须满足要么完全在其左侧，要么完全在其右侧。在所有满足条件的非负整数中，贪心选择最小的 ，这就是“最左适配”的数学表达。
5.3 🧭 启发式逻辑
-
• 降序排序：大尺寸张量对地址连续性要求更高，其可行间隙随尺寸增大急剧减少。优先处理它们能避免后期“大块无处安放”的困境，从而将剩余碎片空间留给数量众多的小张量填充。 -
• 最左适配：强制压实到低地址能最大化内存池右端的连续空闲长度。右端区域越大，后续突发的大块分配请求就越不需要触发池尾扩展，直接抑制峰值增长斜率，并减少碎片产生的可能性。
📊 流程示意图：
-
• 该流程每次迭代只处理当前最大的张量，决策基于当前已放置的状态。 -
• 合并区间操作将多个碎片合并为一个大的不可用区间，简化空隙扫描。 -
• 由于贪心策略不考虑后续张量，但排序保证了后续张量尺寸更小，容易适配剩余空隙。 -
• 该算法在区间图着色问题中表现优异，平均接近最优。
💻 核心实现：
def offline_greedy(tensors):
sorted_tensors = sorted(tensors, key=lambda t: -t.size)
placements = {}
peak = 0
for t in sorted_tensors:
occupied = []
for pid, (off, sz, st, ed) in placements.items():
if not (ed <= t.start or t.end <= st):
occupied.append((off, off + sz))
# 合并区间
occupied.sort()
merged = []
for l, r in occupied:
if not merged or l > merged[-1][1]:
merged.append([l, r])
else:
merged[-1][1] = max(merged[-1][1], r)
offset = 0
for l, r in merged:
if offset < l and l - offset >= t.size:
break
offset = max(offset, r)
placements[t.id] = (offset, t.size, t.start, t.end)
peak = max(peak, offset + t.size)
return peak, [placements[t.id][0] for t in tensors]
-
• 代码首先排序，然后逐个张量处理。 -
• 对每个张量，收集冲突已分配区间，合并后扫描空隙。 -
• 放置后更新峰值，最后按原始顺序返回偏移。
对示例张量运行该算法，排序后顺序为 T1(20)、T2(15)、T0(10)。放置结果：T1 占 [0,20)，T2 占 [20,35)，T0 扫描空隙发现 [20,35) 能容纳 10，因此放置于 20，峰值 = 35。与 MILP 最优解完全一致。复杂度 ，处理数千张量仅需数毫秒。
6. 🛡️ 在线贪心：时间推进、最佳适配与即时合并
6.1 📂 数据结构
-
• 已分配表：记录当前存活张量的 (偏移, 尺寸, 释放时刻) -
• 空闲块列表：按偏移排序，记录可用连续内存区间
6.2 ⚡ 分配与释放规则
分配过程（时刻 ，张量 ）：
-
• 在空闲块中查找所有尺寸 的块，选择 尺寸最小 的块（Best‑Fit）。 -
• 若找到，从该块切出 ，剩余部分放回空闲列表。 -
• 若未找到，则在当前池尾分配新内存，峰值增加 。
释放过程（时刻 ）：
-
• 从已分配表中移除张量，将其占用的块插入空闲列表。 -
• 立即合并相邻空闲块，维持大块连续空间。
6.3 📐 形式化数学
空闲块集
，分配时选择
。
释放张量
后，合并相邻块：
，
为左右相邻空闲块。
💡 解释： 的表达式表示在所有大小不小于 的空闲块中，选取大小最小的那个，这就是 Best‑Fit 策略。合并公式中， 是位于刚释放块左右两侧的空闲块，将它们与新释放的块连接起来，形成更大的连续空闲区域，从而减少碎片。
6.4 🧭 启发式逻辑
-
• 最佳适配（Best-Fit）：最小化本次分配产生的内部碎片大小。选择最接近请求尺寸的空闲块，能保留最大块给未来的大请求，这是一种保守的风险规避策略——宁可产生大量极小的“边角料”，也不愿将大块切碎。 -
• 即时合并（Coalescing）：内存碎片化的本质是空闲块被已分配块物理隔离。只有在释放时立即合并相邻块，才能对抗时间累积导致的熵增，确保空闲总容量与最大连续块大小之间的差距始终保持收敛，从而抑制峰值因碎片而增大。
📊 流程示意图：
-
• 该流程按时间顺序推进，每个事件驱动状态更新。 -
• 分配时 Best-Fit 查找是在排序空闲块上的线性扫描。 -
• 释放后立即合并，确保空闲块始终保持最大连续长度。 -
• 这种设计不依赖未来信息，鲁棒性强。
💻 核心实现：
def online_greedy(tensors):
events = []
for t in tensors:
events.append((t.start, 0, t.id))
events.append((t.end, 1, t.id))
events.sort(key=lambda x: (x[0], x[1]))
allocated = {} # id -> (off, size, end)
free_blocks = [] # (off, size)
peak = 0
offsets = [0]*len(tensors)
for time, typ, tid in events:
t = tensors[tid]
if typ == 0: # alloc
size = t.size
best_idx, best_fit = -1, float('inf')
for i, (off, sz) in enumerate(free_blocks):
if sz >= size and sz < best_fit:
best_fit, best_idx = sz, i
if best_idx != -1:
off, sz = free_blocks.pop(best_idx)
if sz > size:
free_blocks.append((off+size, sz-size))
free_blocks.sort(key=lambda x: x[0])
else:
off = peak
peak += size
allocated[tid] = (off, size, t.end)
offsets[tid] = off
else: # free
off, size, _ = allocated.pop(tid)
free_blocks.append((off, size))
free_blocks.sort(key=lambda x: x[0])
merged = []
for off2, sz2 in free_blocks:
if not merged or off2 > merged[-1][0] + merged[-1][1]:
merged.append([off2, sz2])
else:
merged[-1][1] += sz2
free_blocks = [(o, s) for o, s in merged]
return peak, offsets
-
• 事件列表包含分配（type=0）和释放（type=1），同一时刻先释放后分配。 -
• 空闲块始终按偏移排序，以便合并。 -
• Best-Fit 扫描所有空闲块，选择最小可用块。
对示例张量按时间顺序模拟：时刻0分配T0（峰值10），时刻1分配T1（无空闲块，扩展至30），时刻2释放T0（空闲块[0,10)），同时分配T2（Best-Fit选中[0,10)但尺寸不足15，被迫扩展至45）。最终峰值 45，比最优值高28.6%。这说明在线算法因无法预见未来，导致碎片无法利用，峰值增大。复杂度 ，常用于PyTorch缓存分配器。
7. ✅ 各类算法达到最优的充分条件
7.1 🟢 离线贪心的最优条件
-
• 生命周期呈嵌套（Laminar）结构：任意两个区间要么不相交，要么一个完全包含另一个。此时冲突图为森林，降序最左贪心等价于树的最优着色。 -
• 所有张量尺寸相等：问题退化为区间图着色，区间图是完美图，贪心首次适配直接得到最小颜色数。 -
• 所有大张量形成一个最大团：即最大尺寸的张量彼此都重叠，其总尺寸构成不可超越的下界，贪心不会突破该下界。
7.2 🟡 在线贪心的最优条件
-
• 释放顺序严格为分配逆序（LIFO）：类似栈式内存，空闲块总在池尾，合并后无碎片，峰值等于历史最大同时存活量。 -
• 所有请求尺寸为幂次且可完全匹配：Best‑Fit配合Buddy系统，不会产生不可用碎片。
7.3 📊 近似比保证
-
• 对于区间图，离线降序首次适配的渐近竞争比 ≤ 1.22。 -
• 在线算法因缺少未来信息，最坏情况可能偏离较大（如示例中的45 vs 35）。
8. 📊 对比实验与性能量化分析
为了直观展示不同分配策略下的内存布局，下图绘制了张量在内存池中的具体起始偏移及占用区间（对应本例的三个张量）：
-
• 该布局展示每个张量在内存池中的具体起始偏移位置。 -
• 多个张量起始于同一偏移（如 T0 和 T2）表明它们实现了内存复用。 -
• 总跨度即为峰值内存，直观反映算法性能。 -
• 若布局中出现较多未被占用的间隙，则说明碎片严重，峰值被抬高。
采用标准测试用例（三个张量尺寸10、20、15，生命周期 [0,2)、[1,3)、[2,4)），三种策略的分配结果如下表：
🔍 关键洞察：
-
• 离线贪心在此达到最优，因大张量 T1 和 T2 重叠形成瓶颈，小张量 T0 可复用空隙。 -
• 在线贪心因无法预见 T2，在 T0 释放前扩展池尾，导致峰值增加 28.6%。 -
• 这量化了静态编译期优化的价值——全知全局时间表可节省约 30% 内存。
大规模随机测试（100张量）显示离线贪心平均比在线优 15%~20%，运行时间均 <10ms，而 MILP 在 时求解时间指数增长。离线贪心的性能优势在张量尺寸分布偏斜（少数大张量、大量小张量）时尤为显著，因为降序排序能最大化大张量之间的空隙复用率，减少碎片。
9. 🏁 总结与未来方向
本文系统梳理了三种典型策略：
-
• MILP精确求解 🎯：最优基准，但规模受限。 -
• 离线贪心（尺寸降序+最左适配） 🚀：接近最优，速度极快，编译优化首选。其启发性在于 先难后易的空间压实。 -
• 在线贪心（时间推进+Best‑Fit+合并） 🛡️：鲁棒性强，适合动态场景。其启发性在于 无未来信息下的最小承诺与碎片抑制。
我们给出了严格数学模型、完整实现和可视化辅助，通过对比实验揭示信息完备性对内存利用率的巨大影响，并强调了峰值内存的重要性以及碎片对峰值的负面影响。
🌟 未来方向：
-
• 联合优化算子调度与内存分配，改变执行顺序以降低峰值。 -
• 支持多级存储（HBM、DDR、共享内存）的异构分配。 -
• 将启发式嵌入JIT编译器，实现自适应规划。
全部代码开源，可直接用于学术验证或工业原型开发。