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

### 并行编程：从顺序到隐式的转变 在当今的计算领域，我们都渴望通过增加处理器数量来显著提升程序的运行速度。然而，现实却往往不尽如人意，大多数应用程序采用顺序编程语言编写，难以充分利用多核处理器的优势。本文将深入探讨并行编程的多种方法，剖析顺序语言对并行性的遮蔽，以及隐式并行编程的潜力。 #### 顺序语言对并行性的遮蔽 许多问题在抽象层面上具有丰富的并行性，以矩阵乘法为例，其抽象解决方案中每个元素的计算相互独立，乘法操作也可并行进行。然而，当用顺序语言（如 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 ``` 这种顺序执行的主要困难在于状态的处理，即存储的重用。当多个并行操作同时访问共享存储位置时，会出现竞态条件，导致结果错误且难以调试。 #### 实现并行执行的方法 为了实现并行执行，人们尝试了多种方法： 1. **自动并行化**：通过编译器将顺序程序转换为并行程序，但由于别名检测和下标分析等问题的不确定性，该方法仅在结构简单的程序中取得了一定成功。 2. **数据并行编程语言**：如 Fortran 90 和 High Performance Fortran (HPF)，通过扩展顺序语言提供并行操作的构造。但这些语言的应用空间有限，且选择合适的数据分布并不容易。 3. **显式并行编程** - **共享内存编程**：使用线程和锁来实现并行，但线程粒度的选择困难，且需要仔细处理同步问题。 - **消息传递**：将并行程序分解为独立的顺序程序，通过消息传递进行通信。但该方法编程难度大，尤其是对于复杂的数据结构。 4. **隐式并行编程**：使用声明式语言，如函数式编程语言，避免了状态的概念，从而避免了并行化问题。但这些语言也存在一些局限性，如难以表达非确定性计算和某些需要状态的程序。 #### 函数式语言的并行性与局限性 函数式语言具有天然的并行性，因为变量具有唯一的值，不会发生变化，不存在反依赖关系。例如，在 pH 中对向量进行缩放操作： ```python b = array (1,n) [ (i, 5 * a!i) | i <- [1..n] ] ``` 此外，函数式语言的非严格数据结构还支持生产者 - 消费者并行性，允许消费者在数据生成的同时进行处理。然而，函数式语言也存在一些局限性，如难以表达非确定性计算、某些程序使用状态表达更简单，以及效率问题（如存储管理开销和不必要的复制）。 #### pH：隐式并行的声明式语言 pH 是 Haskell 的并行方言，它结合了函数式编程的并行性和对状态的显式表达与操作。pH 具有三个层次： 1. **函数层**：基于 Haskell 的纯函数式核心，具有高阶函数、非严格性和静态类型检查等特性，易于编写无竞态的并行程序。 2. **I - 结构层**：