并行计算
实
验
报
告
学院名称计算机科学与技术学院专业计算机科学与技术
学生姓名
学号
年班级
2016年6 月7 日
一、实验内容
本次试验的主要内容为利用MPI计算行列式的值，熟悉MPI及其API的使用，掌握MPI并行程序设计的基本思想和主要编程方法，对实验结果进行统计并分析以及加速情况分析，学会如何以并行的角度分析特定的问题，从而对并行计算有进一步的了解。
二、实验原理
2.1 行列式的计算
给定行列式：
求解行列式值的展开法求解方法如下：
余子式：在阶行列式中，把元素所在的第行和第列划去后，留下来的阶行列式叫做元素的余子式，记作M
ij。
代数余子式：A ij= (-1)i+j M
ij
行列式等于它的任一行（列）的各元素与其对应的代数余子式乘积之和，即D =
a i1A
i1
+a
in
A
in。
一个n阶行列式，如果其中第i行所有元素除外都为零，那末这行列式等于与
它的代数余子式的乘积，即D = a
ij A ij。
2.2 MPI
MPI是一种消息传递编程模型，是一种标准或规范的代表，其实现是一个库。
MPI的执行过程是SPMD(Single Program Multiple Data)的模式，也即所有的MPI 程序运行的代码实际是相同的，只不过每份代码数据不同。
利用MPI的计算方法主要通过让计算过程对于每个核而言，执行代码处理不同的数据。
针对本题目而言，所有核计算的都是代数余子式的计算和相加的问题，只不过对每个核而言，计算的是不同的部分。
程序有一个主进程和若干其他进程，每个进程计算不同的部分，最终把数据发送到主进程，由主进程汇总后得出行列式的值。
三、程序流程图
程序主体部分流程图如下：
图1 程序流程图
四、实验结果及分析
令核的总数数分别为1、2、4、12、16、24，并且对于每次实验重复十次求平均值。
随核心数变化的时间结果如下：
图2 随核心数变化的时间实验加速比曲线的计算公式如下：
结果如下：
图3 加速情况
本次实验过程中，n和ppn的情况如下表
表1 n和ppn序列
预期实验结果为，随着核心的数量的线性的提升，程序能实现线性的加速比的提升，也就是说加速比与核心数量成正比。
实验结果与预期并不完全相符，只有前半段随着核心的数量的上升程序加速比是提高的。
分析原因如下：实验过程设置矩阵阶数为12，当总的核心数量不大于12时，程序有较明显的加速效果，核心数目的提升会带来程序运行效率的提升，而当核心数量大于12时，由于每个核都计算某一的值对应的余子式，使得增加的多个核实际上并没有进行计算，反而增加了通信等开销，导致加速比下降。
根据实验过程，对核心数与任务的关系分析如下：当矩阵阶数小于核心数量时，不能完全发挥多核的性能，此时程序加速情况不能达到核心数的倍数；当矩阵阶数远大于核心数量时，每个核心分到的任务较多，因此程序的加速情况趋于稳定，接近于核心数的增加情况。
五、实验总结
本次试验的主要内容是MPI计算行列式的实现，通过这次实验，我对多核间程序通信的并行计算模式有了进一步的理解。
相对于第二个实验的多线程计算行列式的值而言，MPI计算行列式的程序显得比较复杂。
首先，MPI本身使用时要进行Init和Finalize等操作，其次MPI程序间的通信从阻塞与否来看有阻塞和非阻塞的形式，以及点对点和多对多模式等，其中还有组通信等，因此程序间的数据交换需要细心设计。
而言，对于每个核而言在具体编写的过程中，自己最初的想法是对于矩阵D
nxn
负责一个余子式的计算。
但是行列式的大小可能变得非常大，而实验环境的硬件条件是有限的，所以肯定要将任务近似平均的分配到每个核上而非每个核只计算一个余子式。
因此需要记录每个程序计算部分的始终点，来防止重复计算或者少计算。
在程序实现方面，要使每次计算都有相同的计算量，程序每次运行时生成30x30的矩阵，由于没有重新设置种子的值，所以程序每次运行时生成的矩阵都是一样的。
自己写的计算行列式的程序是直接递归的，因此复杂度较高，在矩阵阶数较大时计算相当缓慢，因此从程序的改进方面，可以采取转换成三角阵等方法，加快程序的运行。
经过本次试验，自己对MPI以及并行程序间的通信有了进一步的理解，认识到
自己的c++基础还不够好，因此要进一步加强自己的技能。
六、程序代码及部署
程序源代码见cpp文件
部署说明：
编译环境为OpenMPI，使用mpicc编译即可，运行时任务提交到服务器上。
编译命令如下：
mpic++ -i_dynamic -o a_det_mpi_11.o a_det_mpi_11.cpp
pbs脚本(rundetmpi.pbs)之一如下：
#!/bin/bash
#PBS -N det
#PBS -l nodes=2:ppn=8
#PBS -q AM016_queue
#PBS -j oe
cd $PBS_O_WORKDIR
for ((i=1;i<=10;i++))
do
procs=$(cat $PBS_NODEFILE | wc -l)
mpirun -np $procs -machinefile $PBS_NODEFILE ./a_det_mpi_11.o >> rundetmpi.log
done
其他pbs的不同仅在于n和ppn的值
提交命令：
qsub rundetmpi.pbs
之后查看rundetmpi.log结果即可。