《中科大并行程序实验报告.pdf》由会员分享，可在线阅读，更多相关《中科大并行程序实验报告.pdf（10页珍藏版）》请在三一文库上搜索。
1、并行程序设计实验报告 公共部分 1.用 MPI_Send 、MPI_Recv实现 MPI_Bcast 、 MPI_Alltoall 、MPI_Gather 、MPI_Scatter 等 MPI 群及通信函数功能。 _MPI_Bcast: 程序运行结果如下 伪代码如下： _MPI_Bcast(sendbuf, sendcount, sendtype, root, comm) 对每个处理器执行以下算法 if my_rank = root then for i = 0 to p do /p 为进程个数 MPI_Send(sendbuf, sendcount, sendtype, i, root, c
2、omm) /root 向每个进程发送消息 end for end if /每个进程从root 接收带有root 标签的消息，接受信息存在各自的sendbuf 中 MPI_Recv(sendbuf, sendcount, sendtype, root, root, comm., /当前主行 * for k = v to n do fk = ai, k end for else v = j*m + i; /当前主行 * 接收主行所在处理器广播来的主行元素 End if if(my_rank = j) then /编号为 j 的处理器对其i+1 行以后各行进行变换 for k= i+1 to m-1
3、 do ak, v = ak, v / fv for w = v+1 to n-1 do ak, w = ak, w fw*ak, v end for end for if(my_rank j) then /编号大于j 的处理器对其所有行变换 for k = 0 to m -1 do ak, v = ak, v / fv for w = v+1 to n-1 do ak, w = ak, w fw*ak, v end for end for end if end for end for end 大体思路如同上面的伪代码给出，核心思想就是如果当前主行在第j 号处理器，那么按 照顺序划分的想法，编
4、号小于j 的处理器已经变换完了自己的各行，不需要做什么处理；编 号为 j 的处理器应用当前主行为其j+1 行等后续各行变换；编号大于j 的处理器其各行都还 没有经过变换，所以应用主行对其所有行进行变换。 有几个地方需要说明，以上伪代码只适用于处理器个数能被矩阵行数整除的情况，例如 9 行 9 列 3 个处理器这样。为了能够对任意数目处理器适用，需做以下改进： 记录 n mod p 为 left，当 left 等于 0 或者当前处理器编号小于left 的时候， 说明这些处理 器都有 m 行数据需要处理，而其他各行都只有m-1 行数据需要处理。例如矩阵为11x11， 有 3 个处理器， 则 m=c
5、eil(11/3)=4 ，left=11 mod 3 = 2 ，所以处理器0 和处理器 1 有 4 行数据， 处理器 2 只有 3 行数据。这导致算法中用” *” 标注的行需做必要修 改，在矩阵发送与结果接收的时候同样要做一些修改，该问题在此处不是主要矛盾，故不赘 述，详情可参见代码ludep.c。 编写的程序已经能够正常处理不能整除的情况，参见算法之前给出的5 个处理器的运行 结果。 加速表如下：去除了输入输出时间，纯并行计算的时间 规模节点数2 4 8 500 0.355469 0.203125 0.179688 1000 2.835938 1.527344 0.988281 2000 2
6、2.835938 12.609375 6.816406 从以上加速表可见，当规模增加的时候，如果节点数不变，并行算法计算的时间相应延 长。 当规模不变处理器数目增加的时候，如果问题规模不太大，则算法运行时间降低，但不 是线性降低， 即处理器越多， 由并行带来的加速效果变化越来越小(如规模 500 和 1000 的问 题， 8 处理器相对于4 处理器的加速效果弱于4 处理器相对于2 处理器的加速效果)。可以 验证当处理器过多的时候(与规模有关 )，并行算法非但不能降低运行时间，反而会延长。这 些都是因为消息传输花费的时间过多。如果规模相对于处理器数目比较大，那么处理器数目 的增加几乎能带来等比例
7、的加速效果的提升(如规模 2000 的问题， 8 处理器相对于4 处理器 的加速效果几乎与4 处理器相对于2 处理器的加速效果相同)，因为此时通信时间相对于运 行时间还不那么明显。 3. LU-OpenMP 3 线程处理9x9 矩阵时运行结果如下： 加速表如下：去除了输入输出时间，纯并行计算的时间 规模线程数2 4 8 500 0.362900 0.185099 0.233649 1000 2.934302 1.442188 1.485869 2000 23.556917 11.816813 11.932859 从以上加速表可见，当规模增加的时候，如果线程数不变，并行算法计算的时间相应延 长。
8、 当规模不变而线程数目增加的时候，一定变化范围内算法运行时间几乎随处理器数目线 性降低。 而如果线程数目过多，运行时间几乎不再改变甚至有所增加，这是由于每个核的处 理能力、 资源都有限， 过多的线程不能继续提高并行计算的效率，反而要花更多的时间调度 分配，导致效率不能继续提高甚至有所下降。 依赖关系如下： 图中设第 k 行为主行，纵坐标为矩阵A 的行号，从k 起始，横坐标为矩阵A 的列号， 从 k 起始。 从上图可见， 主行 k 中每列元素对之后各行每列元素进行变换，同时各行的第k 列元素 对之后各列元素进行变换，即各行内部有依赖关系，而各行之间没有依赖关系，所以可以按 照行划分。 4. 划分
9、通信域 伪代码如下： 每个处理器执行以下操作： MPI_Get_processor_name(name, &namelength) Color = atoi(name + 4) /我们节点的名称都是以node 起始，后面是编号 /按照 Color 的值分割当前通信域，以当前my_rank 为 key MPI_Comm_split(MPI_COMM_WORLD, Color, my_rank, &SplitWorld) 分组实验 MPI 、OpenMP 混合编程： 所选试验为第21 章的求解矩阵最大特征向量值的乘幂法。 给出一个处理500x500 矩阵的运行结果如下： 加速表如下：其中A 为问题
10、规模， B 为 OpenMP 进程数目， C 为 MPI 分配节点数目。 表中数据为并行计算的时间，已经去除了读取、输出的时间，单位为秒。OpenMP 中 Chunk 值设 50。 C 2 4 B A 2 4 8 2 4* 8 500 0.019531 0.011719 0.277344 0.011719 0.007812 0.265625 1000 0.050781 0.035166 0.222656 0.031250 0.023438 0.234375 2000 0.187500 0.105469 0.273438 0.101562 0.062500 0.261719 从上述加速数据表可以
11、看出：随问题规模增大，当节点数、 线程数不变的时候计算时间 逐渐变大。 MPI 并行 (进程级 )与 OpenMP 并行 (线程级 )可以获得比单一方法更为有效的计算结果， 运算时间缩短非常明显。 当规模不变的时候，对于固定线程数，随节点数目上升运行时间下降，但节点数目过多 的时候由于通信消耗过多，时间不会一直下降，甚至可能回升；对于固定节点数目，一定范 围内， 随线程数增加运行时间逐渐缩短。但当线程数目过多的时候，由于单个处理器运行能 力和资源都有限，过多的线程造成的调度等消耗过大，计算时间反而会提高。 通过这个表格我们也可以知道，对于并行算法，不是利用的处理器个数越多效果越好， 因为存在通
12、信开销；同样，对于单个芯片上的并行计算，不是线程数越多越好，当超过处理 器计算能力，调配等带来的开销可能比并行计算带来的时间减少更多。 针对本次实验环境，最好的搭配应该是4 个节点、 4 个线程。 （图中打 *号、用黄色标记） 学号： SC11011033 在曙光机上的文件夹截图如下： 文件夹中有实验的所有源程序、可执行程序及生成随机矩阵用以求最大特征值的程序 RandomMatrix 和生成可以LU 分解的随机矩阵用以验证LU 分解程序的程序 RandomLUMatrix 。 data4eig.txt 为 RandomMatrix 给出的随机矩阵结果。 data4lu.txt 为 RandomLUMatrix给出的可LU 分解的随机矩阵结果。