《mpi冒泡排序并行化》由会员分享，可在线阅读，更多相关《mpi冒泡排序并行化（12页珍藏版）》请在金锄头文库上搜索。
1、北京科技大学计算机与通信工程学院实验报告实验名称：冒泡排序的并行化学生姓名：专 业：计算机科学与技术班 级： 计1203学 号: 指导教师：实验成绩：实验地点： 机电楼301实验时间：2015年4月8日一、实验目的与实验要求1、实验目的（1）学会将串行程序改为并行程序。（2）学会 mpich2 的使用。（3）学会 openmp 的配置。（4）mpi 与 openmp 之间的比较。2、实验要求（1）将串行冒泡程序局部并行化，以降低时间消耗。（2） 理论上求出时间复杂度之比，根据结果得出时间消耗之比，进行比对分析。二、实验设备（环境）及要求Vs2013，mpich2三、实验内容与步骤1、实验一 m
2、pi 并行（1）实验内容1、写出一个冒泡排序程序，求出其时间复杂度，并运行得到相应的时间消耗。2、将冒泡程序改为mpi并行程序：将全部需要排序的数分成4等份，分给四个进程一起 冒泡，最后将所得的结果归到一个进程，进行归并排序，得到结果，得到时间消耗。算出 时间复杂度。3、对得出的结果进行讨论与分析。（2）主要步骤1、串行冒泡程序时间复杂度：取所要排序的数的个数为n个，时间复杂度为n*n/2。代码实现：/ maopao.cpp :定义控制台应用程序的入口点。/#include stdafx.h#include stdlib.h#include ti me.hconst int ARRAY_SIZ
3、E = 120000;int main(int argc, char* argv )int zongshuARRAY_SIZE;srand(10086);time_t now_time, end_time;for (in t i = 0; i ARRAY_SIZE; i+)zongshui=rand();now _time = ti me(NULL);for (int i = 0; i i; j)if (zongshuj = zongshuj - 1)int z = zongshuj - 1; zongshuj - 1 = zongshuj; zongshuj = z;end _time =
4、ti me(NULL);long shijian = end_time now_time;for (int i = 0; i #includemath.h#include stdlib.h#define SIZE 4/进程数const int ARRAY_SIZE = 30000;/每个进程分配的个数int shuzuSIZEARRAY_SIZE;int zonghanshuSIZEARRAY_SIZE;double endwtime;void Sca tter_ 1(in t);int main(int argc, char *argv )int myid;MPI_Init(&argc, &
5、 rg)；MPI_Comm_rank(MPI_COMM_WORLD, &myid);Sca tter_1 (myid);MPI_Finalize();void Scatter_ 1(int myi()int numtasks;srand(10086);for (int i = 0; i SIZE; i+)for (in t j = 0; j ARRAY_SIZE; j+) shuzuij = rand();/随机生成数组int xiaopaixuARRAY_SIZE;double startwtime = MPI_W ti me();MPI_Comm_size(MPI_C0MM_W0RLD,
6、&numtasks);if (nu mt asks = SIZE)MPI_Scatter(shuzu, ARRAY_SIZE, MPI_INT, xiaopaixu, ARRAY_SIZE, MPI_INT, 0, MPI_C0MM_W0RLD);for (in t i = 0; i i; j)if (xiaopaixuj = xiaopaixuj - 1)int z = xiaopaixuj - 1; xiaopaixuj - 1 = xiaopaixuj;xiaopaixuj = z;/每个进程里的冒泡排序MPI_Gather(xiaopaixu, ARRAY_SIZE, MPI_INT,
7、 zonghanshu, ARRAY_SIZE, MPI_INT, 0, MPI_C0MM_W0RLD);int timeSIZE;for (int i = 0; i = 0; j)k =ARRAY_SIZE)(int k = 0; if (tim ekak=0；elseak=zonghanshukARRAY_SIZE t imek 1;int x = a0;for (in t i = 1; iSIZE; i+) if (aix)x = ai;for (int n = 0; n SIZE; n+) if (x = an)tim en = tim en + 1; break;zongpaixu2
8、j = x;endw time = MPI_W time();if (myid);elsefor (int i = 0; i SIZE*ARRAY_SIZE; i+)prin tf (%d , zongpaixu2i);if (myid);elseprintf(wall clock time=% fn, endwtime startwtime);2、实验2在实验一的基础上将程序改为 openmp。代码实现：(水平不高，写的程序通用性不好，只写了四线程的) / Openmp.cpp :定义控制台应用程序的入口点。/#include stdafx.h#includestdio.h#includem
9、ath.h#include stdlib.h#include ti me.h#includeomp.h#define SIZE 4const int ARRAY_SIZE = 12000;int shuzuSIZEARRAY_SIZE;int xiaopaixu1ARRAY_SIZE;int xiaopaixu2ARRAY_SIZE;int xiaopaixu3ARRAY_SIZE;int xiaopaixu4ARRAY_SIZE;int zonghanshuSIZEARRAY_SIZE;int zongpaixuARRAY_SIZE*SIZE;void xiaohansu(int *A, i
10、nt l, int u)for (in t i = l; iu; i+)for (in t j = u - 1; ji; j)if (Aj = Aj - 1)int z = Aj - 1;Aj - 1 = Aj;Aj = z;/每个线程排序int main(int argc, char* argv )int t1, t2;int i;int id;clock_t now_time, end_time; srand(10086);for (int i = 0; i SIZE; i+)for (in T j 二 0; j ARRAY_SIZE; j+) shuzuij = rand();/随机生成
11、数组now _Time = clock();ftpragma omp parallel defau1T(none) shared(shuzu,xiaopaixul,xiaopaixu2,xiaopaixu3,xiaopaixu4,ARRAY_SIZE) privaTe (i)#pragma omp forfor (i = 0; i ARRAY_SIZE; i+)/这个fo r循环是并行的，将数组分为四份 xiaopaixuli = shuzu0i;xiaopaixu2i = shuzuli;xiaopaixu3i = shuzu2i; xiaopaixu4i = shuzu3i;#pragma
12、 omp parallel defau1T(none) shared(xiaopaixul,xiaopaixu2,xiaopaixu3,xiaopaixu4,ARRAY_SIZE)#pragma omp parallel secTions#pragma omp secTionxiaohansu(xiaopaixul, 0, ARRAY_SIZE-1);/排序#pragma omp secTion xiaohansu(xiaopaixu2, 0, ARRAY_SIZE);#pragma omp secTionxiaohansu(xiaopaixu3, 0, ARRAY_SIZE);#pragma omp secTionxiaohansu(xiaopaixu4, 0, ARRAY_SIZE);for (i = 0; i ARRAY_SIZE; i+) /合到一份zonghanshu0i=xiaopaixu1i;zonghanshu1i=xiaopaixu2i;zonghanshu2i=xiaopaixu3i;zonghanshu3i=xiao
