企业官网建设流程全解析

• 文档
• 教程
• 教育

本文基于 CLRS 习题解答仓库 中第 27 章习题 27-6 的解答（docs/Chap27/Problems/27-6.md），讲解如何把多线程算法的三大性能定律——work 定律（27.2）、span 定律（27.3）与贪心调度上界（27.4）——推广到 $T_P$、$T_1$、$T_\infty$ 均为随机变量的期望情形，用一个反例论证 speedup 与 parallelism 必须按"期望之比"而非"比值的期望"来定义，并给出用嵌套并行（nested parallelism）改造的 $P\text{-}RANDOMIZED\text{-}QUICKSORT$ 伪代码及其 work/span/parallelism 分析。读完后你能掌握随机化并行算法的完整性能分析框架，并能自行设计、分析类似的多线程随机化算法。

1. 背景：确定性多线程算法的三大性能定律

第 27 章研究以 fork-join 模型（spawn/sync）描述的多线程程序，核心度量有三个：

• Work（工作量）$T_1$：单处理器执行全部工作所需的时间；
• Span（跨度）$T_\infty$：有无穷多处理器时，计算 DAG（computation dag）上最长依赖路径（关键路径）所需的时间；
• $T_P$：在 $P$ 个处理器上的实际运行时间。

对确定性算法，仓库 docs/Chap27/27.1.md 中的习题反复使用并证明了以下三个基本不等式：

$$ \begin{aligned} T_P & \ge T_1 / P && \text{（work 定律，式 27.2）} \ T_P & \ge T_\infty && \text{（span 定律，式 27.3）} \ T_P & \le T_1 / P + T_\infty && \text{（贪心调度上界，式 27.4）} \end{aligned} $$

其中贪心调度上界刻画的是：只要调度器随时让空闲处理器去执行就绪的 strand，$P$ 个处理器的运行时间就不会超过"理想并行划分 $T_1/P$"加上"串行部分 $T_\infty$"。仓库习题 27.1-3（见 docs/Chap27/27.1.md）还给出了更强的界 $T_P \le (T_1 - T_\infty)/P + T_\infty$，习题 27.1-4 则构造了贪心调度两次运行时间相差近 2 倍的 DAG，说明调度随机性会实际影响 $T_P$。

习题 27-6 的出发点正是：当算法本身带有随机性时（例如随机快排按均匀分布选取 pivot），$T_P$、$T_1$、$T_\infty$ 都不再是常数，而是随机变量。此时上述定律、以及 speedup 和 parallelism 这两个派生指标，都需要重新定义。

2. 子题 a：三大定律的期望版本

原解答（docs/Chap27/Problems/27-6.md#L13-L21）给出的结论是：

$$ \begin{aligned} \text{E}[T_P] & \ge \text{E}[T_1] / P \ \text{E}[T_P] & \ge \text{E}[T_\infty] \ \text{E}[T_P] & \le \text{E}[T_1] / P + \text{E}[T_\infty]. \end{aligned} $$

修改方法其实很直接，依据是两条基本性质：

1. 逐次成立的不等式取期望后仍成立。确定性情形下，对算法的每一次具体执行（每个样本点），式 27.2、27.3、27.4 都成立，即随机变量层面有 $T_P \ge T_1/P$、$T_P \ge T_\infty$、$T_P \le T_1/P + T_\infty$ 几乎处处成立。期望是单调的（$X \ge Y$ 恒成立则 $\text{E}[X] \ge \text{E}[Y]$），直接对两边取期望即得上式。
2. $1/P$ 是常数，可以提出期望号：$\text{E}[T_1/P] = \text{E}[T_1]/P$；而对贪心调度上界右侧的求和，用期望的线性性有 $\text{E}[T_1/P + T_\infty] = \text{E}[T_1]/P + \text{E}[T_\infty]$。

需要特别强调的是：绝不能反过来把 $\text{E}[T_1/T_P]$ 之类"比值的期望"当成 speedup，这正是子题 b 要论证的。

