最终成绩（官方评估口径，100 用例算术平均加速比）

问题	2 核	3 核	4 核	5 核
问题一（场景 A）	1.820	2.492	3.116	3.580
问题二（场景 B）	2.075	2.922	3.643	4.240
问题三（场景 B + L2 Cache）	2.076	2.932	3.677	4.350

全部 1200 个（用例 × 问题 × 核数）评估格经官方命令行工具逐格复放核对：1189 格数值完全一致，11 格因评估器跨进程非确定性做了微幅修正（见下文），无退化格（每格加速比 ≥ 1）。

这是一个多核 NPU 计算图调度问题的完整参赛方案：问题建模、切图与调度算法、候选搜索框架、全量评估结果，以及从 2.4 到 3.6（五核问题一加速比）的完整优化过程记录。

赛题给出 100 个计算图用例（766～38,666 个算子，总计约 70 万算子）。每个算子归属某条流水线（PIPE_M / PIPE_V），算子间通过张量传递数据，张量存放在 DDR、L1 或 UB 上。调度器需要把算子划分成若干子图并分配到 2～5 个核，最小化整体 Makespan。三个问题的差别在通信代价模型：

• 问题一（场景 A）：划分成的子图即任务，跨核任务间等待 1000 周期，同核任务间等待 100 周期；
• 问题二（场景 B）：每核合并一个大任务，跨核数据拷贝延迟 500 周期（同核拷贝免费）；
• 问题三：在问题二基础上增加一块按逻辑张量 id 索引的 1MB 只读 FIFO Cache（读带宽 250 B/cycle，命中不刷新 FIFO 序），考察调度方案能否利用数据复用。

DDR 拷贝带宽 60 B/cycle，L1 512KB，UB 128KB，由官方评估器 multicore_cut_evaluate_problem_{1,2,3}.py 按 config.txt 的固定参数模拟结算。成绩为 100 用例相对单核基线的算术平均加速比。COPY_IN / COPY_OUT 算子不参与划分，由评估器自动生成。

这个问题有两个直接的困难。其一，三个问题的通信代价模型不同，同一套切分在不同问题下的最优粒度差异很大；其二，官方评估器是逐周期事件模拟，一次评估从毫秒级（小图）到数分钟（3.9 万算子大图）不等，搜索空间必须精打细算。

计算图 JSON
   │  图模型：收缩 COPY 节点、生产/消费计数、M/V 工作量、深度与向上 rank
   ▼
切分候选族（按图规模分档组合）
   ├── 区域生长 + FM 精化 + 再均衡（带环守卫）
   ├── 深度窗口 × 连通分量条带（bandcomp，天然无环）
   └── 结构候选：波前条带 / 宽图分摊 / fork-join 模板
   │
   ▼
通信感知列表调度（HEFT 简化，区分场景 A/B 代价）
   │
   ▼
官方评估器实测 → 逐格取最小 Makespan（单核方案兜底）

图模型把原始图收缩成"合格算子"视图：COPY 节点被收缩进边，直接 op→op 依赖保留为零字节边；每算子记 M / V 两条流水的工作量、输入张量的生产者集合；每个切分簇记 M / V 双维负载。所有合法性判断（任务图无环、同核顺序）使用收缩后的完整依赖，而不是只看有张量的边——零字节边同样能构成任务环，这一点曾让我们在官方校验上栽过跟头。

基础方法是通信收益驱动的区域生长：种子取剩余向上工作量最大的算子，邻居按"并入收益 / 工作量"入堆，簇负载到达目标额即止，之后 FM 精化在簇间搬动算子改善切边，再均衡步骤修正负载倾斜。变体包括按边条数计权（小图上跨核同步延迟主导时更准）、M/V 双维均衡等。

这里有个值得一提的教训。链状、弱连通的图上，生长沿一条链推进，链走完时堆空了，算法把"前沿耗尽"当成"该簇已满"，剩下 98% 的算子全部落入按通信就近吸收的兜底逻辑——既破坏了均衡，又把大张量撕成跨核拷贝。某个并行度 157 的宽图因此在全核数上加速比卡在 1.0。修复方式是前沿耗尽且未达目标额时换新种子继续装填（补种），旧行为作为独立候选保留，因为部分图上散射加精化反而更好。这一处修复让 92 个原先生效单核保底的格转为真正的多核方案。

深而稀疏的图（深度数百、层内大量互不连通的分量）上，区域生长补种后簇会交错成环，只能回退到按深度横切——横切天然串行，等于放弃并行。bandcomp 换了个构造：按深度切窗口，窗内取弱连通分量。分量之间无边（定义保证），窗口之间的边只会从浅指向深，任务图因此天然无环，不需要任何环修复。分量按 max(M, V) 工作量做 LPT 装核，并带前驱粘性（优先跟随前驱分量所在核，减少跨核等待），再叠加 FM 精化压缩窗口边界的切分流量。窗口宽度与粘性系数经过全网格扫描（宽度 2～32，粘性 0.25～2.0），不同规模的图甜点不同。在最终结果里，1200 格中 849 格（70.8%）由这一族方案胜出（另有 59 格经跨问题交叉评估采纳，方案同源）。

