Work–Depth 模型

Computation DAG ​

把一次确定的并行执行展开成有向无环图公理库有向无环图Directed acyclic graph · DAG不含有向环的有向图。 $G=(V,E)$。每个节点是一个单位时间原子任务；边 $u\to v$ 表示 $v$ 必须等待 $u$ 完成。入度为零的未执行节点是 ready tasks，调度器只能从它们中选择。

总工作与深度定义为

$$W=|V|,D=\underset{\pi \text{ is a directed path}}{max}|\pi |.$$

若节点有权重 $c(v)$，则 $W=\sum _{v}c(v)$，$D$ 是最大路径权重和；或把整数权重节点展开成任务链。混用“节点数 work”和“带权 span”会破坏调度不等式。

与 $T_1,T_{\mathrm{\infty }},T_P$ 的关系 ​

在单位成本、忽略调度开销时，单处理器必须执行全部节点，所以 $T_1=W$；无限处理器每轮执行所有 ready tasks，时间等于关键路径 $T_{\mathrm{\infty }}=D$。任意 $P$ 处理器调度满足

$$T_P\ge max\{\frac{W}{P},D\}.$$

比值 $W/D$ 称为 average parallelism。它表示整个 DAG 可供利用的平均并行度，不是每一轮都恰有这么多 ready tasks，也不是超过该处理器数后绝无任何加速。

八叶归约的层次状态 ​

八个输入各先产生一个叶任务，然后两两合并。若只计七个加法节点，三层 ready 集大小依次为 4、2、1：work 为 7，depth 为 3，平均并行度 $7/3$。若把读入八个叶值也算单位任务，则 work 为 15、depth 为 4；两种账本都可用，但必须从头到尾一致。

在 $P=2$ 时，第一层 4 个加法需两轮，第二层 2 个加法一轮，根一轮，共 4 轮；下界是 $max(7/2,3)=3.5$，取整后 4，恰好达到。$P=8$ 也只能用 3 轮，因为关键路径不变。

组合规则 ​

两个 DAG 顺序组合、第二个必须等第一个全部结束时，

$$W=W_1+W_2,D=D_1+D_2.$$

若二者完全独立并行启动，则

$$W=W_1+W_2,D=max(D_1,D_2).$$

Fork–join 程序常同时包含两种组合。一个循环体可并行不代表下一阶段与它独立；漏画 barrier 或数据依赖会人为缩短 span。反过来，加入不必要的全局 barrier 会让 DAG 比算法真正依赖更深。

Work efficiency 与 slackness ​

若 $W$ 与最佳串行算法时间同阶，算法 work-efficient。若为了把 $D$ 降到常数而做 $n^2$ 个比较，即使无限处理器很快，也可能在现实 $P$ 下输给 $O(n\log n)$ work 的算法。

当 $P\ll W/D$ 时，容量项 $W/P$ 通常主导，存在充分 parallel slackness；当 $P\gg W/D$ 时，关键路径主导，增加处理器收益很小。Brent 调度定理公理库Brent 调度定理Brent scheduling theorem · Brent's theorem · work-depth scheduling principle把 work 为 W、depth 为 D 的单位任务 DAG 贪心映射到 P 个处理器，得到 W/P+D 级时间上界。把这一直觉变成贪心调度上界。

随机 DAG 与量词 ​

若算法随机性决定分支或任务数量，$W,D$ 是随机变量。可以证明 $\mathbb{E}[T_P]$，也可以分别给 $W,D$ 的高概率界后取联合事件；不能从 $\mathbb{E}[W]$ 与 $\mathbb{E}[D]$ 直接推出所有执行都满足同一时间界。

调度器随机性与算法随机性也应分开。工作窃取公理库工作窃取调度work stealing scheduler · randomized work stealing让工作线程从本地双端队列执行任务，空闲线程随机窃取较老任务，以期望开销实现动态负载均衡。的期望界通常固定一棵 fully strict computation DAG，再对随机受害者选择取期望。

模型边界 ​

Work–Depth DAG 表达控制与数据依赖，却不自动计通信、cache miss、内存容量或写冲突。两个节点没有依赖边，只说明语义上可并行，不保证它们访问内存时没有带宽竞争。

Depth 有时也指 PRAM 同步轮数；span 更强调关键路径。页面可把 $D=T_{\mathrm{\infty }}$ 作为同义约定，但不能把实际 $T_P$ 也叫 depth。处理器数 $P$ 必须在调度阶段进入，而不是藏进 $D$。

参考资料

• Guy Blelloch, Prefix Sums and Their Applications, CMU Technical Report, 1990.
• Robert Blumofe, Charles Leiserson, Scheduling Multithreaded Computations by Work Stealing, Journal of the ACM, 1999.
• Thomas Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, multithreaded algorithms.