mpi冒泡排序行化.docVIP

北京科技大学?计算机与通信工程学院 实 验 报 告 实验名称: 冒泡排序的并行化 专 业： 计算机科学与技术 班 级： 计1203 学 号： 座机电话号码 指导教师： 李建江 实验成绩： 实验地点： 机电楼301 实验时间： 2015年4月8日 一、实验目的与实验要求 1、实验目的 （1）学会将串行程序改为并行程序。 3 学会openmp的配置。 （4）mpi与openmp之间的比较。 2、实验要求 （1将串行冒泡程序局部并行化，以降低时间消耗。 二、实验设备（环境）及要求 Vs2013，mpich2 三、实验内容与步骤 1、实验一 mpi并行 （1）实验内容 1、写出一个冒泡排序程序，求出其时间复杂度，并运行得到相应的时间消耗。 2、将冒泡程序改为mpi并行程序：将全部需要排序的数分成4等份，分给四个进程一起冒泡，最后将所得的结果归到一个进程，进行归并排序，得到结果，得到时间消耗。算出时间复杂度。 3、对得出的结果进行讨论与分析。 （2）主要步骤 1、串行冒泡程序 时间复杂度：取所要排序的数的个数为n个，时间复杂度为n*n/2。 代码实现 // maopao.cpp : 定义控制台应用程序的入口点。 // #include stdafx.h #include stdlib.h #includetime.h const int ARRAY_SIZE 120000; int main int argc, char* argv[] int zongshu[ARRAY_SIZE]; srand 10086 ; time_t now_time, end_time; for int i 0; i ARRAY_SIZE; i++ zongshu[i] rand ; now_time time NULL ; for int i 0; i ARRAY_SIZE; i++ for int j ARRAY_SIZE - 1; j i; j-- if zongshu[j] zongshu[j - 1] int z zongshu[j - 1]; zongshu[j - 1] zongshu[j]; zongshu[j] z; end_time time NULL ; long shijian end_time - now_time; for int i 0; i ARRAY_SIZE; i++ printf %d , zongshu[i] ; printf 所用时间：%ld,shijian ; while true ; 2、并行程序 时间复杂度：取所要排序的数的个数为n个，进程数为m个。时间复杂度： （n/m）* n/m /2 +n+4*n。 代码实现 // MPITest.cpp : 定义控制台应用程序的入口点。 // #include stdafx.h #include mpi.h #include #include #include stdlib.h #define SIZE 4//进程数 const int ARRAY_SIZE 30000;//每个进程分配的个数 int shuzu[SIZE][ARRAY_SIZE]; int zonghanshu[SIZE][ARRAY_SIZE]; double endwtime; void Scatter_1 int ; int main int argc, char *argv[] int myid; MPI_Init argc, argv ; MPI_Comm_rank MPI_COMM_WORLD, myid ; Scatter_1 myid ; MPI_Finalize ; void Scatter_1 int myid int numtasks; srand 10086 ; for int i 0; i SIZE; i++ for int j 0; j ARRAY_SIZE; j++ shuzu[i][j] rand ; //随机生成数组 int xiaopaixu[ARRAY_SIZE]; double startwtime MPI_Wtime ; MPI_Comm_size MPI_COMM_WORLD, numtasks ; if numtasks SIZE MPI_Scatter shuzu, ARRAY_SIZE, MPI_INT, xiaopaixu, ARRAY_SIZE, MPI_INT, 0, MPI_COMM_WORLD ; for int i 0;