文档介绍：科技大学计算机与通信工程学院
实验报告
实验名称：
学生：
专业：
班级：
学号：
指导教师：
实验成绩：________________________________
实验地点：
实验时间：2015年05月
一、实验目的与实验要求
1、实验目的
1对比矩阵乘法的串行和并行算法，查看运行时间，得出相应的结论；
2观察并行算法不同进程数运行结果，分析得出结论；
2、实验要求
1编写矩阵乘法的串行程序，多次运行得到结果汇总；
2编写基于MPI，分别实现矩阵乘法的并行化。对实现的并行程序进行正确性测试和性能测试，并对测试结果进行分析。
二、实验设备（环境）及要求
《VS2013》C++语言
MPICH2
三、实验容与步骤
实验1，矩阵乘法的串行实验
（1）实验容
编写串行程序，运行汇总结果。
（2）主要步骤
按照正常的矩阵乘法计算方法，在《VS2013》上编写矩阵乘法的串行程序，编译后多次运行，得到结果汇总。
实验2矩阵乘法的并行化实验
3个总进程
5个总进程
7个总进程
9个进程
16个进程
四：实验结果与分析
（一）矩阵乘法并行化
矩阵并行化算法分析：
并行策略：1间隔行带划分法
算法描述：将C=A*B中的A矩阵按行划分，从进程分得其中的几行后同时进行计算，最后通信将从进程的结果合并的主进程的C矩阵中
对于矩阵A*B
如图：进程1：矩阵A第一行
进程2：矩阵A第二行
进程3：矩阵A第三行
进程1：矩阵A第四行
时间复杂度分析：
f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2
(k为从进程分到的行数)
因此O(n)=(n)；
空间复杂度分析：
从进程的存储空间不共用，f(n)=n;
因此O(n)=(n);
2间隔行带划分法
算法描述：将C=A*B中的A矩阵按行划分，从进程分得其中的几行后同时进行计算，最后通信将从进程的结果合并的主进程的C矩阵中
对于矩阵A*B
如图：进程1：矩阵A第一行
进程2：矩阵A第二行
进程3：矩阵A第三行
进程3：矩阵A第四行
时间复杂度分析：
f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2
(k为从进程分到的行数)
因此O(n)=(n)；
空间复杂度分析：
从进程的存储空间不共用，f(n)=n;
因此T(n)=O(n);
测试环境简介：
《VS2013》
Win7旗舰版
正确性测试结果：
并行结果：
串行结果：
通过比较发现两者相同，因此可以确定运算结果正确。
性能测试结果：
串行
125ms
107ms
108ms
98ms
109ms
110ms
3进程

5进程

7进程

ms
ms
ms
ms
s
9进程

16进程

通过对比分析得出，并行算法能够有效提高矩阵乘法的运算效率；
（二）串行算法分析
时间复杂度：
f(n)=2+n^2+2*n+3*n+7+n+n+7;
因此T(n)=O(n^2)
空间复杂度：
T（n）=O(1)
五：结论（讨论）
实验结论
根据前面实验结果，可以证明并行算法比串行算法更能有效地运算矩阵乘法，可以提高效率数