最优流水线并行切分
P5947. 最优流水线并行切分
场次:2026年10月28日-AI方向 · 来源:CodeFun2000 P5947
题目描述
将一个 层的深度神经网络按流水线并行部署到 个 GPU 上。层必须按从前往后的顺序切成恰好 段连续子序列,每段分给一个 GPU,且每段至少包含 层。
第 层的计算耗时为 ,该层输出激活对应的通信耗时为 (层号从 到 )。一段若没有覆盖到第 层,总耗时等于段内各层计算耗时之和,再加上该段最后一层的通信耗时;同一段内部的相邻层通信耗时为 。覆盖到第 层的那段没有后继层,通信耗时为 ,总耗时只计计算耗时。
请给出一种切分,使 个阶段总耗时的最大值最小,并输出这个最小值。
输入格式
共三行。
第一行是长度为 的整数序列 。
第二行是长度为 的整数序列 ,与第一行等长。
第三行是一个整数 ,表示 GPU 数量。
输出格式
输出一个整数,表示单个 GPU 最大总耗时的最小值。
数据范围
时间限制:C/C++ ms,其他语言 ms。
内存限制:C/C++ MB,其他语言 MB。
示例
示例 1
输入:
3 8
6 5
1输出:
11说明:
只有 个 GPU,两层必须放在同一阶段。计算耗时为 。两层之间没有跨 GPU 的切分,通信耗时为 ,答案是 。
示例 2
输入:
5 7 4 6 8
3 2 9 6 1
3输出:
14说明:
最优切分是 、、:
- 第 段计算耗时 ,通信耗时 ,总耗时
- 第 段计算耗时 ,通信耗时 ,总耗时
- 第 段计算耗时 ,已经覆盖最后一层,通信耗时 ,总耗时
单个 GPU 的最大总耗时为 。
另一合法切分 、、 的三段耗时分别是 、、,最大值 ,比 更差。
解题思路
先看清楚要最小化的是什么
层按原顺序切成恰好 段,每段至少一层,段与段之间不能打乱顺序。每一段交给一张卡依次算完,整条流水线的速度由最慢的那张卡决定,所以要输出的是「 段耗时的最大值」的最小可能值。
麻烦在于:一段的耗时并不等于它包含的各层计算量之和。层与层之间只在换卡的时候才通信——同一张卡上相邻的两层直接把激活递过去,耗时是 ;只有这一段的最后一层要把结果交给下一张卡,才付一次通信。换句话说,每段结尾都要做一次「交接」,而交接的价钱挂在段尾那一层的 上。
这段交接是后面所有推导的起点:一段贵不贵,不只看它有多长,还要看它结束在哪一层。
一段的耗时 = 段内计算 + 一次交接
按上面的口径,段 的代价是
最后一段之后没有下一张卡,不用交接,所以 被免掉。这一条让「末尾那段」天然比同长度的段便宜,是全题唯一与直觉相反的地方,代码里用 if i < n 把守(见「易错点」第一条)。
段内的计算量交给前缀和,一段的代价就能 算出来:
pref = [0] * (n + 1) # pref[i] = T_1 + ... + T_i
for i in range(1, n + 1):
pref[i] = pref[i - 1] + T[i - 1]
# cost(l, r) = pref[r] - pref[l - 1] + (S[r - 1] if r < n else 0)这是后面能把 DP 压到 而不是 的前提:枚举最后一段的起点时,不用再把这段重新加一遍。
贪心为什么失效:交接费会自己变小
把通信项拿掉,这题就是「分割数组的最大值」:,段越长越贵,于是可以二分答案,判定时从左往右能装就装、装不下再切,段数 即可行。
多出来的 把这一步的立足点抽掉了。从 再往后并一层,代价的变化是
前一项是加进来的计算量,后一项是交接点搬家带来的差价。 陡降的时候,差价可以是负的——并得更多反而更便宜。取 、: 单独成段的代价是 ,把第二层并进来却变成 。
于是「能装就装」这句话没有判据:第一层自己一段就已经超上限,而要不要再并一层,取决于下一层的 会不会突然变小。贪心在第一步就走不下去。
这个输入可以直接贴进运行条(答案 ,切法是 与 ):
0 0 0
100 0 0
2更隐蔽的一处:「最少段数」也不成立
既然不能贪心,那二分答案还能不能救?二分要回答的是一个判定问题:「给定上限 ,能不能切成恰好 段、每段都不超过 」。老老实实按段数做一次 DP 当然能回答,但那就等于把整道题又做了一遍;更省事的想法是只求「最少要切成几段」,再看这个数是否 。这个松懈在这里是错的。
取 、、:唯一合法的两段切法是 、,代价分别是 和 ,答案是 。而 时,整体一段 的代价是 ,最少段数 ,松懈后的判定报「可行」——二分最后就会输出 。
根子还是交接费:把一段拆成两段并不免费,前半段要多付一次交接。所以「能切 段」推不出「能切 段」,段数与可行性之间没有单调关系,夹逼失效。
同样的输入,答案是 :
0 0
100 0
2二分答案本身还活着,但绕一圈不省事
说清楚这一点,免得留下「这题不能二分」的错印象。把段代价写成
固定 后,「从 走到 」合法当且仅当 。 非降,所以合法的 恰好是一段后缀:每层做一次前缀计数,就能 判断每个 上一步有没有可落脚的点,一次判定 ,配上 轮二分是 。
这条路是通的,但和 的 DP 同量级( 时两者实测都在 秒上下),代码还更长,所以本题不走。
顺手把它收成一句能带走的判据:段代价能写成 的形式时,看 是否单调。 单调(纯前缀和)→ 贪心判定成立; 不单调(本题 )→ 判定只能自己做 DP。
把「最慢的那段」存进 DP 的值里
切法是一串切点,天然适合按段数分层:先决定第一段切到哪、第二段切到哪……于是设
:前 层切成恰好 段时,这 段耗时的最大值最小能到多少。
最后一段是 ,它前面是「前 层切 段」的子问题:
这个转移能用,靠的是「最大值」这个聚合量的性质:最后一段的耗时与前面怎么切无关,所以整体的最大值必然等于「前 段的最大值」与「最后一段」两者的较大者。状态里如果存的是总耗时,这条就不成立了——总耗时拆成两半再取大没有意义。
从 起,是因为前 段每段至少一层,至少要占掉 层; 从 起同理。边界是 ,其余 。
INF = float("inf")
prev = [INF] * (n + 1)
prev[0] = 0 # 0 层切 0 段
for k in range(1, K + 1):
cur = [INF] * (n + 1) # i < k 的格子必须保持不可达
for i in range(k, n + 1):
head = pref[i] + (S[i - 1] if i < n else 0) # cost(j+1, i) 里只跟 i 有关的那一半
best = INF
for j in range(k - 1, i):
best = min(best, max(prev[j], head - pref[j]))
cur[i] = best
prev = cur
print(prev[n])head - pref[j] 就是 :把只跟 有关的一半提到内层循环外面算一次, 次转移下能省掉一半加减法。
这套循环实际跑多少次
内层循环的次数是
时约 次转移。只保留上一层的 一行,空间是 ;答案落在最后一行第 格。
完整代码实现
import sys
INF = float("inf")
def solve():
# 输入固定三行:T 序列、S 序列、K
lines = [ln for ln in sys.stdin.buffer.read().splitlines() if ln.strip()]
if not lines:
return
T = list(map(int, lines[0].split()))
S = list(map(int, lines[1].split()))
K = int(lines[2].split()[0])
n = len(T)
# pref[i] = T_1 + ... + T_i,段 [l, r] 的计算耗时是 pref[r] - pref[l - 1]
pref = [0] * (n + 1)
for i in range(1, n + 1):
pref[i] = pref[i - 1] + T[i - 1]
# prev[i]:前 i 层恰好切成 k-1 段时的最小最大耗时
prev = [INF] * (n + 1)
prev[0] = 0 # 0 层切 0 段,只有这一格可达
for k in range(1, K + 1):
cur = [INF] * (n + 1) # 每轮新建:i < k 必须保持不可达
for i in range(k, n + 1):
# cost(j+1, i) = head - pref[j],head 只跟 i 有关
head = pref[i] + (S[i - 1] if i < n else 0)
best = INF
for j in range(k - 1, i):
best = min(best, max(prev[j], head - pref[j]))
cur[i] = best
prev = cur
print(prev[n])
if __name__ == "__main__":
solve()示例推演
示例 1:末尾那段为什么不用交接
、、、。只有一种切法 ,它盖住了最后一层,按定义不用交接:。
式子里 那一支把 跳过了。写成「段尾一律加 」的话这里会变成 ,比答案整整多出一次交接。
示例 2:三层表逐格填
、、,前缀和 。
第一层(,只剩一整段 ):
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 段 | |||||
| 计算 | 5 | 12 | 16 | 22 | 30 |
| 交接 | 末段, | ||||
| 8 | 14 | 25 | 28 | 30 |
第二层(, 从 2 起):
| 2 | — | — | — | 9 | |
| 3 | — | — | 14 | ||
| 4 | — | 16 | |||
| 5 | 18 |
拿 念一遍: 对应 与 ,前两段的最大值是 ,最后一段 ,取大得 ;另外两个 给的是 和 ,都更差。
第三层(,只剩 ):
| 前两段最优 | 最后一段 | 取大 | 对应切分 | |
|---|---|---|---|---|
| 2 | 9(、) | 18 | ||
| 3 | 14(、) | 14 | ||
| 4 | 16(、) | 16 |
最小值 ,与题面说明一致。这张表顺带解释了说明里那句「另一合法切分最大值 」:它就是 那一行,被 压住。 给出 ,代价是把后三层捆在一起—— 光计算就要 。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举全部切点 | 居中时方案数是天文数字, 完全不可算 | ||
| 二分答案 + 可达性判定 | 判定得是「恰好 步可达」,每次 ;可行,但不比下一行快 | ||
| 分层 DP + 前缀和(最优) | 转移总数 ,纯 Python 约 秒 |
「分层 DP + 前缀和」的转移数在 时取到上界:此时每个 的内层循环都要从 跑到 ,三段求和正好凑成 。空间只需前缀和、上一层与当前层各一行,;把整张 都留下会变成 ,而本题只问 ,没有回溯切分的需求,所以不必留。
易错点总结
1. 末段也加了交接费
代码里 if i < n 就是「盖住第 层的段没有后继」这条规则。把它改成无条件 + S[i - 1],样例 1 会输出 (),样例 2 会输出 ——末段 的 被抬到 ,成了新的最大值,正好压过原来那个 。
2. 滚动数组被复用成了同一个对象
为了省一次分配写 cur = prev 不行。 从小到大推进,内层读到的 prev[j] 已经是本轮的 ,等于允许在同一层里继续切,段数上限被打穿。样例 2 会输出 ——那是拆成五段 时的最大值()。它比正确答案小,看上去还挺像回事,最难发现。每轮 cur = [INF] * (n + 1) 不能省,它同时保证了 的格子( 层切 段,根本不存在)不可达。
扩展思考
- 改成「至多 段」就是另一道题。 上面 、 那个例子,恰好 段的答案是 ,允许只用 段时是 。「恰好」这两个字不是措辞:合并一段能免掉一次交接,所以切得越多不一定越好。
- 若 恒为 ,模型退化成「分割数组的最大值」,贪心判定重新成立,二分答案可以做到 (见 P5468)。
相关题目
- 流水线并行的最小峰值负载:同模型去掉通信项,贪心判定就够
- 动态规划
- 查找算法(二分答案:最小化最大值):判定式可行性的通用写法