并行编程：从顺序到隐式的转变

### 并行编程：从顺序到隐式的转变 在当今的计算领域，提升程序性能是一个永恒的追求。我们常常期望通过升级工作站的处理器数量，如从单处理器升级到双处理器，或者从两个处理器增加到四个，就能让程序运行速度翻倍。然而，现实往往并非如此。大多数应用程序都是用顺序编程语言编写的，这些程序无法直接利用多处理器系统的优势。即使升级到对称多处理器（SMP），我们也很难看到应用程序性能有显著提升。 #### 1. 顺序语言对并行性的遮蔽 许多问题在算法层面上具有丰富的并行性，但当用顺序语言表达时，这些并行性就会被掩盖。以矩阵乘法为例，从算法角度看，矩阵乘法具有大量的并行计算机会。给定两个 $n \times n$ 的矩阵 $A$ 和 $B$，它们的乘积 $C = A \times B$ 中的每个元素 $C_{ij}$ 是 $A$ 的第 $i$ 行和 $B$ 的第 $j$ 列的内积。每个 $C_{ij}$ 的计算都是独立的，因此可以并行计算 $n^2$ 个内积。而且，内积计算中的乘法也可以并行进行，但加法通常需要顺序执行。 然而，当用 Fortran 等顺序语言编写矩阵乘法程序时，程序会变成完全顺序执行的。例如： ```fortran integer i, j, k real A(N,N), B(N,N), C(N,N), s do i = 1,N do j = 1,N s = 0.0 do k = 1,N s = s + A(i,k) * B(k,j) end do C(i,j) = s end do end do ``` 这个程序一次只执行一个操作，完全丢弃了算法层面的并行性。如果尝试并行化这个程序，比如使用 `doall` 符号来并行执行 $i$ 和 $j$ 循环，会出现竞态条件。因为多个线程可能同时访问和修改共享变量 $s$，导致最终计算结果错误。 如果将程序修改为使用 $C(i,j)$ 来保存内积的部分和，就可以避免竞态条件： ```fortran integer i, j, k real A(N,N), B(N,N), C(N,N) doall i = 1,N doall j = 1,N C(i,j) = 0.0 do k = 1,N C(i,j) = C(i,j) + A(i,k) * B(k,j) end do end do end do ``` 这说明并发计算同时访问共享可更新存储位置时会遇到困难，并且并行性对原始编码风格非常敏感。 #### 2. 实现并行执行的方法 为了实现并行执行，有几种不同的方法： - **自动并行化**：保留现有的顺序语言，依靠编译器等自动系统将顺序程序安全地转换为并行程序。但由于别名问题和下标分析的复杂性，自动并行化在处理复杂数据结构时仍然面临挑战。例如，编译器需要识别和消除反依赖关系，但在存在别名的情况下，这变得非常困难。 - **数据并行编程语言**：在顺序语言中添加数据并行扩展，如 Fortran 90 和高性能 Fortran（HPF）。这些语言允许对大型数据集合进行并行操作，如向量和矩阵的元素级运算。例如，在 Fortran 90 中，`A = B + C` 可以表示向量或矩阵的加法。HPF 还允许用户指定数据在并行机器上的分布方式，以优化通信和计算效率。 - **显式并行性**： - **共享内存编程**：使用线程和锁来实现并行性。通过创建多个线程并使用锁来保护共享数据，可以避免竞态条件。例如，使用 `fork` 操作创建新线程，使用锁来同步对共享数据的访问。 - **消息传递**：将并行程序视为一组独立的顺序程序，通过发送和接收消息进行通信。这种模型适用于多计算机和集群系统，但编程难度较大，需要仔细设计通信协议和数据分布。 - **隐式并行编程**：使用声明式编程语言，避免状态的概念，从而避免并行化问题。函数式编程语言是这类语言的代表，如 Lisp、SML 和 Haskell。在函数式语言中，变量的值在计算过程中不会改变，所有计算都是基于旧值计算新值。 #### 3. 函数式语言的并行性与局限性 函数式语言具有天然的并行性，因为它们没有反依赖关系。例如，在 pH 中，对向量进行缩放操作时，会定义一个新的向量，而不会改变原始向量的值： ```plaintext b = array (1,n) [ (i, 5 * a!i) | i <- [1..n] ] ``` 矩阵乘法在 pH 中可以表示为： ```plaintext matmult a b = matrix ((1,1), (n,n)) [ ((i,j), ip A i B j) | i <- [1..n], j <- [1..n] ] ip A i B j = let s = a!(i,1) * b!(1,j) in for k <- [2..n] do next s = s + a!(i,k) * b!(k,j) finally s ``` 此外，函数式语言还支持生产者 - 消费者并行性，特别是在非严格数据结构的情况下。例如，一个程序可以在生产者生成数据的同时开始消费部分数据，而不需要等待整个数据结构完全生成。 然而，函数式语言也有其局限性。它们难以表达非确定性计算，某些程序在使用状态时会更简单，并且通常比命令式语言效率低。例如，在图遍历问题中，使用状态可以更直观地实现算法，而纯函数式语言需要更复杂的实现方式。同时，函数式语言的存储管理开销和不必要的复制操作也会影响其效率。 #### 4. pH：隐式并行的声明式语言