任务调度引擎：任务图构建、依赖关系解析、拓扑排序算法、并行调度策略、调度器实现原理
大家好，我是你们的讲师。今天我们来聊聊 Fusion Compiler 运行时系统的核心——任务调度引擎。说实话，这个模块是我在项目中花时间最多、踩坑最深的部分。你想想看，一个芯片设计流程里，成百上千个任务要跑，谁先谁后、怎么并行、资源怎么分配，全得靠它。
我刚开始做调度器的时候，总觉得不就是排个序嘛，有什么难的？结果第一次跑大规模设计，直接死锁了。嗯，从那以后，我再也不敢小看这个模块了。
任务图构建
任务调度第一步，就是要把所有任务和它们的关系画成一张图。这张图，我们叫它任务图（Task Graph）。
任务图是个有向无环图（DAG）。每个节点代表一个任务，每条边代表依赖关系。比如综合任务必须在布局之前完成，那就在综合和布局之间画一条从综合指向布局的箭头。
我个人习惯用邻接表来存储任务图。为什么？因为芯片设计任务通常稀疏，邻接表比邻接矩阵省内存。我在一个 28nm 的项目里，任务数超过 5000，用邻接矩阵直接爆内存了，换成邻接表才搞定。
// 任务图节点结构
typedef struct {
int task_id; // 任务ID
char name[64]; // 任务名称
int duration; // 预估执行时间（秒）
int resource_req; // 资源需求（CPU核数）
int *dependencies; // 依赖的任务ID列表
int dep_count; // 依赖数量
} TaskNode;
// 邻接表表示的任务图
typedef struct {
TaskNode *nodes; // 节点数组
int **adj_list; // 邻接表
int node_count; // 节点数量
} TaskGraph;小提示：任务图的构建一定要考虑动态性。有些任务在运行过程中才会产生新的子任务，比如综合过程中的子模块优化。我建议预留动态添加节点的接口。
依赖关系解析
依赖关系解析，说白了就是搞清楚每个任务到底等谁。常见的依赖类型有三种：
- 数据依赖：前一个任务的输出是后一个任务的输入
- 资源依赖：两个任务争抢同一个硬件资源（比如同一个 license）
- 控制依赖：人为指定的先后顺序（比如先跑综合再跑形式验证）
我在项目中遇到过最头疼的是隐式依赖。什么叫隐式依赖？就是两个任务看起来没关系，但它们都读写同一个文件，这就产生了数据竞争。我曾经在一个 7nm 的项目里，因为没处理好隐式依赖，导致两个任务同时写 log 文件，结果日志全乱了，排查了三天才找到原因。
依赖解析的算法其实不复杂，核心就是遍历每个任务的依赖列表，建立反向索引。这样当某个任务完成时，能快速找到哪些任务在等它。
// 依赖解析：建立反向依赖索引
void build_reverse_deps(TaskGraph *graph, int **reverse_deps, int *rev_counts) {
for (int i = 0; i < graph->node_count; i++) {
for (int j = 0; j < graph->nodes[i].dep_count; j++) {
int dep_id = graph->nodes[i].dependencies[j];
reverse_deps[dep_id][rev_counts[dep_id]++] = i;
}
}
}警告：千万别忽略循环依赖检查！我曾经见过一个设计，综合脚本里 A 依赖 B，B 依赖 C，C 又依赖 A，结果调度器直接死循环了。一定要在构建任务图时就做环检测。
拓扑排序算法
拓扑排序，就是把有向无环图排成一个线性序列，保证每个任务都在它的依赖之后出现。常用的有两种算法：
| 算法 | 原理 | 时间复杂度 | 适用场景 |
|---|---|---|---|
| Kahn 算法 | 不断移除入度为 0 的节点 | O(V+E) | 静态任务图，需要实时获取可执行任务 |
| DFS 后序 | 深度优先遍历，按完成时间逆序排列 | O(V+E) | 需要完整排序结果，不关心中间状态 |
我个人更偏爱 Kahn 算法。为什么？因为它天然支持增量调度——每次移除一个入度为 0 的节点，就产生一个可执行任务。这在并行调度中特别有用。
// Kahn 算法实现拓扑排序
int* kahn_topological_sort(TaskGraph *graph, int *result_size) {
int *in_degree = calloc(graph->node_count, sizeof(int));
int *queue = malloc(graph->node_count * sizeof(int));
int front = 0, rear = 0;
// 计算入度
for (int i = 0; i < graph->node_count; i++) {
for (int j = 0; j < graph->nodes[i].dep_count; j++) {
int dep = graph->nodes[i].dependencies[j];
in_degree[i]++;
}
}
// 入度为0的节点入队
for (int i = 0; i < graph->node_count; i++) {
if (in_degree[i] == 0) queue[rear++] = i;
}
int *result = malloc(graph->node_count * sizeof(int));
int idx = 0;
while (front < rear) {
int node = queue[front++];
result[idx++] = node;
// 减少后继节点的入度
for (int j = 0; j < graph->node_count; j++) {
if (graph->adj_list[node][j]) {
in_degree[j]--;
if (in_degree[j] == 0) queue[rear++] = j;
}
}
}
*result_size = idx;
free(in_degree);
free(queue);
return result;
}并行调度策略
拓扑排序只是基础，真正的挑战在于并行调度。芯片设计任务不是跑得越快越好，还要考虑资源约束。我常用的并行调度策略有三种：
- 贪心调度：有可用资源就立刻执行任务。简单粗暴，但容易造成资源碎片化。
- 优先级调度：给每个任务算一个优先级，关键路径上的任务优先执行。我一般用任务在关键路径上的长度作为优先级。
- 资源感知调度：综合考虑任务优先级和资源需求，避免资源争抢。这个在 license 受限的场景下特别有用。
我记得有一次做 16nm 的芯片，用了 64 核的服务器跑流程。贪心调度虽然简单，但经常出现 60 个核在跑，4 个核闲着的情况。后来换成资源感知调度，把大任务和小任务混排，利用率直接提到了 90% 以上。
核心要点：并行调度不是越快越好，而是要在资源约束下最大化吞吐量。说白了，就是让所有核都忙起来，别闲着。
调度器实现原理
调度器的实现，我把它分成三个核心模块：
- 就绪队列：存放所有依赖已满足、等待执行的任务。我建议用优先队列，按优先级排序。
- 资源管理器：跟踪当前可用的 CPU 核数、内存大小、license 数量。任务执行前要申请资源，执行完释放。
- 事件循环：监听任务完成事件，更新依赖关系，把新就绪的任务加入队列。
调度器的主循环其实很简单，就是个 while 循环：
void scheduler_run(Scheduler *sched) {
while (1) {
// 1. 检查是否有任务完成
check_completed_tasks(sched);
// 2. 更新就绪队列
update_ready_queue(sched);
// 3. 尝试调度就绪任务
while (has_ready_task(sched) && has_available_resource(sched)) {
TaskNode *task = dequeue_ready(sched);
if (allocate_resource(sched, task)) {
execute_task_async(sched, task);
}
}
// 4. 如果没有任务在运行，退出
if (sched->running_count == 0 && sched->ready_count == 0) break;
// 5. 等待事件
wait_for_event(sched);
}
}这里有个细节要注意：任务执行是异步的。你不能在调度器里直接调用任务函数，那会阻塞整个调度循环。我一般用线程池来执行任务，调度器只负责分配。
避坑指南：我曾经在调度器里直接调用了综合工具的命令行，结果综合跑了两个小时，调度器卡死了两个小时。后来改成异步执行 + 回调通知，才解决问题。
知识体系总览
下面这张图是我自己画的，把任务调度引擎的核心逻辑串起来了。你仔细看看，应该能理解整个流程。
这张图从左到右、从上到下展示了调度引擎的完整流程。你注意看底部的反馈箭头——任务完成后会触发依赖更新，这就是事件循环的核心。
好了，任务调度引擎的核心内容就这些。说实话，调度器这个东西，理论看起来简单，真正写起来全是细节。我建议你从一个小规模的调度器开始写，跑通之后再逐步加功能。别一上来就想搞个大而全的，容易把自己绕进去。