从顺序编程到隐式并行编程的探索

### 从顺序编程到隐式并行编程的探索 在当今的计算领域，我们都渴望通过增加处理器数量来显著提升程序的运行速度。然而，现实却不尽如人意，大多数应用程序以顺序语言编写，难以直接利用多核处理器的优势。本文将深入探讨并行编程的挑战，并介绍隐式并行编程的相关概念和优势。 #### 1. 顺序语言对并行性的遮蔽 许多问题在算法抽象层面存在丰富的并行性，但在具体的顺序语言编码过程中，这些并行性往往被掩盖。以矩阵乘法为例，从算法角度看，矩阵乘法具有大量的并行性。 - **矩阵乘法的并行性分析** - 对于两个 \(n \times n\) 矩阵 \(A\) 和 \(B\) 的乘积 \(C = A \times B\)，\(C\) 的每个元素 \(C_{ij}\) 是 \(A\) 的第 \(i\) 行与 \(B\) 的第 \(j\) 列的内积。由于每个 \(C_{ij}\) 的计算相互独立，因此可以并行计算 \(n^2\) 个内积。 - 在内积计算中，所有的乘法运算可以并行进行，但加法运算通常需要顺序执行，因为每个加法依赖于前一个加法的结果。不过，如果考虑加法的结合律和交换律，可以进一步挖掘并行性。例如，通过树状求和结构，\(N\) 次加法的时间复杂度可以从 \(N\) 降低到 \(\log_2(N)\)。 - **顺序语言实现的矩阵乘法** - 以 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 ``` - 这种实现方式完全舍弃了算法层面的并行性。主要问题在于状态的管理，即存储的重用。如果尝试并行执行，会导致竞态条件，使得最终计算结果可能错误，且调试困难。 #### 2. 实现并行执行的途径 为了实现并行执行，人们探索了多种途径。 - **自动并行化** - 自动并行化的目标是将传统顺序程序自动转换为并行程序。然而，由于存储重用和别名问题，这一目标仍然难以实现。例如，在顺序程序中，变量的重用会导致反依赖（use-def 依赖），编译器需要识别和消除这些反依赖才能实现并行化。但别名问题使得编译器难以准确判断变量是否指向同一存储位置，从而增加了并行化的难度。 - 例如，在以下代码片段中： ```fortran S1: x = a + b S2: y = x * c S3: x = d + e S4: z = x + f ``` - 存在从 \(S1\) 到 \(S2\) 和从 \(S3\) 到 \(S4\) 的真数据依赖，以及 \(S2\) 和 \(S3\) 之间的反依赖。通过重命名变量可以消除反依赖，例如将 \(S3\) 中的 \(x\) 改为 \(z\)。但在实际程序中，由于别名和复杂的下标分析，编译器很难准确判断和处理这些依赖关系。 - **数据并行编程** - 数据并行语言通过扩展顺序语言，提供对大型数据集合进行并行操作的原语。例如，Fortran 90 和高性能 Fortran（HPF）。 - 在 Fortran 90 中，赋值语句 `A = B + C` 当 \(A\)、\(B\) 和 \(C\) 为向量时，意味着对向量的每个元素进行加法运算。这种数据并行赋值语句中的元素级计算可以并行执行。 - HPF 进一步扩展了 Fortran 90，允许用户指定数组在并行机器上的分区和对齐方式。例如： ```fortran REAL, DIMENSION(100,100) :: A, B !HPF$ ALIGN A(I,J) with B(J,I) !HPF$ PROCESSORS P(4) !HPF$ DISTRIBUTE A(BLOCK, *) ONTO P ``` - HPF 编译器根据这些信息决定如何在处理器之间分配工作和进行通信。但选择合适的数据分布并不容易，需要权衡不同计算阶段的需求。 - **显式并行编程** - **共享内存编程与线程和锁**：通过扩展顺序语言，引入线程和锁机制来实现并行编程。例如，使用 `fork` 操作创建新线程，同时执行多个任务。但线程粒度的选择是一个难题，过多的线程会增加创建和上下文切换的开销，而过少的线程则会导致处理器空闲。 - 为了避免竞态条件，通常使用锁来保护共享数据。例如，在以