ONNX 调度优化器 (ONNX Scheduler)

ICPC 竞赛题 - 深度学习推理引擎中的节点调度优化问题

📖 文档导航

文档	描述	面向读者
题目介绍	完整的竞赛题目介绍，包含题目描述、规则说明、提交指南	参赛选手
系统设计文档	详细的系统架构设计、数据结构、算法流程	命题人、开发者
实现计划	代码实现计划和进度	开发者

---

题目描述

在深度学习推理引擎中，如何高效调度 ONNX 计算图是一个核心挑战。给定一个或多个 ONNX 计算图，每个图包含多个算子节点，节点之间存在依赖关系。系统具有有限的内存资源和多个专用流水线（如 vector、cube、dma 等）。

目标是在满足所有约束条件下，确定每个节点的最优切分策略（tiling），使得整体调度时间最优。

项目结构

comp/
├── src/                    # 源代码
│   ├── generator.py        # 数据生成器
│   ├── baseline_solver.py  # 基线求解器
│   ├── reference_solver.py # 参考解法 (改进启发式)
│   └── checker.py          # 评测器
├── tests/                  # 测试用例
│   ├── test_generator.py
│   ├── test_baseline_solver.py
│   ├── test_reference_solver.py
│   └── test_checker.py
├── data/                   # 测试数据
│   ├── test_01_simple.yaml
│   ├── test_02_chain.yaml
│   ├── test_03_dag.yaml
│   ├── test_04_multi_graph.yaml
│   ├── test_05_tight_memory.yaml
│   └── reference/          # 参考答案
├── scripts/                # 工具脚本
│   ├── generate_data.py    # 数据生成脚本
│   ├── run_solver.py       # 基线求解器
│   ├── run_reference_solver.py  # 参考解法
│   └── run_all_tests.sh    # 测试脚本
└── docs/                   # 文档
    ├── INTRODUCTION.md     # 题目介绍
    ├── design/             # 设计文档
    └── plans/              # 实现计划

安装要求

• Python 3.8+
• PyYAML
• pytest

pip install pyyaml pytest

快速开始

1. 生成样例数据

python scripts/generate_data.py --graphs 1 --nodes 5 --max-tiling 4 --output data/sample.yaml

2. 运行基线求解器

python scripts/run_solver.py -i data/sample.yaml -o output.yaml

3. 运行参考解法 (推荐)

python scripts/run_reference_solver.py -i data/sample.yaml -o output.yaml

4. 验证解的正确性

python -m src.checker -i data/sample.yaml -o output.yaml

5. 运行所有测试

pytest tests/ -v

测试用例说明

测试用例	描述	节点数	难度
test_01_simple	单节点	1	★☆☆
test_02_chain	链式依赖	3	★★☆
test_03_dag	DAG 依赖	4	★★★
test_04_multi_graph	多图调度	4	★★★
test_05_tight_memory	紧张内存	3	★★★★

API 使用

数据生成

from src.generator import generate_sample_data

yaml_str = generate_sample_data(
    num_graphs=2,
    nodes_per_graph=[3, 4],
    max_tiling=4,
    total_memory=3145728,
    seed=42
)

基线求解

from src.baseline_solver import solve_single_graph
from src.generator import Node, Graph, SystemConfig

nodes = [
    Node(name="A", exec_time=1000, exec_noise=50,
         ocu_memory=524288, pipeline="vector",
         max_tiling_cnt=2, dependencies=[]),
    Node(name="B", exec_time=800, exec_noise=40,
         ocu_memory=524288, pipeline="cube",
         max_tiling_cnt=1, dependencies=["A"])
]

graph = Graph(graph_id=1, start_time=0, deadline=5000, priority=1, nodes=nodes)
config = SystemConfig(total_memory=2097152, pipelines=["vector", "cube"])
result = solve_single_graph(graph, config)

参考解法 (改进启发式)

from src.reference_solver import solve_single_graph_improved
from src.generator import Node, Graph, SystemConfig

# 同上创建 graph 和 config
result = solve_single_graph_improved(graph, config)
print(f"Makespan: {result.makespan}")

方案验证

from src.checker import validate_solution

result = validate_solution("input.yaml", "output.yaml")
if result.is_valid:
    print(f"Valid! Makespan: {result.makespan}")
else:
    print(f"Invalid: {result.error}")

评测标准

硬约束检查（不满足则判为错误）

• 任意时刻内存占用不超过上限
• 所有依赖关系得到满足
• 同一流水线无时间重叠

软约束比较（按优先级排序）

1. 高优先级图的截止时间满足数
2. 整体 makespan（最后完成时间）
3. 峰值内存使用（作为平局决胜）

算法思路

部分分策略

子任务	约束	分值	推荐算法
1	单图 + 无依赖 + 无 tiling	10%	贪心
2	单图 + DAG + 无 tiling	20%	拓扑排序 + 贪心调度
3	单图 + 无依赖 + 有 tiling	20%	枚举 + 贪心
4	单图 + DAG + 有 tiling	25%	关键路径 + 启发式
5	多图 + 完整约束	25%	元启发式/混合整数规划

推荐算法

• 小规模数据：枚举 + 剪枝
• 中等规模：关键路径 + 贪心调度
• 大规模：模拟退火、遗传算法等元启发式算法

参考资料

• 题目介绍 - 完整的竞赛题目介绍
• 系统设计文档 - 详细的架构设计
• Pinedo, M. L. (2016). Scheduling: Theory, Algorithms, and Systems.

License

MIT License