AI 编译器中的指令调度算法总览

AI 编译器的指令调度目标主要有三类：

1. 减少 pipeline stall / 提升 ILP
2. 隐藏访存延迟、充分利用片上 SRAM / buffer
3. 特殊硬件结构如 NPU 的数据复用、tensor tile 排布优化

从主流编译器（LLVM、TVM、IREE、TensorRT、NPU 私有编译器）来看，调度算法可以分为 基础调度算法、图调度算法（Graph-Level）、深度优化算法（Heuristic / ML-based） 三层。

---

1. 基础指令调度算法（Instruction-Level）

这些是 LLVM 后端也在用的经典调度算法，适合 CPU/NPU/自研硬件。

1.1 List Scheduling（列表调度）—— 最常见

• 几乎所有 AI 编译器后端都用
• 基于 优先级 + 就绪队列
• Priority 可按：
  • latency（延迟）
  • critical path
  • resource usage（ALU/Load/Store/FMA）
• 简洁、可扩展

常见变体：

• Top-down List Scheduling
• Bottom-up List Scheduling
• Bidirectional Scheduling

---

1.2 Critical Path Scheduling（关键路径优先）

• 为每个指令计算 从此指令到终点的最长路径长度
• 优先安排关键路径上的操作
• 图神经网路 / transformer 类模型中非常有效（因为矩阵/卷积层本身依赖链长大）

TVM / IREE / TensorRT 的调度器里常常嵌入 Critical Path 分数。

---

1.3 Sethi–Ullman（树型表达式调度）

• 对树表达式优化寄存器压力
• 在 CNN 中的 element-wise 上很常见
• 常见于 compiler IR → target IR lowering 的最后一跳

---

1.4 Cycle Scheduling（周期调度）

适合固定周期流水线 NPU，目标是：

• 让 FMA、Load、Store、ALU 完全 pipeline 化
• 避免 bubble

指令会被分配到一个个“周期 slot”内。

NVIDIA Tensor Core、Cambricon MLU、Huawei Ascend 都有 Cycle-based 调度器。

---

2. 图调度算法（Graph-level Scheduling, Operator-level Scheduling）

这一类发生在 Graph IR，例如 TVM Relay、TensorRT Network、IREE MHLO/StableHLO。

目标是让：

• tensor 保持在 SRAM（降低 DRAM 次数）
• operator 融合得更好
• tile 能复用

图级调度比传统 CPU 指令调度要复杂。

---

2.1 ASAP（As Soon As Possible）

• 尽快调度计算
• 减少 critical path 长度

与：

2.2 ALAP（As Late As Possible）

• 推迟算子，增大调度灵活性
• 为融合（fusion）创造更多机会

二者常配合用于Slack = ALAP - ASAP 计算。

---

2.3 Topological Sort Scheduling（拓扑排序调度）

• 基础图调度
• 应用于 NNIR → TIR、NNIR → NPU IR 的图结构整理
• AI Compiler Graph Level 的基础

---

2.4 Resource-aware Graph Scheduling（资源感知图调度）

适用于 NPU 编译器（SRAM/block/preload/compute）：

• 考虑 tile 大小
• 考虑 buffer 容量
• 考虑 Load/Compute/Store 三流水的 overlap
• 目标是实现：
  • “Compute-Load overlap”
  • “SRAM ping-pong buffer”
  • “double buffering”

如 TensorRT tactic selection、Ascend GE Graph Engine、TVM auto-scheduler 都会做这个。

---

3. 深度优化类调度算法（Heuristic / Search / 学习）

这是近几年 AI 编译器中最“硬核”的部分，主要用于 TVM、IREE、TensorRT、XLA 等自动调优框架。

---

3.1 ILP（整数线性规划）调度

适合 kernel-level / block-level 的精确调度：

• 变量：每条指令的 cycle
• 约束：依赖、资源限制
• 目标：最小化总执行时间

严重 NP-hard，但对小 kernel 很有效。

IREE、XLA GPU kernel 调度都有 ILP 组件。

---

3.2 Simulated Annealing（模拟退火）

搜索调度序排列的最优解。
TVM auto-scheduler 中比较常见。

---

3.3 Genetic Algorithms / Evolutionary Search（遗传算法）

TVM AutoTVM / AutoScheduler 用过。

---

3.4 ML-based Scheduling（机器学习调度）

近几年很热：

• 使用 GNN（图神经网络） 预测指令/算子顺序
• 使用 强化学习 RL 做调度策略
• TensorRT tactic 选择使用大量数据 + 深度学习模型
• LLVM 也有 MLGO：机器学习优化编译器优化序列

这类调度通常比传统启发式提升 5%~20%。

---

4. NPU/AI 专用调度（重点）

你如果要做 NPU 编译器，以下算最重要：

4.1 Load-Compute-Store Pipeline Scheduling

• 把 Load / Compute / Store 重叠起来
• 典型三流水结构
• 类似 GPU 的 “software pipeline”

核心策略：

• 让下一 tile 的 LOAD 与当前 tile 的 COMPUTE 并行
• 让当前 COMPUTE 的 STORE 与下一 COMPUTE 并行

4.2 Tiling-aware Scheduling

• tile 顺序影响 sram hit-rate
• 改 tile 顺序可以减少 DMA 次数

4.3 Reuse-aware Scheduling

• 对 weight / activation 进行重用调度
• AI 加速器的吞吐量很依赖这项

4.4 NPU Latency Hiding Scheduling

• 某些 NPU 上 LOAD latency 很高
• scheduling 时必须主动“铺前”

---

简单的分类图

Instruction Scheduling
├── 传统后端调度
│   ├── List Scheduling
│   ├── Critical Path Scheduling
│   ├── Cycle Scheduling
│   ├── Sethi–Ullman
│
├── 图级调度（Graph-level）
│   ├── ASAP / ALAP
│   ├── Topological Scheduling
│   ├── Resource-aware Scheduling
│
└── 搜索/学习调度
    ├── ILP
    ├── Simulated Annealing
    ├── Genetic Search
    ├── ML-based Scheduling (RL / GNN)