任务数量较小,可以使用回溯枚举所有满足依赖关系的任务执行顺序。
核心算法是拓扑顺序枚举 + 最早可行时间调度:
每个任务用一个二进制状态表示所需的NPU卡集合。
在回溯过程中维护:
设计一个调度系统管理昇腾 NPU 上的训练任务,需满足以下条件:
用例保证存在可调度方案(不存在任务间循环依赖),输出所有任务全部完成需要的最短时间。
第 1 行,NPU 卡总数(1<=NPU卡总数<=10),总任务数量(1<=总任务数量<=8),如:4 2
第 2 行,【第 2−4 行第 0 个任务】,任务 0 依赖的 npu 列表(空格分割),如:0 1
第 3 行,【第 2−4 行第 0 个任务】,任务 0 持续时间,如:5
第 4 行,【第 2−4 行第 0 个任务】,任务 0 依赖的上游任务 ID(无依赖时固定为 −1),如:1
第 5 行,【第 5−7 行第 1 个任务】,任务 1 依赖的 npu 列表(空格分割),如:1 2
第 6 行,【第 5−7 行第 1 个任务】,任务 1 持续时间,如:4
第 7 行,【第 5−7 行第 1 个任务】,任务 1 依赖的上游任务 ID(无依赖时固定为 −1),如:0
……,如果存在更多任务,3 行一组进行输入,任务 i 依赖的 npu 列表(空格分割),如:1 2
……,如果存在更多任务,3 行一组进行输入,任务 i 持续时间,如:4
……,如果存在更多任务,3 行一组进行输入,任务 i 依赖的上游任务 ID(无依赖时固定为 −1),如:0
注意:题目保证输入合法,无需校验输入
格式:int 类型数值
解释:所有任务全部完成需要的最短时间,用例保证存在可调度方案(不存在任务间循环依赖)
输入
2 3
0
3
-1
0
2
-1
1
4
1
输出
6
说明
方案1:优先执行耗时长的任务(任务0先执行)
时间0~3 NPU0: 任务0(持续3,时间0-3) NPU1: 空闲(任务2依赖任务1,还未完成)
时间3~5 NPU0: 任务1(持续2,时间3-5) NPU1: 空闲(任务2需等待任务1,任务1在时间5完成,但任务2还未开始)
时间5~9 NPU0: 空闲 NPU1: 任务2(持续4,时间5-9)
任务完成时间: 任务0: 时间3完成 任务1: 时间5完成 任务2: 时间9完成
总时间:9
方案2:优先执行耗时短的任务(任务1先执行)
时间0~2 NPU0: 任务1(持续2,时间0-2) NPU1: 空闲(任务2依赖任务1,还未完成)
时间2~6 NPU0: 任务0(持续3,时间2-5) NPU1: 任务2(持续4,时间2-6,任务1在时间2已完成,满足依赖)
时间5~6 NPU0: 空闲(任务0已完成) NPU1: 任务2继续执行(时间5-6)
任务完成时间:
任务1: 时间2完成 任务0: 时间5完成 任务2: 时间6完成
总时间:6
输入
3 2
0 1
4
-1
1 2
5
0
输出
9
说明
调度顺序: 任务1依赖任务0,只能先执行任务0再执行任务1,总耗时4+5=9,输出9
提示 NPU 编号从 0 开始,任务编号从 O 开始