非常规计算中的并行处理：突破传统认知

### 非常规计算中的并行处理：突破传统认知 #### 1. 引言 在众多非常规计算问题中，并行处理发挥着至关重要的作用。为了更清晰地探讨，我们采用两种计算模型：顺序计算模型和并行计算模型。 顺序计算模型为随机访问机器（RAM），它由单个处理器 \(p_1\) 构成，可访问存储程序和数据的内存，处理器还拥有一些本地存储寄存器，用于实现顺序算法。RAM 算法的每一步都在恒定时间（定义为一个时间单位）内完成，包含以下三个阶段： - **读取阶段（READ）**：处理器从内存的任意位置读取数据到其寄存器之一。 - **计算阶段（COMPUTE）**：处理器对其一个或两个寄存器的内容执行基本算术或逻辑运算。 - **写入阶段（WRITE）**：处理器将一个寄存器的内容写入内存的任意位置。 并行计算模型是并行随机访问机器（PRAM），它配备 \(n\) 个处理器 \(p_1, p_2, \ldots, p_n\)（\(n \geq 2\)），用于实现并行算法。这些处理器共享一个存储数据的公共内存，可进行读写操作。在程序的控制下，处理器同步运行，每个处理器在其本地寄存器中都有一份程序副本。必要时，处理器可同时访问公共内存中的同一位置进行读取（并发读取，CR）或写入（并发写入，CW）。为解决多个处理器同时写入同一内存位置的冲突，PRAM 有多种解决方式，其指令集包含如 MIN CW（选择多个值中的最小值）、AND CW（获取多个二进制值的逻辑与）和 SUM CW（计算多个值的总和）等 CW 指令。PRAM 算法的每一步同样在恒定时间（一个时间单位）内完成，也包含三个阶段： - **读取阶段（READ）**：最多 \(n\) 个处理器同时从最多 \(n\) 个内存位置读取数据，每个处理器最多从一个内存位置读取，并将获取的值存储在本地寄存器中。 - **计算阶段（COMPUTE）**：最多 \(n\) 个处理器对其本地数据执行基本算术或逻辑运算。 - **写入阶段（WRITE）**：最多 \(n\) 个处理器同时将数据写入最多 \(n\) 个内存位置，每个处理器最多将本地寄存器中的值写入一个内存位置。 为比较并行算法和顺序算法的性能，我们引入了加速比和减速比的概念。加速比 \(S(1,n)\) 定义为最快已知顺序算法的最坏情况运行时间 \(t_1\) 与使用 \(n\) 个处理器的并行算法的最坏情况运行时间 \(t_n\) 的比值，即 \(S(1,n)=\frac{t_1}{t_n}\)。通常情况下，好的并行算法的加速比越大越好，并且在很多计算问题中，加速比最多等于并行计算机使用的处理器数量，这形成了并行计算中的一个传统认知——加速比民间定理：对于给定的计算问题，使用 \(n\) 个处理器的并行算法相对于该问题最快可能的顺序算法的加速比最多等于 \(n\)，即 \(S(1,n) \leq n\)。 减速比则用于衡量减少并行计算机处理器数量对运行时间的影响。传统观点认为，如果一个计算使用 \(n\) 个处理器需要时间 \(t_n\)，使用 \(p\) 个处理器（\(p < n\)）需要时间 \(t_p\)，那么 \(t_p\) 满足一定的上界，这就是减速比民间定理：\(\frac{t_p}{t_n} \leq \frac{n}{p}\)。然而，一些非常规问题的出现，对这两个民间定理提出了挑战。 #### 2. 先前工作 近期，一些非常规计算问题的提出，凸显了并行性的两个此前未被充分认识的方面： - 存在一些计算，并行算法能够实现超线性加速比，这在以前被认为是不可能的。 - 存在一些本质上并行的计算，即这些计算可以成功并行执行，但无法顺序执行。 下面我们详细介绍这些非常规问题。 ##### 2.1 单向函数 若一个函数 \(f\) 本身计算所需时间较少，但其逆函数 \(f^{-1}\) 的计算复杂度极高，则称 \(f\) 为单向函数。例如，对于整数序列 \(x_1, x_2, \ldots, x_n\)，计算给定子集的整数和很容易，但仅根据和来确定该整数序列中哪些元素相加得到这个和，目前尚无高效算法。 假设为了解决某个问题，需要计算 \(g(x_1, x_2, \ldots, x_n)\)，其中 \(g\) 是一个 \(n\) 变量的函数，计算 \(g\) 需要 \(\Omega(n)\) 次操作。例如，\(g(x_1, x_2, \ldots, x_n)=x_1^2 + x_2^2 + \cdots + x_n^2\)。计算 \(g\) 所需的输入 \(x_1, x_2, \ldots, x_n\) 以 \(n\) 对的形式给出，即 \(\langle x_i, f(x_1, x_2, \ldots, x_n) \rangle\)（\(i = 1, 2, \ldots, n\)）。函数 \(f\) 具有这样的性质：从 \(x_1, x_2, \ldots, x_n\) 计算 \(f\) 需要 \(n\) 个时间单位，而从 \(f(x_1, x_2, \ldots, x_n)\) 提取 \(x_i\) 需要 \(2^n\) 个时间单位。由于 \(g\) 需要实时计算，存在一个截止时间约束：如果一对数据在到达后的一个时间单位内未被处理，它将过时（被固定大小缓冲区中的其他数据覆盖）。 - **顺序解决方案**：\(n\) 对数据同时到达并存储在缓冲区中，等待 RAM 处理。在第一个时间单位，读取 \(\langle x_1, f(x_1, x_2, \ldots, x_n) \rangle\) 并计算 \(x_1^2\)，此时其他 \(n - 1\) 对数据已不可用。为了获取 \(x_2, x_3, \ldots, x_n\)，单个处理器 \(p_1\) 需要对 \(f\) 求逆，这需要 \((n - 1) \times 2^n\) 个时间单位，然后计算 \(g(x_1, x_2, \ldots, x_n)\)。因此，顺序算法的运行时间 \(t_1 = 1 + (n - 1) \times 2^n + 2(n - 1)\) 个时间单位。 - **并行解决方案**：当 \(n\) 对数据到达后，\(n\) 个处理器的 PRAM 立即处理。处理器 \(p_i\) 读取 \(\langle x_i, f(x_1, x_2, \ldots, x_n) \rangle\) 并计算 \(x_i^2\)（\(i = 1, 2, \ldots, n\)），然后 PRAM 处理器使用 SUM CW 计算 \(g(x_1, x_2, \ldots, x_n)\)，并行算法的运行时间 \(t_n = 1\) 个时间单位。 - **加速比和减速比**：PRAM 相对于 RAM 的加速比 \(S(1,n) = \frac{(n - 1) \times 2^n + 2(n - 1) + 1}{1}\)，是关于 \(n\) 的超线性函数，这与加速比民间定理相矛盾。如果 PRAM 只有 \(