mpi冒泡排序并行化教學提綱

1、mpi冒泡排序并行化精品文檔北京科技大學計算機與通信工程學院實驗報告實驗名稱：冒泡排序的并行化學生姓名： 朱帥專業(yè)：計算機科學與技術(shù)班級： 計1203學 號: 41255072指導教師： 李建江實驗成績：實驗地點： 機的樓301實驗時間：2022年4月8日收集于網(wǎng)絡(luò),如有侵權(quán)請聯(lián)系治理員刪除精品文檔一、實驗目的與實驗要求1、實驗目的(1)學會將串行程序改為并行程序.(2)學會mpich2的使用.學會openmp的配置.(4) mpi Op openmp之間的比擬.2、實驗要求(1)將串行冒泡程序局部并行化,以降低時間消耗.理論上求出時間復雜度之比,根據(jù)結(jié)果得出時間消耗之比,進行比對分析.二、實

2、驗設(shè)備(環(huán)境)及要求Vs2022, mpich2三、實驗內(nèi)容與步驟1、實驗一 mpi并行(1)實驗內(nèi)容1、寫出一個冒泡排序程序,求出其時間復雜度,并運行得到相應的時間消耗.2、將冒泡程序改為mpi并行程序：將全部需要排序的數(shù)分成 4等份,分給四個進程一起冒泡,最后將所得的結(jié)果歸到一個進程,進行歸并排序,得到結(jié)果,得到時間消耗.算出時間復雜度.3、對得出的結(jié)果進行討論與分析.(2)主要步驟收集于網(wǎng)絡(luò),如有侵權(quán)請聯(lián)系治理員刪除精品文檔n*n/2.1、用行冒泡程序時間復雜度：取所要排序的數(shù)的個數(shù)為n個,時間復雜度為代碼實現(xiàn)：/ maopao.cpp :定義限制臺應用程序的入口點./#include

3、"stdafx.h"#include "stdlib.h"#include "time.h" |const int ARRAY_SIZE = 120000;int main( int argc, char * argv 口)int zongshuARRAY_SIZE;srand(10086);time_t now_time, end_time;for ( int i = 0; i < ARRAY SIZE; i+) zongshui=rand();now_time = time( NULL;for ( int i = 0; i

4、< ARRAY_SIZE; i+)for ( int j = ARRAY_SIZE - 1; j > i; j-)if (zongshuj <= zongshuj - 1)int z = zongshuj - 1;zongshuj - 1 = zongshuj; zongshuj = z;end_time = time( NULL;long shijian = end_time - now_time;for ( int i = 0; i <ARRAY_SIZE; i+) printf( "%d ", zongshui);printf("所用

5、時間：%ld",shijian);while ( true );收集于網(wǎng)絡(luò),如有侵權(quán)請聯(lián)系治理員刪除精品文檔2、并行程序時間復雜度：取所要排序的數(shù)的個數(shù)為 n個,進程數(shù)為m個.時間復雜度:(n/m) *(n/m)/2)+n+4*n.代碼實現(xiàn)：/ MPITest.cpp :定義限制臺應用程序的入口點./#include "stdafx.h"#include "mpi.h" |#include <stdio.h>#include <math.h>#include "stdlib.h"#define SIZ

6、E 4/ 進程數(shù)const int ARRAY_SIZE = 30000;/每個進程分配的個數(shù) int shuzu SIZEARRAY_SIZE;int zonghanshu SIZEARRAY_SIZE;double endwtime;void Scatter_1( int );int main( int argc , char * argv )int myid;MPI_Init(& argc, & argv);MPI_Comm_ranMMPI_COMM_WORLByid);Scatter_1(myid); |MPI_Finalize();)void Scatter_1( i

7、nt myid) int numtasks; srand(10086);for ( int i = 0; i < SIZE; i+)for ( int j = 0; j < ARRAY_SIZE; j+) shuzuij = rand(); |) ) /隨機生成數(shù)組 int xiaopaixuARRAY_SIZE; double startwtime = MPI_Wtime(); MPI_Comm_sizeMPI_COMM_WORLDjmtasks); if (numtasks = SIZE)收集于網(wǎng)絡(luò),如有侵權(quán)請聯(lián)系治理員刪除精品文檔MPI_Scatter(shuzu, ARRA

8、Y_SIZE, MPI_INT, xiaopaixu, ARRAY_SIZE, MPI_INT, 0, MPI_COMM_WORLDfor ( int i = 0; i <ARRAY_SIZE; i+)for ( int j = ARRAY_SIZE - 1; j > i; j-)if (xiaopaixuj <= xiaopaixuj - 1)int z = xiaopaixuj - 1;xiaopaixuj - 1 = xiaopaixuj; xiaopaixuj = z;) ) /每個進程里的冒泡排序| MPI_Gather(xiaopaixu, ARRAY_SIZE,

9、 MPI_INT, zonghanshu, ARRAY_SIZE, MPI_INT, 0, MPI_COMM_WO)RLD int time SIZE;for ( int i = 0; i < SIZE; i+) timei = 0;int a SIZE;int zongpaixu2ARRAY_SIZE* SIZE;for ( int j = ARRAY_SIZE*SIZE - 1; j >= 0; j-)for ( int k = 0; k < SIZE; k+)if (timek >= ARRAY_SIZE) ak = 0; else ak = zonghanshu

