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

### 隐式并行编程：从顺序到并行的探索 在当今的计算领域，我们都渴望通过增加处理器数量来提升程序的运行速度，就像升级处理器或内存系统那样轻松获得性能提升。然而，现实却并非如此，大多数应用程序都是用顺序编程语言编写的，这些程序难以充分利用多处理器的优势。本文将深入探讨并行编程的难题，并介绍一些解决方案，包括自动并行化、显式并行和隐式并行编程，最后着重介绍pH语言的特点和优势。 #### 顺序语言对并行性的遮蔽 许多问题在抽象层面上具有丰富的并行性，但当用顺序语言实现时，这些并行性往往被掩盖。以矩阵乘法为例，从算法层面看，矩阵乘法存在大量并行计算的可能性。 ##### 矩阵乘法的并行性分析 给定两个n×n的矩阵A和B，它们的乘积C = A × B，其中Cij是A的第i行和B的第j列的内积。从这个定义可以看出，C的每个元素都是独立计算的，因此可以并行计算n²个内积。同时，内积计算中的乘法也可以并行进行，但加法由于依赖前一次的结果，通常需要顺序执行。不过，如果考虑到加法的结合律和交换律，还可以进一步挖掘并行性。 例如，利用加法的结合律，可以将加法操作组织成树形结构，从而将N次加法的时间复杂度从N步降低到log₂(N)步。利用加法的交换律，还可以实现非确定性的求和方式，避免慢速计算对整体求和的影响。 ##### 顺序语言中的矩阵乘法 然而，当我们用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 ``` 这个程序是完全顺序执行的，每次只执行一个操作。即使我们尝试通过`doall`指令将i和j循环并行化，也会遇到竞态条件的问题。因为变量s被多个并行计算共享，同时读写s会导致结果错误，且这种错误难以调试。 如果我们将程序修改为使用C(i,j)来保存部分和，就可以避免竞态条件，但这也说明并行性对原始编码风格非常敏感。 #### 实现并行执行的方法 为了实现程序的并行执行，人们尝试了多种方法，主要包括自动并行化、显式并行和隐式并行。 ##### 自动并行化 自动并行化的目标是将传统顺序程序自动转换为并行程序。但由于存储重用导致的依赖关系，如反依赖（use-def dependence），使得并行执行变得困难。编译器需要识别和消除这些依赖关系，例如通过重命名变量来消除反依赖。 然而，实际情况中，由于别名（aliasing）和下标分析的复杂性，编译器很难准确识别依赖关系。例如，在循环中，变量的下标可能在运行时动态确定，编译器无法提前判断是否存在依赖。此外，循环变换有时可以消除依赖，但这也增加了编译器的复杂性。 尽管自动并行化的目标仍然难以实现，但相关研究带来的见解、术语和技术具有重要价值。目前，自动并行化主要在结构相对简单的程序中取得了一定成果，如包含简单循环和矩阵计算的程序。 ##### 数据并行编程语言 数据并行语言通常是顺序语言的扩展，允许对大型同质数据集合进行并行操作。Fortran 90和High Performance Fortran (HPF)是典型的例子。 在Fortran 90中，赋值语句`A = B + C`在变量为向量时，会自动执行向量加法，即对每个元素进行并行计算。同时，Fortran 90还支持数据并行循环和各种数组归约操作，程序员可以在较高层次上指定并行性，由编译器负责具体实现。 HPF则进一步解决了分布式内存机器上的数据分布问题。程序员可以通过指令指定数组如何在并行机器上分区和对齐，HPF编译器会根据这些信息分配工作和生成通信代码。然而，选择合适的数据分布并不容易，需要权衡通信成本和数据局部性。 以下是一个HPF数组分布的示例： ```fortran REAL, DIMENSION(100,100) :: A, B !HPF$ ALIGN A(I,J) with B(J,I) ```