并行计算论文详解.doc

******************* 实践教学 ******************* 兰州理工大学 理学院 2016年春季学期 并行计算 课程设计 专业班级： 13级信息与计算科学 姓 名： 田 兴 福 学 号： 指导教师： 孟新友 郭秀婷 成 绩： 摘要 本文主要设计了MIMD（多指令流多数据）异步并行的Gauss一Seidel迭代法，并利用MPI消息传递模型实现了该算法并实际测试了求解所花费的时间和进行了算法的理论评估。算法的主要过程如下：首先，主进程在数据域对线性方程组的增广矩阵进行带状化分，并将划分的结果广播到其他处理器，然后，各个处理器按照自己的指令流进行计算，并利用存储转发的方式进行消息传递，最后，满足精度要求后，通过设置同步路障使得各个处理器的结果归约至主进程，由主进程并输出求解结果。 关键词：异步并行 Gauss一Seidel迭代法 消息传递 同步 路障  目录 摘要 2 一．题目及要求 4 1.1题目 4 1.2要求 4 二．算法设计原理 4 2.1设计算法 4 2.2算法原理 5 三．算法描述及设计流程 6 3.1算法描述 6 3.2设计流程 7 四．源程序代码及运行结果 9 4.1源程序代码 9 4.2运行结果 16 五．算法分析及优缺点 17 5.1算法分析 17 5.2优缺点 17 总结 18 参考文献 19 一．题目及要求 1.1题目 迭代求解的高斯-赛德尔法（MIMD异步并行算法）求解方程组的解 1.2要求 本次课程设计的题目是利用高斯-赛德迭尔求解方程组，在求解过程中要求用MIMD异步并行算法求解。 二．算法设计原理 2.1设计算法 求解线性方程组的高斯—赛德尔法（Gauss-Seidel Method），实际上是迭代法，不仅稠密矩阵性系适用，而且稀疏矩阵性系也适用。下面是他的主要原理： 在求解,可以将系数矩阵分解为,其中均为的矩阵，具体的定义如下：[2] 这样，可以换成。如果给定初始解, 则第次迭代可计算如下： (1) 由于在迭代的算法中需要判断是否在第次收敛，这里利用向量的1范数去判断是否终止迭代过程，计算公式如下： (2) 式能够加快顺序计算速度，因此当依次计算时，第次迭代的值，一部分可以用本次迭代的值（相应于上三角部分），而一部分可用本次迭代的值（相应于下三角部分）。 2.2算法原理 对于以上的分析，该算法无法直接并行化，为此通过分析，将线性方程组的增广矩阵按行划分如图 1。 图 1 增广矩阵的划分 对于高斯-塞德尔迭代，计算的新值时，使用的旧值和的新值。计算过程中与及的新值会在不同的处理器中产生，因此可以考虑采用时间偏移的方法，使各个处理器对新值计算的开始和结束时间产生一定的偏差。编号为 my_rank 的处理器一旦计算出的新值，就立即广播给其余处理器，以供各处理器对x 的其它分量计算有关的乘积项并求和。当它计算完 x的所有分量后，它还要接收其它处理器发送的新的分量，并对这些分量进行求和计算，为计算下一轮的作准备。计算开始时，所有处理器并行地对主对角元素右边的数据项进行求和，此时编号为 0 的处理器 （简称为）计算出然后广播给其余处理器，其余所有的处理器用的新值和其对应项进行求和计算，接着计算出当完成对的计算和广播后，计算出，并广播给其余处理器，其余所有的处理器用的新值求其对应项的乘积并作求和计算。 然后计算出当完成对的计算和广播后，计算出，如此重复下去，直至 在 中被计算出并广播至其余的处理器之后，计算出下一轮的新的，这样逐次迭代下去，直至收敛为止。[1] 三．算法描述及设计流程 3.1算法描述 通过在第二小节的分析，我们才用类程序语言对MIMD异步并行算法的Guass一Seidel法进行描述： 输入：输入矩阵，常数项，初始解，精度。 输出：解向量。 对所有处理器my_rank(my_rank=)同时执行如 for(i=my_rank m;(my_rank+1) m；i++) //所有处理器并行的对主对角线元素右边的数据求和 sum[i]=0.0 for(j=i+1;jn-1;j++) sum[i]=sum[i]+A[i,j]*x[j] total=0 endfor endfor while(totaln){//total为新旧值之差小于 的 分量个数 （2.1）iteration=0// iteration为本处理器中新旧值之差小于 的分量个 （2.2）for(