10、kARRAY_SIZE - timek - 1; int x = a0;for ( int i = 1; i< SIZE; i+) if (ai>x)x = ai;for ( int n = 0; n < SIZE; n+) if (x = an)timen = timen + 1; break;zongpaixu2j = x;收集于網(wǎng)絡(luò),如有侵權(quán)請聯(lián)系治理員刪除精品文檔)endwtime = MPI_Wtime();if ( myid);elsefor ( int i = 0; i < SIZE*ARRAY_SIZE; i+)printf( "%d &quo

11、t;, zongpaixu2i);)if ( myid);elseprintf( "wall clock time=% fn" , endwtime - startwtime);)2、實驗2在實驗一的根底上將程序改為openmpo代碼實現(xiàn)：(水平不高,寫的程序通用性不好,只寫了四線程的)/ Openmp.cpp :定義限制臺應用程序的入口點./#include"stdafx.h"#include<stdio.h>#include<math.h>#include"stdlib.h"#include"ti

12、me.h"#include<omp.h>#defineSIZE 4const int ARRAY_SIZE = 12000;int shuzu SIZEARRAY_SIZE;int xiaopaixu1ARRAY_SIZE;int xiaopaixu2ARRAY_SIZE;int xiaopaixu3ARRAY_SIZE;int xiaopaixu4ARRAY_SIZE;int zonghanshu SIZEARRAY_SIZE;l , int u)u; i+)u - 1; j > i; j-)int zongpaixuARRAY_SIZE* SIZE;void x

13、iaohansu( int * A, intfor ( int i = l; i < for ( int j =if ( Aj <= Aj - 1)收集于網(wǎng)絡(luò),如有侵權(quán)請聯(lián)系治理員刪除精品文檔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 ( int j = 0; j <

14、ARRAY_SIZE; j+) shuzuij = rand();)/隨機生成數(shù)組now_time = clock();private (i),將數(shù)組分為四份#pragma omp parallel default (none)shared(shuzu,xiaopaixu1,xiaopaixu2,xiaopaixu3,xiaopaixu4,ARRAY_SIZE)#pragma omp forfor (i = 0; i < ARRAY_SIZE; i+)/ 這個 for 循環(huán)是并行的xiaopaixu1i = shuzu0i;xiaopaixu2i = shuzu1i;xiaopaixu3

15、i = shuzu2i;xiaopaixu4i = shuzu3i;)#pragma omp parallel default (none)shared(xiaopaixu1,xiaopaixu2,xiaopaixu3,xiaopaixu4,ARRAY_SIZE)#pragma omp parallel sections#pragma omp sectionxiaohansu(xiaopaixu1, 0, ARRAY_SIZE-1); / 排序#pragma omp section收集于網(wǎng)絡(luò),如有侵權(quán)請聯(lián)系治理員刪除精品文檔xiaohansu(xiaopaixu2, 0, ARRAY_SIZE

16、);#pragma omp sectionxiaohansu(xiaopaixu3, 0, ARRAY_SIZE);#pragma omp sectionxiaohansu(xiaopaixu4, 0, ARRAY_SIZE);for (i = 0; i < ARRAY_SIZE; i+)/ 合至U一份zonghanshu0i=xiaopaixu1i;zonghanshu1i=xiaopaixu2i;zonghanshu2i=xiaopaixu3i;zonghanshu3i=xiaopaixu4i; int time SIZE;for ( int i = 0; i < SIZE;

17、i+) timei = 0;int a SIZE;for ( int j = ARRAY_SIZE*SIZE - 1; j >= 0; j-)for ( int k = 0; k < SIZE; k+)if (timek >= ARRAY_SIZE) ak = 0; else ak = zonghanshukARRAY_SIZE - timek - 1; int x = a0;for ( int i = 1; i< SIZE; i+) if (ai>x)x = ai; for ( int n = 0; n < SIZE; n+)if (x = an)time

