4、图调度与映射：调度算法与资源约束下的映射

好，咱们进入正题。图调度与映射，说白了就是回答两个问题：“谁先干？” 和 “谁来干？”。

你想想看，编译器把高级语言翻译成数据流图之后，图里每个节点都是一条指令。但芯片里的运算单元（比如加法器、乘法器）是有限的。怎么把这些指令安排到不同的时钟周期里，再分配到具体的硬件单元上——这就是调度与映射要解决的事。

我个人习惯把调度比作“排班表”，把映射比作“分座位”。排班排不好，资源就浪费；座位分不好，数据通路就打架。

4.1 列表调度：最经典的“贪心”策略

列表调度（List Scheduling）是我入行时学的第一个调度算法。它其实不复杂，核心思路就一句话：每次从“就绪队列”里挑一个优先级最高的指令发出去。

什么叫“就绪”？就是这条指令的所有依赖数据都已经准备好了。比如一条加法指令，它的两个操作数都算出来了，那它就可以进就绪队列。

优先级怎么定？常见的有两种：

• 最长路径优先：看这条指令到最终输出的最长路径长度，路径越长越优先。因为拖了它，后面一串都得等。
• 最大扇出优先：看这条指令的结果被多少条后续指令使用。用的人多，就先发，好让后面早点开工。

我在项目中遇到过一个问题：列表调度虽然简单高效，但它有个“短视”的毛病。它只看当前就绪队列里的最优解，不会为后面的指令做长远规划。有时候为了抢一个乘法器，把加法器闲置了，结果后面一堆加法指令排队等着——这就亏了。

4.2 贪心调度：更快，但更“莽”

贪心调度（Greedy Scheduling）比列表调度更激进。它不维护一个完整的就绪队列，而是每到一个时钟周期，就看看当前有哪些指令可以发射，然后能发多少发多少，直到资源用满为止。

说白了，就是“有活就干，别闲着”。

贪心调度的好处是速度快，实现简单。坏处是——嗯，它太“贪”了。有时候为了填满当前周期的资源，把一些本可以晚点执行的指令提前了，结果导致关键路径上的指令被挤到后面去，反而拖长了总周期数。

我举个例子你就明白了：

// 假设有两条指令：
// A: a = b + c   (延迟2周期)
// B: d = a + e   (依赖A的结果)
// 资源：1个加法器

// 贪心调度：
// 周期1: 发射A (加法器被占用)
// 周期2: 等待A完成 (加法器空闲，但B还不能发射)
// 周期3: 发射B
// 总周期：3

// 如果稍微“不贪”一点：
// 周期1: 发射A
// 周期2: 插入一条不依赖A的独立指令 (如果有的话)
// 周期3: 发射B
// 总周期：3 (但资源利用率更高)

你看，贪心调度在周期2里，加法器明明空闲，但它没有别的指令可发（因为就绪队列里只有B，而B还没准备好）。这时候如果有其他独立指令，贪心调度会优先发它们——但如果没有，它就干等着。

我个人觉得，贪心调度更适合资源非常充裕的场景。如果芯片里运算单元多到用不完，那贪心调度几乎就是最优解。但要是资源紧张，它就容易“踩坑”。

4.3 资源约束下的映射：把指令“塞”进硬件里

调度完了，接下来就是映射。映射解决的是“这条指令到底用哪个硬件单元来执行”的问题。

资源约束下的映射，核心挑战有三个：

• 资源数量限制：比如只有2个乘法器，但同一周期有3条乘法指令要发射，那就得把其中1条挪到下一周期。
• 资源类型匹配：加法指令不能跑到乘法器上，这是常识。但有些指令可以“复用”资源，比如整数加法和逻辑运算可以共用ALU。
• 数据通路冲突：两个运算单元如果共享一条总线，那同一周期就不能同时写结果。这个坑我踩过——有一次没检查总线冲突，仿真通过，但流片回来发现数据老是被覆盖。

映射的常用策略有：

1. 直接映射：每个指令类型绑定到固定硬件单元。简单，但灵活性差。
2. 动态映射：运行时根据资源占用情况动态分配。灵活，但硬件开销大。
3. 模调度映射：针对循环体，把多次迭代的指令交错映射到同一套硬件上。这是高性能计算里的常用招数。

4.4 一张图看懂调度与映射的流程

下面这张SVG图，是我自己画的调度与映射核心流程。你可以把它当作本章的“知识地图”。

4.5 实际项目中的经验总结

做了这么多年芯片设计，我总结了几条关于调度与映射的“血泪教训”：

嗯，调度与映射这块，说白了就是在有限资源下，找到指令执行的最优时空安排。没有银弹，只有根据你的芯片架构、应用场景、性能目标去反复调优。我建议你从列表调度入手，先跑通基本流程，再逐步加入贪心、模调度等高级策略。

记住：好的调度方案，能让芯片性能翻倍；差的调度方案，再牛的硬件也白搭。

公众号:蓝海资料掘金营，微信deep3321