《并行计算导论》课程报告

矩阵向量乘法的并行化 2016 年 3 月 31 日 第 1 页 共 12 页 北 京 科 技 大 学 并行计算导论 实验报告 题目：矩阵向量乘法的并行化 学 院 计算机与通信工程学院 班 级 计 1301 1303 1304 班 组号 学号 姓名 贡献比(%) 成绩 41351145 徐期涛 20% 41355003 王皓 20% 41155019 范彦凯 20% 41355080 陈寒 20% 2 41345053 徐松松 20% 指导教师 李建江 时 间 2016 年 3 月 22 日至 3 月 31 日 矩阵向量乘法的并行化 2016 年 3 月 31 日 第 2 页 共 12 页 一、任务描述 基于 MPI 和 OpenMP，分别实现矩阵向量乘法的并行化。对实现的并行程序进行 正确性测试和性能测试，并对测试结果进行分析。 二、矩阵向量乘法串行算法描述与分析 1. 串行算法描述 在线性代数中，矩阵和向量的乘法是将每行矩阵的每个元素乘以向量中的每 个元素，得到一个新的向量，要求矩阵是 N*N 阶，向量是 N 阶，这样相乘后， 得到一个新的 N 阶向量。 利用串行算法，设置循环，让矩阵中的每一行的元素乘以完向量的每个元素 后得到一个数值再进行下一行的乘法，一直到最后一行的乘法结束，得到新 的向量。 2. 空间复杂度分析 对于 N 阶的矩阵向量乘法，A*b=x，定义数据类型为 long，则需要的存储空 间为（N2+2*N）*4 Byte 。 （矩阵数：N2+向量数 N+结果 N） 3. 时间复杂度分析 对于 N 阶的矩阵向量乘法，A*b=x，需要串行算法执行的次数为：N2*(N-1) 三、矩阵向量乘法的并行化 （一）基于 MPI 的矩阵向量的并行化 1. 并行策略（含图示） 因为矩阵乘以向量，每行的乘法是相互独立的，所以可以把 N 阶矩阵按行平 均分配给各个进程，让每个进程分别处理分配给它的数据块。 矩阵向量乘法的并行化 2016 年 3 月 31 日 第 3 页 共 12 页 2. 并行算法描述 先为程序指定阶数，然后用随机数生成 N 阶方阵和向量，采用静态均匀负载， 为每个处理器分配相同数量的数组元素，做到负载相对比较均衡（由于可能 存在 0 元素，使得负载相对有些偏差） 。然后把 N 阶方阵和向量显示出来，做 MPI 静态并行计算，然后将得出的结果显示出来 3. 空间复杂度分析 设进程数为 n，数据类型为 long，则 N 阶矩阵向量乘法的所需的空间为： N2+n*N+N， （矩阵空间 N2+n 倍的 b 向量空间 n*N+结果 N） 4. 时间复杂度分析 假设负载均衡，假设最小的划分块大于等于矩阵的一行，由于将行分块划分 给各个进程，所以整体的时间是 1/n 倍的串行算法的时间复杂度，即 1/n*N2*(N-1) （二）基于 OpenMP 的矩阵向量的并行化 1. 并行策略（含图示） 与 MPI 并行策略类似，把矩阵按行分块，与向量相乘，但是可以采用更为灵 活的池技术动态调用，更加充分利用了计算资源。 矩阵向量乘法的并行化 2016 年 3 月 31 日 第 4 页 共 12 页 2. 并行算法描述 设定矩阵和向量的阶数，这里指定为 20000 阶，随机生成矩阵和向量，用户 设置程序开启的线程数，然后调用 OpenMP 函数让程序自动将 for 语句进行 并行，然后记录计算时间，最后将所用时间显示出来 3. 空间复杂度分析 设线程数为 n ，则空间复杂度与 MPI 程序的空间复杂度相同，即 N2+n*N+N 4. 时间复杂度分析 由于采用了池技术动态调用，所以时间复杂度无法精确计算，矩阵如果是稀 疏矩阵则需要的时间相对较短，如果是稠密矩阵则相对较长。 四、关键源代码段 （一）MPI 程序的关键源代码段 MPI_Init( MPI_Comm_rank(MPI_COMM_WORLD, MPI_Comm_size(MPI_COMM_WORLD, if (my_rank = 0) printf(“输入数组（ n*n）的 nn“); scanf(“%d“, start_t = MPI_Wtime(); m= (int *)malloc(sizeof(int)*number*number); y = (int *)malloc(sizeof(int)*number); for(i=0;inumber;i+) for(j=0;jnumber;j+) mj*number+i=rand()%20+1; for(i=0;inumber;i+) yi=rand()%20+1; 矩阵向量乘法的并行化 2016 年 3 月 31 日 第 5 页 共 12 页 MPI_Barrier(MPI_COMM_WORLD); MPI_Bcast( x = (int *)malloc(sizeof(int)*number*number/comm_sz); y1= (int *)malloc(sizeof(int)*number/comm_sz); z1= (int *)malloc(sizeof(int)*number); MPI_Scatter(m,number*number/comm_sz,MPI_INT,x,number*number/comm_sz,M PI_INT,0,MPI_COMM_WORLD); MPI_Scatter(y,number/comm_sz,MPI_INT,y1,number/comm_sz,MPI_INT,0,MPI _COMM_WORLD); z= (int *)malloc(sizeof(int)*number); for(j=0;jnumber;j+) zj=0; for(i=0;inumber;i+) for(j=0;jnumber/comm_sz;j+) zi+=xi+number*j*y1j; MPI_Reduce(z,z1,number,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD); if(my_rank=0) for(j=0;jnumber;j+) printf(“z1%d=%d n“,j,z1j); end_t= MPI_Wtime(); 矩阵向量乘法的并行化 2016 年 3 月 31 日 第 6 页 共 12 页 printf( “ It took %f secondsn“,end_t-start_t); MPI_Finalize(); return 0; （二）OpenMP 程序的关键源代码段 1. 指导语句 1： omp_set_num_threads(num_thread); 设置线程数 2. 指导语句 2： #pragma omp parallel shared(a,b,c) private(i,j,k) 调用 OpenMP 函数 3. 指导语句 3： #pragma omp for schedule(dynamic) 动态调用 源代码： #include “stdafx.h“ #include“omp.h“ #include“stdio.h“ #include“time.h“ #define NN 20000 int aNNNN,bNN1; long long cNN1; void solve(int n,int num_thread) int i,j,t,k,time; clock_t startTime,endTime; /long long sum; omp_set_num_threads(num_thread); 矩阵向量乘法的并行化 2016 年 3 月 31 日 第 7 页 共 12 页 for(i=0;in;i+)/对矩阵 a 和矩阵 b 进行初始化 t=i+1; for(j=0;jn;j+) aij=t+; bi1=t; startTime=clock(); #pragma omp parallel shared(a,b,c) private(i,j,k) #pragma omp for schedule(dynamic) for(i=0;in;i+) ci1=0; for(k=0;kn;k+) ci1+=aik*bk1; endTime=clock(); time=endTime-startTime; printf(“time=%dmsn“,time); int _tmain(int argc, _TCHAR* argv) int n, num_thread; 矩阵向量乘法的并行化 2016 年 3 月 31 日 第 8 页 共 12 页 printf(“input n and num_thread:n“); while(scanf(“%d%d“, printf(“input n and num_thread:n“); return 0; 五、程序运行测试与分析 （一）MPI 程序的测试与分析 1. 测试环境简介 硬件： 软件：Visual Studio 2010 2. 正确性测试结果 矩阵向量乘法的并行化 2016 年 3 月 31 日 第 9 页 共 12 页 3. 性能测试结果 随着阶数增大，所花时间也增大；但是相比串行算法所花时间在一定范围内 随着进程数增多而降低的更为明显。进程太多的时候会出现饱和。 4. 分析 在阶数很小的情况下，由于并行计算的通信开销也占用了一定的系统资源， 所以相比串行计算所减少的时间不是很明显甚至会不如串行算法，但是随着阶数 增加，并行计算会大大减少程序所运行的时间，并且进程数越多越快，但是当进 程数太多的时候，由于是单电脑多核 CPU 运行，所以会在硬件上出现瓶颈，减少 的时间并无太大变化，反而有可能因为增加了通信开销而使效率减小。 （二）OpenMP 程序的测试与分析 1. 测试环境简介 硬件： 软件：Visual Studio 2010 2. 正确性测试结果（拷屏） 矩阵向量乘法的并行化 2016 年 3 月 31 日 第 10 页 共 12 页 3. 性能测试结果 4. 分析 由于在程序中指定了阶数为 20000 阶，可以看出，线程数在 32 的时候，相对 其他的线程数最为经济，到了 128 个线程的时候，减少的时间并不多，到了 300 基本没变化，一个原因是因为单电脑运行存在硬件瓶颈，还有一个原因是 因为指定的阶数为 20000 阶，由于是动态调用，所以当开到 300 个线程的时 矩阵向量乘法的并行化 2016 年 3 月 31 日 第 11 页 共 12 页 候，有可能浪费了很多的计算资源。 六、实验报告总结 OpenMP 是针对多核/多 CPU 并行计算而设计的工具，其实现方法较为 简单，只要在要并行的部分进行标注即可，具有内存开销小、编程语句简洁 直观的优点。 MPI 是多主机联网协作进行并行计算的工具，也可以用于单主机上多核/ 多 CPU 的并行计算，不过效率低下。其优点是能协调多台主机共同工作，但 其缺点也很明显，即并行效率较低、内存开销大、不直观、编程过程复杂（ 需要协