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

### 并行编程：从顺序到隐式的转变 在当今的计算领域，并行编程已成为提升程序性能的关键手段。然而，传统的顺序编程方式使得程序难以充分利用多核处理器的优势。本文将深入探讨并行编程的多种实现方式，包括自动并行化、数据并行编程、显式并行编程（共享内存和消息传递）以及隐式并行编程，并详细介绍消息传递矩阵乘法的不同版本及其优化策略。 #### 1. 顺序语言对并行性的掩盖 许多问题在算法抽象层面具有丰富的并行性，但在顺序语言中实现时，这些并行性往往被掩盖。以矩阵乘法为例，其在算法层面具有大量并行性： - **矩阵乘法的并行性**：对于两个 $n \times n$ 矩阵 $A$ 和 $B$ 的乘积 $C = A \times B$，$C$ 的每个元素 $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$ 循环，会出现竞态条件，导致计算结果错误。 #### 2. 实现并行执行的方法 由于直接将顺序程序并行化存在风险和困难，有几种替代方法可以实现并行执行： - **自动并行化**：依靠编译器等自动系统将顺序程序安全地转换为并行程序。但由于别名和下标分析等问题，该方法仅在结构相对简单的程序中取得了成功。 - **数据并行编程**：通过扩展顺序语言，提供对大型同质数据集合进行并行操作的构造。例如 Fortran 90 和 High Performance Fortran (HPF)，它们允许对向量和矩阵进行元素级的并行操作。但这种方法仅适用于基于密集矩形数组和简单嵌套循环并行性的应用。 - **显式并行编程** - **共享内存编程（线程和锁）**：通过扩展顺序语言引入线程，多个线程可以同时访问共享数据。但需要使用锁来保护共享数据，避免竞态条件。例如，使用 `fork` 创建新线程，使用锁保护对共享计数器的操作。 - **消息传递**：并行程序由多个独立的顺序程序组成，通过发送和接收消息进行通信。这种模型适用于多计算机和集群环境。 #### 3. 消息传递矩阵乘法 消息传递模型下的矩阵乘法有多种实现方式，下面介绍不同版本及其优化： - **版本 1**： - 收集矩阵 $A$ 的行和矩阵 $B$ 的列：每个节点通过循环将矩阵 $A$ 向左滑动，将矩阵 $B$ 向上滑动，最终每个节点包含 $A$ 的第 $i$ 行和 $B$ 的第 $j$ 列。 - 计算内积：每个节点使用本地的 $a_i$ 和 $b_j$ 向量计算内积。 ```fortran i = my_i bj(i) = bij j = my_j ai(j) = aij do iijj = 1, n–1 send(up, bj(i)) send(left, ai(j)) i = i + 1 if (i.gt.n) i = 1 j = j + 1 if (j.gt.n) j = 1 receive(down, bj(i)) receive(right, ai(j)) end do cij = 0.0 do k = 1,n cij = cij + ai(k) * bj(k) end do ``` - **版本 2**：将两个循环合并为一个，假设向上和向左的发送操作可以并行进行，该循环仅需 $N$ 个通信时间步。 ```fortran i = my_i bj(i) = bij j = my_j ai(j) = aij do iijj = 1, n–1 send(up, bj(i)) send(left, ai(j)) i = i + 1 if (i.gt.n) i = 1 j = j + 1 if (j.gt.n) j = 1 receive(down, bj(i)) receive(right, ai(j)) end do ``` - **版本 3**：通过观察内积中的加法可以以不同顺序执行而不改变最终结果，将存储需求从 $n^3$ 降低到 $n^2$。 ```fortran cij = aij * bij do k = 1, n–1 send(left, aij) send(up, bij) receive(right, aij) receive(down, bij) cij = cij + aij * bij end do ``` #### 4. 并行编程的挑战与展望 并行编程面临着诸多挑战，不同的并行编程方法各有优缺点： | 并行编程方法 | 优点 | 缺点 | | --- | --- | --- | | 自动并行化 | 系统性，避免人为引入竞态条件 | 仅适用于结构简单的程序，别名和下标分析困难 | | 数据并行编程 | 提供高级并行操作构造 | 仅适用于特定类型的应用，数据分布