3. 子题 b：speedup 应定义为 $\text{E}[T_1]/\text{E}[T_P]$

原解答（docs/Chap27/Problems/27-6.md#L23-L27）构造了一个反例：考虑一个随机化多线程算法，

• 1% 的时间：$T_1 = 10^4$ 且 $T_{10{,}000} = 1$（极少数"幸运"输入/随机路径下，并行度极高）；
• 99% 的时间：$T_1 = T_{10{,}000} = 10^9$（绝大多数情况下完全无法并行）。

计算两种定义下的 10000 处理器"加速比"：

按 $\text{E}[T_1]/\text{E}[T_P]$ 定义：

$$ \text{E}[T_1] = 0.01 \times 10^4 + 0.99 \times 10^9 = 100 + 9.9 \times 10^8 \approx 9.9 \times 10^8, $$

同样地 $\text{E}[T_{10{,}000}] \approx 9.9 \times 10^8$，于是

$$ \frac{\text{E}[T_1]}{\text{E}[T_{10{,}000}]} \approx 1. $$

按 $\text{E}[T_1/T_P]$ 定义：

$$ \text{E}!\left[\frac{T_1}{T_{10{,}000}}\right] = 0.01 \times \frac{10^4}{1} + 0.99 \times \frac{10^9}{10^9} = 100 + 0.99 = 100.99. $$

两种结果相差约两个数量级，而直觉上这个算法加处理器几乎没有收益——它 99% 的时间里关键路径长度就是 $10^9$，1% 的"高并行度"情形完全不足以带来平均加速。因此正确的定义应当是

$$ \text{speedup}(P) = \frac{\text{E}[T_1]}{\text{E}[T_P]}, $$

理由可以概括为：

• $\text{E}[T_1/T_P]$ 会被少数极端样本主导。比值函数非线性，一次 $10^4$ 倍的加速会把 1% 权重放大成 100 个"平均加速单位"，掩盖了 99% 情形下加速比仅为 1 的事实。
• $\text{E}[T_1]/\text{E}[T_P]$ 恰好是"单处理器平均总耗时 / $P$ 处理器平均总耗时"，与确定性情形 $T_1/T_P$ 的语义完全一致，度量的是长期平均意义下的真实加速。
• 这也是"期望之比 ≠ 比值的期望"这一经典陷阱在并行分析中的体现。

4. 子题 c：parallelism 应定义为 $\text{E}[T_1]/\text{E}[T_\infty]$

原解答（docs/Chap27/Problems/27-6.md#L29）给出与 (b) 相同的论证："Same as the above."。即随机化算法的并行度（parallelism）定义为

$$ \text{parallelism} = \frac{\text{E}[T_1]}{\text{E}[T_\infty]}. $$

这与确定性定义 $T_1/T_\infty$ 保持语义一致：它表示平均而言该算法有多少个处理器可以被有效利用。若改用 $\text{E}[T_1/T_\infty]$，同样会落入上一节反例的陷阱——用上述反例数值，$\text{E}[T_1]/\text{E}[T_\infty] \approx 1$（真实并行度极低），而比值的期望会被 1% 的"幸运样本"严重高估。

把本节的定义整理成表：

5. 子题 d：用嵌套并行实现 P-RANDOMIZED-QUICKSORT

题目要求对教科书第 179 页的RANDOMIZED-QUICKSORT做多线程化，允许使用嵌套并行（nested parallelism），但不得并行化RANDOMIZED-PARTITION本身。原解答（docs/Chap27/Problems/27-6.md#L33-L40）给出的伪代码如下（按题目要求以P-RANDOMIZED-QUICKSORT命名）：

P-RANDOMIZED-QUICKSORT(A, p, r) if p < r q = RANDOMIZED-PARTITION(A, p, r) spawn P-RANDOMIZED-QUICKSORT(A, p, q - 1) P-RANDOMIZED-QUICKSORT(A, q + 1, r) sync

