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

### 隐式并行编程：从顺序到并行的转变 在当今的计算领域，我们都期望程序能随着处理器数量的增加而自动提升运行速度。然而，现实却并非如此，大多数应用程序都是用顺序编程语言编写的，这些程序无法直接利用多处理器的优势。本文将深入探讨并行编程的难题，并介绍一种名为 pH 的隐式并行编程语言。 #### 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 ``` 这个程序是完全顺序执行的，所有操作依次进行，完全丢弃了算法层面的并行性。问题的关键在于状态的处理，顺序语言中存储的重用会导致并行执行时出现不确定性（竞争条件）。例如，在上述程序中，如果尝试并行执行 $i$ 和 $j$ 循环，变量 $s$ 的重用会导致不同线程之间相互干扰，最终计算出的矩阵 $C$ 的值可能是错误的。 #### 2. 实现并行执行的方法 由于直接将现有顺序程序并行化具有很大的风险和难度，因此有几种不同的方法可以实现并行执行： | 方法 | 描述 | 示例语言 | | ---- | ---- | ---- | | 自动并行化 | 依靠编译器等自动系统将顺序程序安全地转换为并行程序。 | - | | 数据并行编程 | 在现有顺序语言中提供“数据并行”扩展，使编译器更容易进行并行化。 | 高性能 Fortran、OpenMP | | 显式并行编程 - 共享内存编程 | 程序员指定并行执行的部分，并使用线程和锁等工具来管理共享状态。 | POSIX 线程（pthreads）、Java | | 显式并行编程 - 消息传递 | 并行程序由多个独立的顺序程序组成，通过通信原语进行消息传递。 | PVM、MPI | | 隐式并行编程 | 使用无状态或声明式语言，避免状态管理带来的并行化问题。 | pH | #### 3. 顺序程序的自动并行化 将传统顺序编程语言中的程序自动转换为并行程序的目标自 20 世纪 70 年代初就开始被研究，但至今仍未完全实现。要理解存储重用如何阻碍并行执行，我们需