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

### 并行编程：从顺序到隐式的转变 在当今的计算领域，我们常常期望通过升级处理器数量来提升程序的运行速度。然而，当我们将工作站从单处理器升级到多处理器时，却往往无法看到应用程序性能有显著的提升。这是因为大多数应用程序都是用顺序编程语言编写的顺序程序，这些程序无法直接利用多个处理器的优势。那么，是什么让并行编程变得如此困难？又有哪些解决方案呢？ #### 顺序语言如何掩盖并行性 许多问题在抽象层面上具有丰富的并行性，但当用顺序语言编写代码时，这些并行性往往被掩盖。以矩阵乘法为例，我们可以清晰地看到这种现象。 ##### 矩阵乘法中的并行性 矩阵乘法是计算机图形学中许多问题的核心计算。给定两个 $n \times n$ 的矩阵 $A$ 和 $B$，它们的乘积 $C = A \times B$ 是另一个 $n \times n$ 的矩阵，其中 $C_{ij}$ 等于 $A$ 的第 $i$ 行与 $B$ 的第 $j$ 列的内积。 从算法层面来看，矩阵乘法具有丰富的并行性： - 每个 $C_{ij}$ 的计算是相互独立的，因此可以并行计算 $n^2$ 个内积。 - 内积计算中的所有乘法可以并行进行，但加法通常需要顺序执行。不过，由于加法具有结合律和交换律，我们可以通过树求和或非确定性求和的方式来实现并行加法，从而进一步提高并行性。 以下是矩阵乘法和内积计算的并行性示意图： ```mermaid graph LR classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; A1(矩阵 A):::process --> C1(计算 C11):::process A2(矩阵 A):::process --> C2(计算 C12):::process B1(矩阵 B):::process --> C1 B1 --> C2 C1 --> C(矩阵 C):::process C2 --> C subgraph 内积计算 style 内积计算 fill:#ffffff,stroke:#000000,stroke-width:1px M1(乘法 1):::process --> A1 M2(乘法 2):::process --> A1 M1 --> B1 M2 --> B1 A1(加法 1):::process --> M1 A2(加法 2):::process --> M2 A1 --> A2 A2 --> 结果 end ``` ##### 顺序语言中的矩阵乘法 当我们用 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$ 循环，就会出现竞争条件，导致计算结果错误。 #### 如何实现并行执行 既然让程序员直接将现有顺序程序并行化既危险又困难，那么有哪些替代方法呢？主要有以下几种途径： | 方法 | 描述 | 示例语言 | | ---- | ---- | ---- | | 自动并行化 | 依靠编译器等自动系统将顺序程序安全地转换为并行程序 | 无 | | 数据并行扩展 | 在现有顺序语言中提供“数据并行”扩展，使编译器更容易进行并行化 | 高性能