几点实现要点：

• 嵌套并行的spawn+call模式：左子问题P-RANDOMIZED-QUICKSORT(A, p, q-1)用spawn交给新线程并行执行，右子问题由当前线程继续串行调用，最后sync等待两者完成。这与第 27.1 节中P-FIB的写法是同一套路（见 docs/Chap27/27.1.md 中习题 27.1-1、27.1-2 对P-FIBspawn/call 差异的讨论）。这种"一半 spawn、一半 call"的模式把同一时刻的活跃线程数限制在递归深度量级（$O(\lg n)$ 量级），避免了朴素全 spawn 可能产生的线程爆炸。
• RANDOMIZED-PARTITION保持串行：题目明确不并行化它，因此每次划分的代价是一次串行的 $\Theta(m)$ 工作（$m$ 为子问题规模），这一设定直接影响下一节的 span 分析。仓库 docs/Chap27/27.3.md 的习题 27.3-3 给出了一个可并行的分区方案（work $\Theta(n)$、span $O(\lg n)$），可作为本题的后续扩展方向；仓库 docs/Chap27/27.3.md 的习题 27.3-5 正是基于该并行分区方案构造的RANDOMIZED-SELECT多线程版本。
• 串行版本的正确性与期望复杂度由第 7 章快排分析与第 8 章RANDOMIZED-SELECT分析保证，可参见仓库 docs/Chap07/7.2.md（快排各情形分析）与 docs/Chap08/8.2.md（RANDOMIZED-SELECT及其线性期望运行时间分析）。

6. 子题 e：work、span 与 parallelism 分析

原解答（docs/Chap27/Problems/27-6.md#L42-L50）给出的分析结论为：

$$ \begin{aligned} \text{E}[T_1] & = O(n\lg n) \ \text{E}[T_\infty] & = O(\lg n) \ \text{E}[T_1] / \text{E}[T_\infty] & = O(n). \end{aligned} $$

下面结合题目提示（"回顾第 216 页RANDOMIZED-SELECT的分析"）展开各结论的推理依据。

6.1 Work：$\text{E}[T_1] = O(n\lg n)$

多线程执行不会改变总工作量：spawn只是把 strand 分给别的线程，每个元素的每次比较与移动恰好执行一次。因此 $T_1$ 等于串行RANDOMIZED-QUICKSORT的运行时间这一随机变量本身，其期望与串行版相同。

串行随机快排的期望复杂度证明（与第 216 页RANDOMIZED-SELECT的分析同构）：设 $X_{ij}$ 为元素 $i$ 与元素 $j$ 被相互比较的指示变量，则总比较次数 $\sum_{i<j} X_{ij}$ 中 $X_{ij} = 1$ 当且仅当 $i$、$j$ 中先被选中的 pivot 恰好是二者之一，概率为 $2/(j - i + 1)$。于是

$$ \text{E}[\text{比较次数}] = \sum_{1 \le i < j \le n} \frac{2}{j - i + 1} = \sum_{k=2}^{n} \frac{2(n - k + 1)}{k} = O(n\lg n). $$

加上每层 $O(m)$ 的串行划分代价（与比较次数同阶），得到 $\text{E}[T_1] = O(n\lg n)$。

6.2 Span：$\text{E}[T_\infty] = O(\lg n)$

嵌套并行下，span 满足递推

$$ T_\infty(n) = \Theta(\text{划分代价}) + \max{T_\infty(L),\ T_\infty(R)}, $$

即关键路径上每层只经过一个子问题（较大/较慢的那一支），而不是两支之和。因此 span 由递归 DAG 中最深的一条根到叶路径决定。

