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

### 并行编程从顺序到隐式的探索 在当今的计算机领域，我们都期望程序能随着处理器数量的增加而显著提升运行速度。然而，现实是大多数应用程序以顺序语言编写，难以充分利用多核处理器的优势。本文将深入探讨并行编程的挑战，并介绍多种并行编程方法，包括自动并行化、数据并行编程、显式并行编程和隐式并行编程，同时分析它们的优缺点。 #### 顺序语言对并行性的遮蔽 许多问题在抽象层面具有丰富的并行性，但在顺序语言中实现时，这种并行性往往被掩盖。以矩阵乘法为例，从算法层面看，矩阵乘法存在大量并行计算的可能性。 - **矩阵乘法的并行性分析** - **元素独立性**：对于两个 \(n \times n\) 矩阵 \(A\) 和 \(B\) 的乘积 \(C = A \times B\)，\(C\) 的每个元素 \(C_{ij}\) 是 \(A\) 的第 \(i\) 行与 \(B\) 的第 \(j\) 列的内积，这些内积计算相互独立，可并行进行。 - **乘法并行性**：每个内积计算中的乘法操作也可以并行执行，但加法操作由于依赖前一个加法的结果，通常需要顺序执行。不过，利用加法的结合律和交换律，可以进一步挖掘并行性。例如，通过树状求和结构，可将 \(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 ``` 这个程序是完全顺序执行的，每次只执行一个操作。如果尝试并行执行 \(i\) 和 \(j\) 循环，会出现竞态条件（race condition），导致计算结果错误。例如，在并行执行时，多个线程可能同时访问和修改变量 \(s\)，相互干扰。 为了避免竞态条件，可以修改代码，消除变量 \(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 ``` 这表明并行性对原始编码风格非常敏感，同时也说明了顺序语言的一个优点：程序员无需担心竞态条件，顺序语义使得程序的状态操作行为易于理解和调试。 #### 实现并行执行的方法 由于直接对顺序程序进行并行注解存在风险且难度较大，因此有多种方法可用于实现并行执行。 - **自动并行化** - **原理**：保留现有顺序语言，依靠编译器等自动系统将顺序程序安全地转换为并行程序。 - **挑战**：重用存储导致的依赖关系（如真数据依赖、反依赖和输出依赖）使得并行化变得复杂。特别是别名（aliasing）和复杂的下标计算，使得编译器难以准确识别和消除依赖关系。例如，在存在别名的情况下，编译器可能无法确定变量是否指向同一存储位置，从而保守地假设存在依赖关系。 - **适用范围**：目前，自动并行化主要适用于结构相对简单的程序，如包含简单循环和矩阵计算的程序。对于具有复杂索引结构的数组（如稀疏矩阵）和其他数据结构（如树、图和队列），自动并行化仍然是一个难题。不过，一些新的方法，如“交换性分析”（commutativity analysis），利用面向对象语言的封装特性，为解决这一问题提供了新的思路。 下面是一个简单的示例，展示了依赖关系和别名问题： ```fortran ! 原始代码 S1: x = 1.0 S2: y = x + 1.0 S3: x = 2.0 S4: z = x + 1.0 ! 消除反依赖后的代码 S1: x = 1.0 S2: y = x + 1.0 S3: z1 = 2.0 S4: z = z1 + 1.0 ``` - **数据并行编程** - **特点**：数据并行语言通常是顺序语言的扩展，允许对大型同质数据集合进行并行操作。主要示例包括 Fortran 90 和高性能 Fortran（HPF）。 - **Fortran 90 的数据并行特性**：在 Fortran 90 中，赋值语句可以对数组进行元素级的并行操作。例如，`A = B + C` 当 `A`、`B` 和 `C` 为向量时，表示对向量的每个元素进行加法操作。此外，Fortran 90 还支持数据并行循环和各种数组归约操作，程序员可以在较高层次上指定并行性，由编译器负责具体的实现细节。 - **HPF 的数据分布管理**：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 ``` 这段代码指定了矩阵 \(A\) 和 \(B\) 的元素对齐方式，以及 \(A\) 的行在四个处理器上的块分布方式。HPF 编译器根据这些信息决定如何分配工作和进行通信。 然而，选择良好的数据分布并不容易，不同的计算阶段可能需要不同的对齐和分布方式。动态重新分布数组可以缓解冲突，但会带来额外的开销。因此，许多研究人员致力于开发自动化方法，为普通 Fortran 90 代码插入 HPF 数据分布注解。 下面是一个简单的数据并行编程示例，展示了 Fortran 90 中向量加法的并行操作： ```fortran REAL, DIMENSION(1:100) :: A, B, C A = B + C ``` #### 显式并行编程 显式并行编程将并行执行的负担转移给程序员，主要有两种方法：共享内存编程和消息传递。 - **共享内存编程：线程和锁** - **线程的概念**：通过扩展顺序语言，引入线程的概念。线程可以看作是多个具有相同数据视图的顺序程序，两个线程可以持有同一变量的地址，并使用标准的变量访问符号访问其内容。线程中过程调用的局部变量是私有的，其他线程无法访问。 - **线程创建的表示方法**：一种表示创建新线程的符号是用 `fork` 替换函数调用。例如，`F(i)` 替换为 `fork F(i)`。当机器遇到普通的过程调用时，会暂停执行，执行函数 `F` 直到完成，然后返回并继续执行后续代码；而当遇到 `fork` 时，会创建一个新的线程并行执行 `F`。 下面是一个简单的线程创建示例： ```fo ```