对特定形态的图配了三个结构候选：深依赖宽波前图用波前条带（同层按 M/V 双维均衡切 lane）；并行度远超核数的宽图用强制分摊；重复 fork-join 结构用阶段模板。它们只在触发形态条件的图上加入候选集。

列表调度按"向上 rank（含通信）"定优先级，逐任务选最早完工的核，同核前驱 +100 周期、跨核 +1000（场景 A）或 +500 拷贝延迟（场景 B）。每个格的候选集按图规模分档（小图全档扫描、大图收缩到验证过的组合），全部经官方评估器实测取最小 Makespan；任何候选劣于单核基线即回退合法单核方案，保证全部格加速比 ≥ 1。

三个问题共用同一方案格式，因此每个问题的赢家方案可以直接拿到其他问题的评估器下免费重评。六个方向 × 400 格的全量交叉采纳了 59 个格——问题一的不少弱格直接受益于问题二代价模型下长出的条带分区。

1200 格（100 用例 × 3 问题 × 4 核数）的逐格指标、汇总统计与核对口径，见 results/BENCHMARK_1200.md。

最终 1200 格全部经官方 CLI 独立进程复放（每格留档输入、输出 JSON）：

• 1189 / 1200 与评测记录完全一致；
• 11 格出现偏差。排查结论：P2/P3 评估器存在跨进程非确定性——同一方案在不同独立进程中的 Makespan 与新增搬运量会有微差（同一进程内完全确定；本地的 PYTHONHASHSEED 扫描排除了散列种子因素，为 Linux Python 3.8 的运行间行为）。11 格偏差为 0.1%～1.6%（单次复放相对评测记录的观测，非多次采样统计），修正口径为 CLI 存档值，即提交的方案与成绩互相印证的那一份；
• 对外引用成绩时建议按 ±0.5% 理解典型复跑波动，极端情形可达 1.6%。

复评全量 1200 格合计 2.8 小时（平均 8.3 秒/格，最慢单格 183 秒），64 核机器 44 并发约 40 分钟。六轮批量优化在服务器端累计约 17 小时。

问题二 / 问题三五核同期从 2.600 / — 提升到 4.240 / 4.350。逐轮的完整记录（包括失败的方向：缓存亲和分核、spill 因果假设、路径分区、P1 链合并等）见 docs/OPTIMIZATION_NOTES.md——负结果同样是这份文档的一部分。

├── README.md                 本文件
├── LICENSE
├── src/                      求解代码（仅标准库）
│   ├── scheduler.py          图模型 / 区域生长 / FM 精化 / bandcomp / 列表调度
│   ├── structural_scheduler.py  结构候选（波前、宽图、fork-join）
│   ├── run_experiments.py    候选集构建、评估循环、结果落盘
│   ├── make_report.py        报告与图表
│   ├── sync_cross_v36.py     跨问题交叉评估
│   └── audit_worker.py       官方 CLI 逐格复放审计
├── tests/                    15 项回归测试（切分合法性、环守卫、条带契约）
├── results/
│   ├── BENCHMARK_1200.md     1200 格结果说明（指标口径、汇总统计、方法分布）
│   ├── best_plans/           1200 格最优方案（配合官方附件可直接复跑成绩）
│   ├── audit/                官方 CLI 复放审计汇总
│   ├── audit_summary.json    审计核对汇总（1189 一致 / 11 修正 / 0 错误）
│   └── report/               逐用例结果 CSV、加速比曲线、方法贡献统计
└── docs/
    ├── README_SOLUTION.md    算法与复现说明（论文表述框架）
    └── OPTIMIZATION_NOTES.md 方法演进与负结果记录

赛题附件（data/case_*.json 计算图与 code/multicore_cut_evaluate_problem_*.py 官方评估器）请从竞赛官方渠道获取，放到与 src/ 平级的 data/ 与 code/ 目录后：

# 1) 全量实验：生成候选 -> 官方评估器打分 -> 逐格择优
#    （支持断点续跑，小图秒级、3.9 万算子大图单格可达数十分钟）
python src/run_experiments.py --full
# 2) 汇总为逐格明细 CSV 与图表
python src/make_report.py
# 3) 校验结果（覆盖 1200 格与数值一致性，默认严格）
python src/validate_results.py
# 4) 回归测试（15 项）
python -m unittest discover -s tests
# 5) 官方 CLI 逐格复放审计：核对仓库提交的 1200 个方案
#    （单格 0.5 秒~3 分钟，全量约 2.8 小时；结果与 audit_summary.json 对照）
python src/run_audit.py --jobs 8

数据流：run_experiments.py 逐格写入最优方案与指标 → make_report.py 汇总为 all_results.csv → validate_results.py 以该 CSV 为单一数据源做覆盖与一致性校验 → run_audit.py 用官方 CLI 独立进程复核每格。仓库 results/best_plans/ 提交了全部 1200 个最优方案，因此第 6 步不需要重跑搜索即可独立复核我们的成绩。

注意评估器的运行间非确定性：同一方案在独立进程中重复评估，P2/P3 的 Makespan 可能出现 0.1%～1.6% 的漂移，对比实验时应固定进程内评估或取多次中位。

求解代码与文档以 MIT 许可发布。赛题附件（计算图用例、官方评估器、config.txt）版权归竞赛主办方所有，本仓库不收录。