Work–Depth 模型

Work 统计所有必须完成的任务，depth 统计任何调度都绕不过的最长依赖链。前者限制有限处理器的总吞吐，后者限制无限处理器的最快时间；二者分开后，平均并行度 $W/D$ 才能说明增加处理器在哪个区间仍有收益。

八叶归约的层次状态 ​

八个输入各先产生一个叶任务，然后两两合并。若只计七个加法节点，三层 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 顺序组合、第二个必须等第一个全部结束时，

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

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$。