图优化：算子调度

可视化演示

展示AI编译器算子调度三维度：调度流程（拓扑依赖分析→就绪集计算前驱完成的算子→资源分配→执行循环推进直到完成）、调度策略对比（并行调度最大化吞吐利用多SM多核/内存感知调度最小化峰值内存避免同时激活过多张量/流水线调度最小化延迟三类非互斥组合使用）、关键路径优化（优化前A→B→C→D→E串行关键路径长度5无并行度/优化后B与C并行D与E并行关键路径长度3加速40%通过拓扑重排暴露并行度）,三模式切换理解算子调度核心机制。

调度的意义

周末晚上，小饭馆接到一桌十道菜的大单。后厨只有一位大厨时，只能按菜谱一道接一道做；但如果你请来了一支八人厨师团队、面前摆着八个灶台，问题立刻就变了：先做哪道菜？哪些菜能同时开火？哪道菜必须等另一道菜出锅才能动手？这就是调度的意义——决定每道工序以什么顺序、在哪个灶台、什么时候开始干。

在深度学习里，计算图就是菜谱：每个节点是一个算子（卷积、归一化、激活等），有向边代表张量在算子之间的流动。GPU 有数千个计算核心，相当于一支庞大的后厨团队。如果算子按照图里写的顺序一个个执行，绝大多数核心只能围观，硬件利用率极低。算子调度要做的事情，就是重新安排这些算子的执行顺序和并行方式，让尽可能多的计算核心同时忙起来，从而缩短整张图的执行时间。

串行执行是“一人后厨”的参照系：所有算子排成一队，总耗时等于每个算子耗时之和。

调度的目标，就是在不违反数据依赖的前提下，让总执行时间远远小于这个串行下界。好的厨师长拿到菜谱先扫一眼依赖关系，再排兵布阵，让一桌菜几乎同时出锅——这就是调度的价值。

依赖关系识别

菜谱里藏着严格的先后约束：肉必须焯水才能下锅爆炒，否则口感发柴；而高汤和蒸鱼互不相干，完全可以同时开火。这些约束不是厨师长随意定的，而是食材特性决定的。在计算图里，算子的依赖关系写在边上——一条边从算子 $v_1$ 指向 $v_2$，意味着 $v_2$ 必须等 $v_1$ 做完才能开始。

依赖关系中最常见的是数据依赖，也叫写后读（RAW）：$v_2$ 要读取 $v_1$ 写出的张量，比如卷积的输出喂给归一化层，归一化只能等卷积结束。此外还有读后写（WAR）和写后写（WAW），在并行执行、内存复用的场景下同样会限制重排。控制依赖则来自 if 等分支结构：分支汇合处的算子要等所有分支都执行完。一张计算图本质上是一个有向无环图（DAG），边就是依赖。依赖边规则很简单：一个算子的所有前驱都完成后，它才处于“就绪”状态，可以被调度执行。

数据依赖可以用读写集合精确判定——$v_1$ 写出的变量集合与 $v_2$ 读入的变量集合相交，说明 $v_2$ 必须等 $v_1$。

厨师长看菜谱时，心里默默画着一张“谁等谁”的关系图：能并行的菜分开安排，必须等待的菜排好先后。这张图，就是调度算法眼里的 DAG。

关键路径分析

一桌菜最快多久能上齐？不是把所有菜各做一遍的时间总和，而是看“最磨蹭”的那条流水线。比如宴席上必须有炖两小时的高汤，那不管其他菜多快，整桌菜至少也要两小时。这条最长的依赖链，就是关键路径。

在计算图中，从入口算子到出口算子的每一条路径，都把路径上所有算子的耗时加起来；其中最大的那个值就是关键路径长度。识别关键路径不必真的枚举所有路径——可以用前向遍历：从入口出发，不断更新每个算子的最早开始时间（等于所有前驱的完成时间最大值），最后取所有算子完成时间的最大值。

关键路径的意义在于它划定了加速极限：哪怕给后厨加再多人手，高汤该炖两小时还是两小时。资源应该优先喂给关键路径上的算子，否则整桌菜的总时间就会被这条“高汤链”卡死。

调度策略方法

