Brent 调度定理

定理 ​

把计算固定为带 precedence 边的有向无环图：每个节点恰耗一个离散时间步，总节点数即 work $W$，最长依赖链的节点数即 span $D$。给定 $P\ge 1$ 个相同处理器，贪心（list）调度器公理库贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。每步从全部 ready nodes 中任取至多 $P$ 个并行执行，并在 ready nodes 不足 $P$ 时全部执行。模型忽略通信、同步、任务创建、迁移和调度本身的开销。在这些假设下，完成时间满足

$$T_P\le \lfloor \frac{W-D}{P}\rfloor +D$$

的一种常见精细版本成立；忽略取整可写成

$$T_P\le \frac{W}{P}+D.$$

结合容量与关键路径下界，得到

$$max\{W/P,D\}\le T_P\le W/P+D,$$

所以这个单位时间 DAG 模型中的贪心调度在常数因子内最优。

满轮与非满轮证明 ​

把调度轮分为两类。满轮执行恰好 $P$ 个任务；其数量至多 $W/P$，因为每个任务只执行一次。非满轮开始时 ready tasks 少于 $P$，贪心调度会把它们全部执行。

在一个非满轮中，任取剩余 DAG 的最长路径，它的第一个节点必然 ready，因此本轮会被执行。轮末所有剩余最长路径至少失去首节点，剩余 depth 严格下降 1。初始 depth 为 $D$，所以非满轮至多 $D$ 个。

两类相加给 $T_P\le W/P+D$。更精细地，每个非满轮至少执行关键路径上的一个任务，把其中 $D$ 个任务从满轮的工作账本扣除，可得到 $(W-D)/P+D$ 及相应取整形式。

一个分层 DAG 的调度轨迹 ​

设五个依赖层的 ready 数量依次为 8、6、4、3、2，且后一层必须等前一层全部完成。取 $P=4$：各层分别用 2、2、1、1、1 轮，总时间 7；work 为 23，depth 为 5。

定理给

$$T_4\le 23/4+5<11,$$

而通用下界为 $max(23/4,5)=23/4$。上界不要求每层均匀，也不声称等号；这个实例的层 barrier 使实际 7 轮落在上下界之间。

处理器区间与 work efficiency ​

若 $P\le W/D$，则 $W/P\ge D$，从而

$$T_P\le 2W/P.$$

此时增加处理器可近似线性加速。若 $P>W/D$，span 项主导，继续加处理器无法越过 $D$；$W/D$ 因而是算法的平均并行度门槛。

定理不会修复超线性 work。若并行算法 $W=n^2,D=\log n$，它在很多处理器上可能很快，却不如 work 为 $n\log n$ 的串行基线节省总资源。

Scan 的代入例子 ​

work-efficient 的并行 scan公理库并行前缀扫描parallel prefix scan · parallel scan · prefix computation用上扫归约和下扫传播在线性工作、对数深度内计算任意幺半群运算的全部前缀。有 $W=\mathrm{\Theta }(n)$、$D=\mathrm{\Theta }(\log n)$。Brent 定理给

$$T_P=O(n/P+\log n).$$

当 $P\le n/\log n$ 时近似为 $O(n/P)$；当 $P$ 更大，树形依赖的对数 span 成为瓶颈。这个结论来自 DAG 调度，不是把无限处理器时间简单除以 $P$。

适用条件 ​

定理开头的模型假设不能从公式中省去。带权任务可拆成单位链或使用加权版本，但不可抢占任务会引入额外最大任务长度项。

共享内存冲突、通信、任务创建和同步开销均未计入。现实调度器若无法发现所有 ready tasks，或因局部队列让处理器空闲，就不自动达到此上界；工作窃取公理库工作窃取调度work stealing scheduler · randomized work stealing让工作线程从本地双端队列执行任务，空闲线程随机窃取较老任务，以期望开销实现动态负载均衡。需要独立的随机分析。

保证类型与消歧 ​

Brent 定理是给定 DAG 的确定性存在/贪心上界，不是期望界。若 DAG 本身由随机算法生成，可以对每个实现分别应用，再对 $W,D$ 的分布取期望或高概率事件。

有些文献把它称 work–time scheduling principle，符号用 $T_1,T_{\mathrm{\infty }}$：

$$T_P\le T_1/P+T_{\mathrm{\infty }}.$$

这里 $T_1=W,T_{\mathrm{\infty }}=D$ 依赖单位成本约定，不能把实际测得的单线程时间与抽象 work 任意混配。

参考资料

• Richard Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM, 1974.
• Guy Blelloch, Bruce Maggs, Parallel Algorithms, in Algorithms and Theory of Computation Handbook, 2010.
• Thomas Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, multithreaded scheduling.