并行计算中的协同效应与算法应用

### 并行计算中的协同效应与算法应用 #### 1. 并行计算的核心理论 在并行计算的理论和实践中，有一个核心观点：若在给定模型下，某计算用 $p$ 个处理器需 $t_p$ 时间完成，用 $q$ 个处理器（$q < p$）需 $t_q$ 时间完成，那么对于正常数 $\alpha \geq 1$，有 $1 \leq \frac{t_q}{t_p} \leq \alpha \frac{p}{q}$。 这一观点对增加处理器数量解决问题的效果以及减少处理器数量时算法的性能都进行了限制。当 $q = 1$ 时，有 $\frac{t_1}{t_p} \leq \alpha p$，这就是“加速定理”，意味着用 $p$ 个处理器解决顺序执行需 $t_1$ 时间的问题时，并行时间 $t_p$ 最多比 $t_1$ 小 $p$ 倍。反之，当处理器数量从 $p$ 减至 $q$（$1 < q < p$）时，就是“减速定理”，即 $p$ 个处理器解决问题的时间 $t_p$，在使用 $q$ 个处理器时最多减少 $p/q$ 倍。 不过，很多日常例子和实际情况都与这些“定理”相悖。如很多任务一个人完成需 $t_1$ 时间，$p$ 个人完成可能只需 $t_p$ 时间，且 $t_p$ 远小于 $\frac{t_1}{p}$；而 $\frac{p}{2}$ 个人完成任务的时间 $t_{p/2}$ 会远大于 $2t_p$，大型建筑工作就是很好的例证。 #### 2. 并行协同效应 对于一大类计算问题，$\frac{t_q}{t_p} \leq \alpha \frac{p}{q}$（$q < p$）这一说法并不成立，存在一种计算现象叫并行协同效应：在给定模型下，存在用 $p$ 个处理器需 $t_p$ 时间完成的计算，以及用 $q$ 个处理器（$q < p$）需 $t_q$ 时间完成的相同计算，且 $\frac{t_q}{t_p}$ 渐近大于 $\frac{p}{q}$。 当并行协同效应起作用时，$p$ 个处理器执行计算的速度渐近快于 $\frac{t_1}{p}$，即运行时间减少的倍数大于使用的处理器数量；而 $q$ 个处理器（$1 < q < p$）执行此类计算的速度渐近慢于 $\frac{pt_p}{q}$，意味着未充分使用并行性时，运行时间增加的倍数大于处理器数量的比例。这里“渐近”表示 $\frac{\frac{t_q}{t_p}}{\frac{p}{q}}$ 不是常数。 并行协同效应在非传统计算中较为常见，比如时间相关的应用，计算机实时接收输入并需在特定截止日期前输出结果；或者输入随时间变化、输出影响后续输入的应用。以下通过几个例子来说明。 ##### 2.1 独立输入流 假设计算机接收 $n$ 个独立且同时的数据流作为输入，每个流的形式为 $< V_1, V_2, \cdots, V_n >$，是序列 $X = (X_1, X_2, \cdots, X_n)$ 的不同循环排列。例如，当 $n = 5$ 时，有五个输入流：$< X_1, X_2, X_3, X_4, X_5 >$、$< X_5, X_1, X_2, X_3, X_4 >$、$< X_4, X_5, X_1, X_2, X_3 >$、$< X_3, X_4, X_5, X_1, X_2 >$ 和 $< X_2, X_3, X_4, X_5, X_1 >$。每个流中，$V_{i + 1}$ 在 $V_i$ 之后 $n$ 个时间单位到达，接收一个值需一个时间单位。 - **顺序计算机情况**：单个处理器只能监控一个流。因为处理器读取并存储所选流的第一个值时，其他流同时到达的剩余 $n - 1$ 个值已来不及处理。若要找出 $X$ 中的最小值，处理器依次读取所选流的值，记录当前最小值，处理 $n$ 个