厨师长手里有一本排班表。最稳妥的做法是拓扑排序——像“先备菜、再切配、最后掌勺”一样，按依赖关系的先后把算子排成一列，保证顺序合法。更聪明一点的做法是优先级调度：关键路径上的菜是硬菜，给它们插队，让它们尽早开工，因为一旦拖了它们，整桌菜都会延误。贪心调度则信奉“手里有活就干”：只要某个算子已经就绪，立刻把它派到空闲的计算单元上，绝不让灶台空等。动态调度则是应对“客人临时加菜”——运行时根据实测耗时不断调整后续安排。

无论哪种策略，衡量排班表好坏的指标都是完工时间（makespan）：在某种调度方案下，所有算子中最晚完成的那个时刻。调度优化的目标就是让这个最晚完成时间尽量小。

一张好排班表不在于花哨，而在于让每个灶台都别闲着、让硬菜别等太久。实际编译器往往把多种策略组合使用：用拓扑序保证正确，用优先级照顾关键路径，用贪心让资源满载。

并行度与负载

八位厨师不能都去切同一根葱。并行度不是越高越好，关键在分工合理：热菜组、凉菜组、汤锅组各司其职，谁忙完了就去帮最忙的组——这就是负载均衡。在 GPU 上，算子并行指的是让互不依赖的算子同时运行；流式并行是借助 CUDA stream 让不同 kernel 在时间上重叠；设备协同则是把不同算子分配到 GPU、CPU 等多类硬件上同时干活。

但 Amdahl 定律给所有并行优化画了一条天花板：程序里总有无法并行的串行部分，这部分时间不会随核心数增加而减少。串行比例 $f$ 越大，加速比的上限越低。这也是为什么调度不能只追求“让算子跑起来”，还要尽量减少串行瓶颈——比如把初始化、同步、内存拷贝这些“必须排队”的环节压缩到最小。

厨师长不会让八个人都去端同一盘菜，而是让每个人都在干活、且干的是当前最需要的活。调度器同样要平衡各计算单元的负载，避免“旱的旱死、涝的涝死”。

算子融合协同

焯水后的肉片，如果先装盘、放凉、收进冰箱，下锅前再拿出来，中间全是浪费的搬运时间。聪明的厨师会把焯水和下锅连成一道工序，省掉中间的装盘与冷藏。算子融合就是这个思路：把计算图上相邻的多个算子合并成一个 kernel 来执行。

融合带来的收益非常直观。原本每个算子都要从显存读一次输入、写一次输出，图里有 $N$ 个算子就是 $2N$ 次访存；融合成一个 kernel 后，中间张量直接留在寄存器和共享内存里，不落回显存，整体只需读一次输入、写一次输出。访存往往是比计算更贵的“搬菜”成本，省掉中间搬运对推理延迟立竿见影。经典的 Conv+BN+ReLU 融合，在 CNN 推理中几乎是标配。融合后图的节点变少，调度问题的规模也随之缩小，但要注意融合过度会让单个 kernel 资源占用过高，反而拖慢速度。

融合就是“连灶”——把几个步骤安排在一个灶台上连续完成，省掉中间洗锅、装盘、冷藏的折腾。它和调度是黄金搭档：融合缩减问题的规模，调度在缩减后的图上继续精打细算。

系统实践生态

现实世界里的后厨已经用上了高科技。XLA 像一位总厨，拿到整份菜谱后先做全局分析，把计算图编译成自己的中间表示（HLO），完成依赖分析和算子调度后再生成高效代码。PyTorch 2.0 的 torch.compile 则像一个“边看菜谱边排班”的聪明帮厨：先用 Dynamo 捕获计算图，再做图优化与代码生成。cuDNN 的 benchmark 模式像个爱试菜的品控——每次开工前把几种候选做法都试跑一遍，挑最快的那个。Triton 则是发给帮厨们的标准化操作手册，让开发者以接近 Python 的写法描述算子，由编译器负责映射到底层调度。

这些系统在“选择最快的实现”这件事情上高度一致：候选实现不止一种，与其靠理论猜，不如实测一把。

