并行计算论文

实践教学实践教学 兰州理工大学兰州理工大学 理学院 2016 年春季学期 并行计算并行计算 课程设计课程设计 专业班级 13 级信息与计算科学 姓 名 田 兴 福 学 号 13540231 指导教师 孟新友 郭秀婷 成 绩 2 摘要摘要 本文主要设计了 MIMD 多指令流多数据 异步并行的 Gauss 一 Seidel 迭 代法 并利用 MPI 消息传递模型实现了该算法并实际测试了求解所花费的时间 和进行了算法的理论评估 算法的主要过程如下 首先 主进程在数据域对线 性方程组的增广矩阵进行带状化分 并将划分的结果广播到其他处理器 然后 各个处理器按照自己的指令流进行计算 并利用存储转发的方式进行消息传递 最后 满足精度要求后 通过设置同步路障使得各个处理器的结果归约至主进 程 由主进程并输出求解结果 关键词 异步并行 Gauss 一 Seidel 迭代法 消息传递 同步 路障 3 目录目录 摘要 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 4 一 题目及要求一 题目及要求 1 11 1 题目题目 迭代求解的高斯 赛德尔法 MIMD 异步并行算法 求解方程组 的解 13 52 4225 321 32 321 xxx xx xxx 1 21 2 要求要求 本次课程设计的题目是利用高斯 赛德迭尔求解方程组 在求解过程中要 求用 MIMD 异步并行算法求解 二 算法设计原理二 算法设计原理 2 12 1 设计算法设计算法 求解线性方程组的高斯 赛德尔法 Gauss Seidel Method 实际上是迭 代法 不仅稠密矩阵性系适用 而且稀疏矩阵性系也适用 下面是他的主要原 理 在求解 可以将系数矩阵 分解为 其中均为 的矩阵 具体的定义如下 2 这样 可以换成 如果给定初始解 则第 次迭代可计算如下 1 由于在迭代的算法中需要判断是否在第 次收敛 这里利用向量的 1 范数去 判断是否终止迭代过程 计算公式如下 2 5 1 式能够加快顺序计算速度 因此当依次计算时 第 次迭代的值 一部分可以用本次迭代的值 相应于上三角部分 而一部分可用本次迭代的值 相应于下三角部分 2 22 2 算法原理算法原理 对于以上的分析 该算法无法直接并行化 为此通过分析 将线性方程组的增 广矩阵 按行划分如图 1 图 1 增广矩阵的划分 对于高斯 塞德尔迭代 计算的新值时 使用的旧值和 i x 11 in xx 的新值 计算过程中与及的新值会在不同的处 01 i xx i x 01 i xx 11 in xx 理器中产生 因此可以考虑采用时间偏移的方法 使各个处理器对新值计算的 开始和结束时间产生一定的偏差 编号为 my rank 的处理器一旦计算出 的新值 就立即广播给其余处理器 以供 1 i x myrankmi myrankm 各处理器对 x 的其它分量计算有关的乘积项并求和 当它计算完 x 的所有分 i x 量后 它还要接收其它处理器发送的新的分量 并对这些分量进行求和计算 x 为计算下一轮的作准备 计算开始时 所有处理器并行地对主对角元素右边 i x 的数据项进行求和 此时编号为 0 的处理器 简称为 计算出然后广播 0 p 0 x 6 给其余处理器 其余所有的处理器用的新值和其对应项进行求和计算 接着 0 x 计算出当完成对的计算和广播后 计算出 并广播给其 0 p 12 x x 0 p 1m x 1 p m x 余处理器 其余所有的处理器用的新值求其对应项的乘积并作求和计算 m x 然后计算出当完成对的计算和广播后 计算出 1 p 12 mm xx 1 p 2 1m x 2 p 2 m x 如此重复下去 直至 在 中被计算出并广播至其余的处理器之后 1n x 1p p 计算出下一轮的新的 这样逐次迭代下去 直至收敛为止 1 0 p 0 x 三 算法描述及设计流程三 算法描述及设计流程 3 13 1 算法描述算法描述 通过在第二小节的分析 我们才用类程序语言对 MIMD 异步并行算法的 Guass 一 Seidel 法进行描述 输入 输入矩阵 常数项 初始解 精度 nn A 1 n b 0 1 0 1 0 0 0 n xxxx 输出 解向量 n xxx 1 0 对所有处理器 my rank my rank 同时执行如 for i my rank m my rank 1 m i 所有处理器并行的对主对角线元素右边的数据求和 sum i 0 0 for j i 1 j n 1 j sum i sum i A i j x j total 0 endfor endfor while total n total 为新旧值之差小于 的 分量个数 2 1 iteration 0 iteration 为本处理器中 新旧值之差小于 的分量个 2 2 for j 0 j n 1 j 依次以第 0 1 n 1 行为主行 7 i q j m ii if my rank q 表示朱行所在的处理器 产生的新值 Temp x j x j b j sum j a I j Endif If x j temp Iteration Endif 将 x j 的新值广播到其他的 n 1 个处理器 S j 0 For i my rank m i my rank 1 m i If j Sum i sum i A I j x j Else 其他处理器 接受广播来的 x j 新值 endif 对所存在各行计算 x j 所对应的内积项累加 For i my rank m i my rank 1 m 1 i Sum i sum i A I j x j endfor endfor 求出所有处理器中 iteration 和 total 的值并广播到所有处理器 endfor endwhile 3 23 2 设计流程设计流程 为了实现 MIMD 异步并行算法的 Guass 一 Seidel 法 采用的消息传模型进 行实现 具体的实现流程如图 2 8 图 2 程序设计流程 消息传递中所使用的相关函数如表 1 函数名功能 MPI Init int m float B float A float V double starttime double time1 double time2 int my rank int p MPI Status status FILE fdA fdB fdB1 10 void Environment Finalize float a float b float v free a free b free v int main int argc char argv int i j my rank group size int k float sum float b float v float a float differ float temp w int iteration total loop int r q loop 0 total 0 w 0 9 MPI Init MPI Comm size MPI COMM WORLD MPI Comm rank MPI COMM WORLD p group size if my rank 0 starttime MPI Wtime fdA fopen dataIn txt r 11 fscanf fdA d d if size N 1 printf the input is wrong n exit 1 A float malloc floatsize size size B float malloc floatsize size V float malloc floatsize size for i 0 i size i for j 0 j N j if j N 1 fscanf fdA f B i else fscanf fdA f A i size j for i 0 i size i fscanf fdA f V i fclose fdA printf Input of file dataIn txt n printf d t d n size N for i 0 i size i for j 0 j size j 12 printf f t A i j printf f n B i printf n for i 0 i size i printf f t V i printf n n printf nOutput of result n MPI Bcast m size p if size p 0 m v float malloc floatsize size a float malloc floatsize m size b float malloc floatsize m sum float malloc floatsize m if my rank 0 for i 0 i m i for j 0 j size j a i j A i j for i 0 i m i b i B i if my rank 0 for i 0 i size i 13 v i V i MPI Bcast v size MPI FLOAT 0 MPI COMM WORLD if a NULL b NULL v NULL printf allocate space fail else printf allocate space successful n if my rank 0 for i 1 i p i MPI Send MPI Send free A free B free V else MPI Recv a m size MPI FLOAT 0 my rank MPI COMM WORLD MPI Recv b m MPI FLOAT 0 my rank MPI COMM WORLD time1 MPI Wtime for i 0 i m i for j 0 j size j printf f a i j printf n 14 for i 0 i m i sum i 0 0 for j 0 j my rank m i sum i sum i a i j v j printf This is f n sum i while total size iteration 0 total 0 for j 0 j size j r j m q j m if my rank q temp v my rank m r for i 0 i r i sum r sum r a r my rank m i v my rank m i v my rank m r 1 w temp w b r sum r a r my rank m r if fabs v my rank m r temp E iteration 15 MPI Bcast sum r 0 0 for i 0 i r i sum i sum i a i my rank m r v my rank m r else MPI Bcast 4 for i 0 i m i sum i sum i a i q m r v q m r MPI Allreduce loop if my rank 0 printf 2d th total vaule d n loop total time2 MPI Wtime if my rank 0 for i 0 i size i printf x d f n i v i printf n printf Iteration num d n loop printf Whole running time f seconds n time2 starttime printf Distribute data time f seconds n time1 starttime printf Parallel compute time f seconds n time2 time1 16 MPI Barrier MPI COMM WORLD MPI Finalize Environment Finalize a b v return 0 4 24 2 运行结果运行结果 Input of file dataIn txt 3 4 5 000000 2 000000 2 000000 4 000000 0 000000 2 000000 1 000000 5 000000 1 000000 1 000000 3 000000 1 000000 0 000000 0 000000 1 000000 Output of result allocate space successful This is 2 000000 1 th total vaule 0 2 th total vaule 0 3 th total vaule 0 4 th total vaule 0 5 th total vaule 0 6 th total vaule 0 7 th total vaule 3 x 0 1 999635 x 1 1 999954 x 2 0 999866 17 Iteration num 7 Whole running time 0 004000 seconds Distribute data time 0 003000 seconds Parallel compute time 0 001000 seconds 五 算法分析及优缺点五 算法分析及优缺点 5 15 1 算法分析算法分析 若取一次乘法和加法运算时间或一次比较运算时间为一个单位时间 在算 法开始阶段 各处理器并行计算主对角线右边元素相应的乘积项并求和 所需时 间为 进入迭代计算后 虽然各个处理器所负责的 的分量在每 一轮计算中的开始时间是不一样的 但一轮迭代中的计算量都是相等的 因此 不妨取 0 号处理器为对象分析一轮迭代计算的时间 容易得出 0 号处理器计算 时间为 另外它在一轮迭代中做广播操作 次 通信量为 1 归约操作 1 次 通信量为 1 所有的通信时间为 因此高塞德尔迭代一轮并行时间 5 25 2 优缺点优缺点 利用 MIMD 异步并行算法求解方程组节省时间且容易操作 通信效率高 但 是调程序麻烦 使用处理器个数太多 太多就会影响效率 18 总结总结 通过这次课程设计 让我更加深刻了解课本知识 和以往对知识的疏忽得 以补充 在设计过程中遇到一