18、n = timen + 1;break;收集于網(wǎng)絡(luò),如有侵權(quán)請聯(lián)系治理員刪除精品文檔zongpaixuj = x;)/歸并Iend_time = clock();double shijian = end_time - now_time;for ( int i = 0; i < SIZE*ARRAY_SIZE; i+)| printf( "%d ", zongpaixui);)printf("所用時間：lf" , shijian /CLK TCKwhile ( true );四：實驗結(jié)果與分析Mpi:用行H:birxinqX(rpi'iria

19、opaoa p. c xe3W685 3Z685 32GA6 32686 32&86 32&87 32&S7326B6 326B0 3268,修 修勺!269修勺2691 32491 3立石.之 32£.？ 312 3162 9京 322 32£93 32332fc9J 32C94 久匕94 NZJ94 22t9£ 32G9 32fc9? 32t932657 3Z617 3267 3Z617 32697 326?l 32691 326T9 326T9 326»9 32709 32700 32700 701 J2701 3S901

20、32701 32寵 1 舞作士 92901 3201 327B3 乳加口 3之？04 324 5S?®4 M 4 3270C 327BL 327UL 32加9 327UL 227的 3270!, 327% 3270b 327BG 327B(> 327«t 327U 3Z7W 3Z7U6 327tt? 3277 327tH 3EE8 32 必迪 32?的 32?那 32709 3270? 3270? ?±a 32ft.a a3fi?ia S35n 32711351132?1a 口之力2 5i?±a m2 32712 32712 S2713 32713

21、 32713 32713 32713 32714 2i714 A2714 22714 32714 2271 32713Z?lh 32717 271? 32717 32718 E7lS 32718 3271 32717 3Z7JV 3Z7IT 3272n 32729 3272a 32721 33721 32721 32721 32721 32722 32722 32723 32723 32723 32J 32724 22724 S3734 32724 32724 3272!i 32721 3272C 3»?2<>3272 327S& 327133Z7Zt 3Z77f

22、c 327ZE 327Zt 3226 32m 32727 3Z-JZ8 327r8 327Z 327?7 3273H J271W 730 3Z730 32730 32731 3273Z 3273Z 32733 33734 32734 32734 32734 32734 52735 制 J 32?3G 3272G 3273t 3273K J273K 327J7 32737 3273? J2?37 33737 3273S 32738 3273 3Z73? 3Z73? 32737 3Z7+0 3Z7A0 327B 3Z741 3Z741 3Z741 32741 32741 3Z741 32742 ?

23、42 3NKZ 32742 32742 3271Z 3274Z 3274J 33743 327-13 327+1 32744 32744 事NF W ；12174G 1274r 丁2745 1S74E 3274.15717 H2717 127? 1277 3274T 7274fl 工2743274W 3274M 32749 32719 32KtM 3270 3工？5H 327» ；1271H 327SH 32751 32751 3275Z 752 3275JI 3275? 32752 327S3 32753 32754 3 2754 32754 32755 32755 3 2VSS

24、32 756 32 b 337S6 33TC& 32居？ 327 J2W J2757 32W 32TCS 3275B 32TC9 32TC9 3fKf 31VG 327fre 3Z740 327«B 327fii 32761 32761 32761 32?fr2 327&2 32762 32K2 32763 327fi)m 327&3 32763 32V&3 3274 327G4 3 276 3 276S (2765 32*765 32?fe5 3 2765 32 76 32 5 327Gfi 327fc7 327S7 所用時閶出37Mpi收集于網(wǎng)絡(luò),

25、如有侵權(quán)請聯(lián)系治理員刪除精品文檔bflf 32&B9 32&I9 3267B32fi9L 32b9L 32672 326V2 32672 3Z6V2 326f2 32672 32693 32693 KG打 32£93 32493 32693 轂£94 326M 32&V4 32696 326 32697 326»? 126V7 Slfel7 3267 3Z&97 328326f> 32b98 3269f 3299 32699 3270B 32788 327M 32 701 327ft1 327B1 32781 32701 32

26、702 32703 32703 32783 32783 327fM $Z?H4 327M 327H 4 J2VMS 327M1>327®S 2705 J2?H5 327EK 327WS 327«fe 327M6 327Uf> £?» 322雕327A6 蕤 1m 327A7 32W7 32707 3270ft 327M32709 9370? 3270V 32709 32W 323271M 3271» 32710 32711 32711 12711 3271L J2712 2712 32712 JZ712 3Z712 3Z71 2 3

27、2712 32712 H713 32713 32713 32713 3Z?U 32?H 32714 3Z714 32714 32?H 32715 弁力總 JS71C ifi7i9 3i?17 52717 329lft 3271i a2?tfl 嵬3571* 位力中 33719 1272« 曼 72U 3272U 3272W 22721 32721 33721 32721 32721 32722 2222 32722 12723 32722 3272 3 32724 33724 32724 3 24 32724 3372S 3272S 3272S 3272 S n725 32725 3

28、2725 32726 7272b 3Z72E 32726 32726 3272b 3272G 32727 3272b 32YZ8 3272? 3272? 3273b 3273M 32 73fl 32730 32730 32931 39732 32732 32731 32734 32734 32734 32TO4 32再4 32735 3273 £ 1272L. 3273t 2273G 3272L 3273& J2727 32727 32737 a2727 3237 32718 32?!1 32總 JZ73? 32735 12737 3Z710 3Z7« 3Z740

29、327-11 32741 32?41 32741 32711 32711 12742 32 742 32742 32742 32742 32742 32742 32743 32743 32743 32744 32744 32744 32745 32.74 £ 3274E 3274S 32745 3274G SSTMG 3274£ 32747 32747 32747 3274? 32747 32740 32748 12748 3Z74B 3274? 3Z7? 3Z7S® 327E0 32758 327S0 3270 327S3 327S1 32751 327S2 3

30、2 ?52 32752 32753 32752 32753 理3 32754 32754 327B4 32755 32755 跪756 337SC 3Z75 t 327E&327E7 327 32757 32TC7 327E7 32756 3275 8 32S 32TC8 32759 32759J27t0 32%M 52?tU 227tl 327t1 32?tl 22X1 327t2 327t2 327t2 32XZ 32'3 32*?£3 33 7fi1 32763 32763 32T&3 32764 J2754 32764 3 2765 32765 32

31、765 327fi5 JZ765 3Z766 32 三含加6 3戈%7“all ulwclt 七五,e="AlgS&El.F1.2萬2.4萬3.6萬4.8萬6.0萬7.2萬用行秒0.4411.7663.9516.87710.46914.6876線秒0.0290.1080.2420.4350.6560.9404線秒0.0350.1510.3390.6150.9691.4092線秒0.1190.5021.1082.0403.1214.516從表中可以看出4線程的時候,并行程序的速度是用行程序速度的十倍之多,而理論上大概8倍.這就跟改的程序有關(guān).在并行程序中,最后采用的是 歸并,由

32、此,發(fā)生了這些奇妙的情況：實那么本身的算法就比冒泡優(yōu)一些,但又 不能只采用冒泡算法,那樣在最后又來個冒泡,具程序就沒有意義了.Openmp收集于網(wǎng)絡(luò),如有侵權(quán)請聯(lián)系治理員刪除精品文檔H :binxi ng o pn0pe nmebvpermp. ese3第舞 3asi5 3«S1635U 3061M 30533 三4日 30548 305-42 19543 才酹立 3必&厘 3Q579 3«SS 305VI 3055 3 30601 3酶叫 14613 3W17 3«1« 3061> 396ZB 3W20 3*«? 3063 3

33、38£2M 3BA31 3防,團 3iK4H 30C-4B 3EM48 3MES 3B6&B 3M58 3B6&0 30(55 9BMJ 30Ml 1«*3 ?W3 3M>g 3M*7 3W77 >V7» 7*775 JE芋 nE,尋孑 30767 IffTPV 3V7VO 3H ?H5 ：lH7HM IHTB/ ：rB7R3 IWV ?W77 1W79G 3F7?6 3Cm*. JHTVt:MW1 邑JWff.9 SBBfa? JMfr?芋咖3tM 占需 3 電* if ¥ JfcHW JW721患者J4W4S IMt?l&

34、#187;9tb 3B99C 30999 2B9 79 309flB 3H9II J(N9S 3M95 3099t 21MU7 31KB LK1 11K2 31 kz 3107S aim- aim iims nee3 aina 3i«?a 3iB9» 31al7 jib?h 3ii» 311 ib juJ 9 91110 311±£ 911.3C 311S4 31 L4fl 1142 3114E iLITA 31284 91 fM 3121 31217 3119G 3123b 31226 312Z& 31233 3127 3i260 3

35、1272 312？3 3127T 31Z7T 31292 31Z95 312H 31 29ft 3!2*9 315?9制加 31391 313S1 31322 31J23： 31 羽&JI J90 313M 014 帆 打剜E DH2& 1H31 31 d5fl 31463 314B3 3146H 3H71 MW 31196 JI4BI 31-IM> lt49B 3M9I 31 £M 11S19 11 31530 31£lft 11S31 31537 31S.£i31SB4 315H5 liteti 31&K 31M 3137 31637 31M7 31fi<? 31W 316SA 31«