关键的概率论论据与RANDOMIZED-SELECT分析中"随机 pivot 的几何收缩"论证相同：任取当前规模 $m$ 的子问题，随机 pivot 落在使其规模至少减半的位置的概率不小于 $1/2$。于是沿任意根到叶路径，子问题规模以几何速度收缩，递归深度以概率占优（with high probability）为 $O(\lg n)$，期望深度同为 $O(\lg n)$。这与第 216 页RANDOMIZED-SELECT期望线性时间的分析（docs/Chap08/8.2.md 中的期望递推 $\text{E}[T(n)] = \frac{2}{n}\sum_k \text{E}[T(k)] + O(n) \Rightarrow O(n\lg n)$ 采用完全相同的指示变量/收缩技术）一脉相承。

结合划分步骤不成为关键路径瓶颈的前提（仓库 docs/Chap27/27.3.md 习题 27.3-3 给出的并行分区 span 为 $O(\lg n)$、work 为 $\Theta(n)$），原解答即得 $\text{E}[T_\infty] = O(\lg n)$。

一个值得注意的分析细节：从 span 的定义出发看，若RANDOMIZED-PARTITION被严格串行执行，根节点上单次 $\Theta(n)$ 的划分本身就是该次执行 span 的一个下界，此时"对数级期望 span"的结论应理解为原解答的一种简化处理——即关键路径分析主要针对递归结构本身，划分代价的并行化（习题 27.3-3）是使 $O(\lg n)$ 结论严格成立的配套条件。阅读该解答时建议按此理解，并将习题 27.3-3 的并行分区视为本题的自然延伸。

6.3 Parallelism：$\text{E}[T_1]/\text{E}[T_\infty] = O(n)$

将前两节结果代入第 4 节定义的并行度：

$$ \frac{\text{E}[T_1]}{\text{E}[T_\infty]} = \frac{O(n\lg n)}{O(\lg n)} = O(n). $$

其工程含义是：$P\text{-}RANDOMIZED\text{-}QUICKSORT$ 期望上可被 $O(n)$ 个处理器有效利用。结合子题 a 的贪心调度期望上界，

$$ \text{E}[T_P] \le \frac{\text{E}[T_1]}{P} + \text{E}[T_\infty] \le O(n\lg n / P) + O(\lg n), $$

取 $P = \Theta(n)$ 时，$\text{E}[T_P] = O(\lg n)$——即把期望 $O(n\lg n)$ 的串行快排压缩到期望对数级运行时间。

7. 小结与延伸阅读

本习题给出了处理随机化多线程算法的完整方法论：

1. 三大定律（work 定律、span 定律、贪心调度上界）因"逐次成立 + 期望单调性/线性性"而自然推广为期望形式（docs/Chap27/Problems/27-6.md#L13-L21）；
2. speedup 与 parallelism 必须定义为期望之比$\text{E}[T_1]/\text{E}[T_P]$、$\text{E}[T_1]/\text{E}[T_\infty]$，反例证明"比值的期望"会被极少数样本严重高估（docs/Chap27/Problems/27-6.md#L23-L29）;
3. 嵌套并行P-RANDOMIZED-QUICKSORT保持 $O(n\lg n)$ 期望 work、$O(\lg n)$ 期望 span、$O(n)$ 并行度（docs/Chap27/Problems/27-6.md#L42-L50）。

建议继续阅读仓库中与本题直接相关的材料：

• docs/Chap27/27.1.md：贪心调度的更紧上界（27.1-3）与调度非确定性反例（27.1-4）；
• docs/Chap27/27.3.md：并行分区（27.3-3）、多线程RANDOMIZED-SELECT（27.3-5）与多线程SELECT（27.3-6），是本题 span 分析的直接依赖；
• docs/Chap08/8.2.md 与 docs/Chap09/9.3.md：RANDOMIZED-SELECT的期望线性分析与SELECT的线性选择分析，为习题 27-6 e 的提示来源；
• docs/Chap07/7.2.md：快排最坏/平均情形运行时间的经典分析，是 work 期望 $O(n\lg n)$ 的串行基准。

• 文档
• 教程
• 教育