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

### 并行编程：从顺序到隐式的转变 在当今的计算领域，并行编程变得越来越重要。随着多核处理器的普及，利用并行性来提高程序性能成为了关键。然而，传统的顺序编程语言在挖掘并行性方面存在诸多困难，这促使我们探索新的编程方法和语言。 #### 顺序语言对并行性的掩盖 许多问题在算法层面具有丰富的并行性，以矩阵乘法为例，从算法角度看，矩阵 $C$ 的每个元素都可以独立计算，即 $n^2$ 个内积可以并行进行。而且，内积计算中的乘法也能并行执行，但加法由于依赖前一个结果，通常需要顺序执行。不过，若考虑加法的结合律和交换律，还能挖掘出更多并行性。 然而，当用顺序语言（如 Fortran）编写矩阵乘法程序时，并行性完全被消除。例如下面的 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$ 循环，会出现竞态条件，导致计算结果错误。 #### 实现并行执行的方法 为了实现并行执行，人们探索了多种方法： 1. **自动并行化**：通过编译器将顺序程序安全地转换为并行程序。但由于别名问题、下标分析等难题，自动并行化仅在结构较简单的程序中取得成功。 2. **数据并行编程语言**：如 Fortran 90 和 High Performance Fortran (HPF)，通过扩展顺序语言提供并行操作大型数据集合的原语。例如，在 Fortran 90 中，向量和矩阵的赋值语句可以自动并行执行。但选择合适的数据分布是一个难题，会影响程序性能。 3. **显式并行性** - **共享内存编程**：通过线程和锁来管理共享状态，避免竞态条件。但线程粒度的选择是一个挑战，过多或过少的线程都会影响性能。 - **消息传递**：由多个独立的顺序程序通过发送和接收消息进行通信。以矩阵乘法为例，实现消息传递的矩阵乘法程序较为复杂，需要仔细设计通信逻辑。 4. **隐式并行编程**：使用声明式语言，避免状态的概念，从而避免并行化问题。例如函数式编程语言，在函数式语言中，变量的值在计算过程中不会改变，所有计算都是基于旧值定义新值。 #### 函数式语言的特点与局限 函数式语言具有隐式并行性，因为不存在变量值的改变，所以没有反依赖关系。例如，在 pH 中缩放向量的代码如下： ```plaintext b = array (1,n) [ (i, 5 * a!i) | i <- [1..n] ] ``` 这定义了一个新向量 $b$，而原向量 $a$ 保持不变。矩阵乘法也可以用类似的方式表达： ```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 ``` 此外，函数式语言还具有生产者 - 消费者并行性，通过非严格数据结构，消费者可以在生产者计算的同时开始工作。 然而，函数式语言也存在局限性。一些计算任务本质上是非确定性的，如基准测试、通信协议和存储分配器等，无法用函数式语言表达。而且，函数式语言通常效率较低，存在存储管理开销和不必要的复制问题。 #### pH：隐式并行的声明式语言 pH 是 Haskell 的并行方言，它结合了函数式编程的优点和对状态操作的支持，分为三个层次： 1. **函数层**：其核心语法和非严格语义与纯函数式语言 Haskell 相同，没有状态的概念，因此编写无竞态的并行程序很容易。核心特性包括高阶函数和非严格性，高阶函数可以提高语言的参数化能力，非严格性允许函数在参数可用之前执行，并允许数据结构的组件在一段时间内为空。 2. **I - 结构层**：在函数核心的基础上添加了 I - 结构，这是一种有限但良性的状态形式，保证程序无竞态且具有确定性。I - 结构组件从空到满的转换是一次性的，读取操作不会出现不确定性。 3. **M - 结构层**：添加了 M - 结构，允许重用存储和任意操作状态。与命令式语言的赋值语句不同，对 M - 结构数据的访问是隐式同步的，这使得共享状态的操作更经济且高效。例如，多个并行计算更新共享数组 $h$ 的组件时，pH 中的更