XLA、PyTorch 2.0、cuDNN、Triton 这些工具的本质，都是把“厨师长的经验”变成可自动运行的排班系统，让每一轮推理都能拿到一份不错的调度表。

挑战与前沿

厨房越来越大、菜单越来越长、客人还随时改菜——排班这件事正在变得空前困难。动态形状就是“客人临时改菜”：模型输入的长宽、batch大小在运行时才确定，计算图的结构虽然不变，但每个算子的耗时估算随时在变，提前排好的班表可能瞬间失效。

更麻烦的是搜索空间爆炸。调度一个 $n$ 个算子的图，合法的执行顺序本质上是一个拓扑排序，数量最多可以达到 $n!$ 量级；当 $n$ 到几十上百时，穷举所有方案是天文数字。事实上，在资源受限的通用场景下求最优调度是 NP-hard 问题，不存在多项式时间的通用最优解。因此工程上的出路是启发式算法加代价模型——代价模型负责估算每个算子在当前硬件上的耗时，启发式算法则在有限时间内给出“够好”的调度。端侧设备资源更紧张，调度器自身的开销也必须压到极低。

好的厨师长不是能穷举所有排法，而是有一套又快又稳的经验法则，加上对每道菜耗时的准确预估。算子调度的前沿，正是在动态、复杂、资源受限的现实里，用启发式和代价模型逼近那个理想的下界。

AI 应用场景

Python 演示

from collections import deque def build_model():    # 每个算子: (耗时, 依赖的算子列表)    ops = {        'Input':  (1, []),        'Conv1':  (1, ['Input']),        'BN':     (1, ['Conv1']),        'Conv2':  (1, ['Conv1']),        'ReLU':   (1, ['Conv2']),        'Add':    (1, ['BN', 'ReLU']),        'Output': (1, ['Add']),    }    return ops def analyze_and_schedule(ops):    names = list(ops.keys())    indeg = {n: len(ops[n][1]) for n in names}    adj = {n: [] for n in names}    for n in names:        for dep in ops[n][1]:            adj[dep].append(n)     # Kahn 拓扑排序，同时计算每个算子的最早开始时间    start = {n: 0 for n in names}    order = []    q = deque([n for n in names if indeg[n] == 0])    while q:        u = q.popleft()        order.append(u)        for v in adj[u]:            start[v] = max(start[v], start[u] + ops[u][0])            indeg[v] -= 1            if indeg[v] == 0:                q.append(v)     finish = {n: start[n] + ops[n][0] for n in names}    critical_len = max(finish.values())     # 贪心就绪调度：每个时间单位执行所有已就绪算子    ready = deque(n for n in names if not ops[n][1])    done = set()    remaining = {n: ops[n][0] for n in names}    time = 0    while ready:        next_ready = []        for _ in range(len(ready)):            u = ready.popleft()            remaining[u] -= 1            if remaining[u] == 0:                done.add(u)                for v in adj[u]:                    if v not in next_ready and all(d in done for d in ops[v][1]):                        next_ready.append(v)        time += 1        for v in next_ready:            ready.append(v)    return order, critical_len, time if __name__ == '__main__':    ops = build_model()    order, critical_len, greedy_time = analyze_and_schedule(ops)    serial_time = sum(v[0] for v in ops.values())    print('拓扑序:', ' -> '.join(order))    print('串行耗时:', serial_time)    print('关键路径长度:', critical_len)    print('贪心就绪调度耗时:', greedy_time)

1. indeg = {n: len(ops[n][1]) for n in names}统计每个算子的前驱依赖数量，用于 Kahn 拓扑排序。
2. q = deque([n for n in names if indeg[n] == 0])没有依赖的算子先入队，相当于后厨里“可以直接开工”的菜。
3. start[v] = max(start[v], start[u] + ops[u][0])前向传播更新最早开始时间，取所有前驱完成时刻的最大值。
4. critical_len = max(finish.values())所有算子完成时刻的最大值就是关键路径长度，也是理论上限。
5. remaining[u] -= 1贪心模拟中每次消耗一个时间单位，代表 CPU 帮算子“走一秒”。
6. all(d in done for d in ops[v][1])检查一个算子的所有前驱是否都已完工，只有全部完成它才就绪。

常见误区

面试题