DAG 调度

基于 DAG 的任务调度算法详解。

概述

Mini-ImagePipe 使用有向无环图（DAG）来表示算子依赖关系。调度器自动确定执行顺序和并行度。

Kahn's Algorithm

我们的拓扑排序使用 Kahn's algorithm（1962）：

1. 计算所有节点的入度
2. 将所有入度为 0 的节点加入队列
3. 当队列不为空时：
   a. 从队列中移除节点
   b. 将其加入排序列表
   c. 对于每个邻居，减少其入度
   d. 如果入度变为 0，将其加入队列
4. 如果排序列表包含所有节点 → 有效的 DAG
5. 否则 → 检测到循环

实现

std::vector<int> TaskGraph::getTopologicalOrder() const {
    std::vector<int> inDegree(nodes_.size(), 0);
    for (const auto& node : nodes_) {
        inDegree[node.id] = static_cast<int>(node.dependencies.size());
    }

    std::queue<int> q;
    for (size_t i = 0; i < nodes_.size(); ++i) {
        if (inDegree[i] == 0) {
            q.push(static_cast<int>(i));
        }
    }

    std::vector<int> order;
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        order.push_back(current);

        for (int dependent : nodes_[current].dependents) {
            if (--inDegree[dependent] == 0) {
                q.push(dependent);
            }
        }
    }

    return order.size() == nodes_.size() ? order : std::vector<int>{};
}

循环检测

基于 DFS 的循环检测在执行前验证图的有效性：

bool hasCycle = !graph.validate();
if (hasCycle) {
    return cudaErrorInvalidValue;
}

层级执行

任务根据依赖关系组织成层级：

Level 0:  [Source A]  [Source B]      ← 并行执行
Level 1:  [Process C]                  ← 等待 A
Level 2:  [Process D]                  ← 等待 B 和 C
Level 3:  [Sink E]                     ← 等待 D

多流执行

流分配策略

1. 同一层级的任务分配到可用流
2. 采用轮询分配实现负载均衡
3. CUDA 事件同步跨流依赖

错误传播

当任务失败时：

1. 任务状态 → FAILED
2. 触发错误回调
3. 所有下游任务标记为 FAILED（跳过）
4. 独立任务继续执行

参考资料

• Kahn, A. B. (1962). "Topological sorting of large networks." Commun. ACM.
• Cormen, T. H., et al. (2009). Introduction to Algorithms. MIT Press.