一、AI 编译器中的 SRAM 内存分配管理算法
AI 编译器的 SRAM 分配目标通常包括：
- 最小峰值内存（peak memory）
- 减少带宽访问（减少 DRAM ↔ SRAM 往返）
- 保持计算并行度
- 为 kernel 调度与算子融合提供约束
在各大 NPU 编译器（TensorRT、TFLite、TVM、IREE、XNNPACK、各家 SoC NPU 编译器）中，常见的 SRAM 分配策略可分为三类：
1. 静态图的'生存期区间 (Liveness-based) 分配'
这是目前 最常见、所有主流编译器都使用的基础算法。
1.1 Linear Scan（线性扫描分配）
原理：
- 对每个 tensor 做 liveness analysis：得到
start与end点。 - 按时间顺序扫描分配固定区域。
特点：
- O(n) 时间复杂度，编译速度快。
- 分配结果可预测、确定性强。
- 对内存块（tensor）的生命周期要求较严。
缺点：
- 没有全局优化，不是最优解。
- 在多分支 / 大模型中依然可能碎片高。
绝大多数 NPU 编译器的 baseline 都是它（包括 TVM、ONNX Runtime EP、厂商私有编译器）。
2. 区间图着色（Interval Graph Coloring）
思想来自寄存器分配，将 tensor 视为区间图上的节点，冲突区间染色融合空间。
优点：
- 更接近最优内存布局。
- 支持在极小 SRAM 中 squeeze 更大模型。
缺点：
- NP-hard，需要启发式（heuristic）。
- 编译速度较慢，多用于高端设备（GPU/TPU 类编译器）。
TensorRT、Meta 的 Glow、部分 NPU 编译器内部采用该技术。
3. Memory Planning with Best-Fit / First-Fit（内存框选分配）
相比 linear scan 更灵活：
- First Fit：找第一个足够大的空洞。
- Best Fit：找最适合的空洞，减少碎片。
- Worst Fit：为未来保留更多大洞（rare）。
这些算法常用于：
- TFLite Micro
- XNNPACK
- 部分嵌入式 NPU 后端（如 ARM Ethos-U）
优点：
- 实现简单
- 对碎片化有改善
- 很适合 运算图较小/算子固定 的 microcontroller NPU
4. 仿射模型优化（Affine Memory Planning）
IREE、MLIR、边缘 AI 编译器常用。
- 建立一个 tensor offset 分配问题
