并行计算对等模式 .pptVIP

MPI并行程序的对等模式 对等模式和主从模式是MPI的两种最基本的并行程序设计模式，可以说绝大部分MPI的程序都是这两种模式之一或二者的组合。 MPI程序一般是SPMD程序，当然也可以用MPI来编写MPMD程序，但是所有的MPMD程序都可以用SPMD程序来表达二者的表达能力是相同的。 对等模式的MPI程序设计 Jacobi迭代是一种比较常见的迭代方法，Jacobi迭代得到的新值是原来旧值点相邻数值点的平均。 Jacobi迭代的局部性很好，可以取得很高的并行性，是并行计算中常见的一个例子。将参加迭代的数据按块分割后各块之间除了相邻的元素需要通信外在，各块的内部可以完全独立地并行计算。随着计算规模的扩大通信的开销相对于计算来说比例会降低，这将更有利于提高并行效果。 迭代格式 线性方程组 Ax = y，即 Jacobi迭代原理介绍 若aii≠0, i = 1,2,…,n ,上式可变为 记 则 写成矩阵形式 或简记为 对任意初始向量 构造迭代格式： 上式称为简单迭代或雅可比（Jacabi）迭代。 雅可比迭代算法 算法描述： 1. 输入系数矩阵A和常数项向量y； 2. 形成雅可比迭代矩阵B和向量g 4. 实现迭代 5. 输出方程组的解 x2[i]，i=1,2,…,n. 3. 赋初始值 简化的Jacobi算法描述 假设元素 （m为行数，n为列数），若 满足 ，那么在每一次迭代中 。 设矩阵A= ，其中红色框包围部分，就是 每次迭代需要更新部分，简单 说：就是存在上下左右邻居的 数。 Jacobi迭代的串行表达 double a[N+1][N+1], b[N+1][N+1]; ...... for (k = 0; k SETP; k++){ //迭代次数 for (j = 1; j N; j++){ //计算 for (i = 1; i N; i++){ b[i][j] = (a[i - 1][j] + a[i + 1][j] + a[i][j - 1] + a[i][j + 1]) * 0.25; } } for (j = 1; j N; j++){ //更新值 for (i = 1; i N; i++){ a[i][j] = b[i][j]; } } Jacobi迭代的并行分析 为了并行求解，这里将参加迭代的数据按列进行分割，并假设一共有4个进程同时并行计算，数据的分割结果如图所示： Jacobi迭代的并行分析 假设需要迭代的数据是M×M的二维数组A(M,M)， 令M=4*N。按图示进行数据划分，则分布在四个不同进程上的数据分别是：进程0 ，A(M,1:N)； 进程1， A(M,N+1:2*N)；进程3，A(M,2*N+1:3*N)； 进程3， A(M,3*N+1:M)。 由于在迭代过程中，边界点新值的计算需要相邻边界其它块的数据，因此在每一个数据块的两侧又各增加1列的数据空间用于存放从相邻数据块通信得到的数据。这样原来每个数据块的大小从M*N扩大到M* N+2 ，进程0和进程1的数据块只需扩大一块即可满足通信的要求，但这里为了编程的方便和形式的一致在两边都增加了数据块。 Jacobi迭代的并行分析 计算和通信过程是这样的：首先对数组赋初值，边界赋为8 ，内部赋为0， 注意对不同的进程赋值，方式是不同的（两个内部块相同，但内部块和两个外部块两两互不相同）； 然后便开始进行Jacobi迭代，在迭代之前，每个进程都需要从相邻的进程得到数据块，同时每一个进程也都需要向相邻的进程提供数据块。