并行报告双面

1、6. 附录6.1 基于OpenMP的并行程序设计6.1.1 代码及注释#include stdafx.h#include #include #include #include #include #define NUM_THREADS 2#define SIZE 100int xh_aSIZE,xh_dSIZE,xh_bSIZE/2,xh_cSIZE/2;void quick_sort(int xh_s, int l, int r)if (l r)int i = l, j = r, x = xh_sl;while (i j)while(i = x) / 从右向左找第一个小于x的数j-; if(i

2、 j) xh_si+ = xh_sj;while(i j & xh_si x) / 从左向右找第一个大于等于x的数i+; if(i j) xh_sj- = xh_si;xh_si = x;quick_sort(xh_s, l, i - 1); / 递归调用quick_sort(xh_s, i + 1, r);int _tmain(int argc, _TCHAR* argv)printf(%d个随机数的排序n,SIZE);omp_set_num_threads(2);int i=0,j=0,k=0,l=0;long n=SIZE/2;srand(unsigned)time(NULL); /初始

3、化随机数种子 for (i = 0; i SIZE; i+)xh_ai = rand(); clock_t xh_t1,xh_t2;#pragma omp parallel for private(i)for(i=0;in;i+)xh_bi=xh_ai;xh_ci=xh_ai+n; xh_t1=clock();#pragma omp parallel sections /快速排序的并行，分两个线程 #pragma omp sectionquick_sort(xh_b, 0, n-1);/对b排序 #pragma omp sectionquick_sort(xh_c, 0, n-1);/对c排序

4、 while(ln&jn)if(xh_blxh_cj)xh_dk=xh_bl;l+;k+;else xh_dk=xh_cj;j+;k+;while(ln)xh_dk=xh_bl;l+;k+;while(jn)xh_dk=xh_cj;j+;k+;xh_t2=clock();printf(parallel time=%dn,(xh_t2-xh_t1); xh_t1=clock();quick_sort(xh_a, 0, SIZE- 1); xh_t2=clock();printf(serial time=%dn,(xh_t2-xh_t1);system(pause);return 0;6.1.2

5、执行结果截图（体现串行时间、并行时间和加速比）（1）小数据量验证正确性的执行结果图 1（2）大数据量获得较好加速比的执行结果图 2图 36.1.3 遇到的问题及解决方案（1）问题一错误代码及后果while(in&jn)if(xh_bixh_cj)xh_dk=xh_bi;i+;k+;while(in)xh_dk=xh_bi;i+;k+;正确代码while(ln&jn) if(xh_blxh_cj) xh_dk=xh_bl;l+; k+;while(ln) xh_dk=xh_bl;l+; k+;分析错误的使用了共享变量i,因为i的值在前面已经赋过值，值不是0,使得i的值不是从0开始，使得排序数组的

6、靠后的几个随机数全变成了0，解决方法：重新给i赋值为0，或替换变量，或将归并排序封装成函数，然后调用。6.2 基于MPI的并行程序设计6.1.1 代码及注释（变量名 名字首字母 开头）#include stdafx.h#include #include mpi.h#include #include #include #define SIZE int xh_aSIZE,xh_dSIZE,xh_bSIZE/2,xh_cSIZE/2,xh_sSIZE/2;void quick_sort(int xh_s, int l, int r)if (l r)int i = l, j = r, x = xh_s

7、l;while (i j)while(i = x) / 从右向左找第一个小于x的数j-; if(i j) xh_si+ = xh_sj;while(i j & xh_si x) / 从左向右找第一个大于等于x的数i+; if(i j) xh_sj- = xh_si;xh_si = x;quick_sort(xh_s, l, i - 1); / 递归调用quick_sort(xh_s, i+1, r);void m_quick_sort(int xh_a,int myid, int l, int r) int m,i; m=r/2;if(myid=0)for(i=0;im;i+)xh_si=xh

8、_ai;if(myid=1)for(i=0;im;i+)xh_si=xh_ai+m;m=m-1;if (l m)int i = l, j = m, x = xh_sl;while (i j)while(i = x) / 从右向左找第一个小于x的数j-; if(i j) xh_si+ = xh_sj;while(i j & xh_si x) / 从左向右找第一个大于等于x的数i+; if(i j) xh_sj- = xh_si;xh_si = x;quick_sort(xh_s,l,i - 1); / 递归调用quick_sort(xh_s,i+1, m);m=m+1;void main(int

9、 argc,char *argv) int myid,numprocs; int m=SIZE; int n=SIZE/2; double startwtime,endwtime; int i=0,j=0,k=0,l=0; srand(unsigned)time(NULL); /初始化随机数种子 for (i = 0; iSIZE; i+) xh_ai = rand(); MPI_Status status; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&numprocs); MPI_Comm_rank(MPI_COMM_WORLD,

10、&myid); if(numprocs=1)startwtime=MPI_Wtime(); quick_sort(xh_a, 0, SIZE- 1); endwtime=MPI_Wtime(); printf(time=%fn,endwtime-startwtime); else if(numprocs=2) if(myid=0) printf(%d个随机数的排序n,SIZE); startwtime=MPI_Wtime(); MPI_Bcast(&m,1,MPI_INT,0,MPI_COMM_WORLD); MPI_Send(xh_a,SIZE,MPI_INT,1,99,MPI_COMM_W

11、ORLD); if(myid=1) MPI_Recv(xh_a,SIZE,MPI_INT,0,99,MPI_COMM_WORLD,&status); m_quick_sort(xh_a,myid, 0,SIZE);if(myid=1) for(i=0;iSIZE/2;i+)xh_ci=xh_si;MPI_Send(xh_c,SIZE/2,MPI_INT,0,99,MPI_COMM_WORLD); if(myid=0) for(i=0;iSIZE/2;i+)xh_bi=xh_si;MPI_Recv(xh_c,SIZE/2,MPI_INT,MPI_ANY_SOURCE,99,MPI_COMM_WO

12、RLD,&status);while(ln&jn)if(xh_blxh_cj)xh_dk=xh_bl;l+;k+;else xh_dk=xh_cj;j+;k+;while(ln)xh_dk=xh_bl;l+;k+;while(jn)xh_dk=xh_cj;j+;k+;/*for(i=0;iSIZE;i+)printf(%d ,xh_di);printf(n);*/endwtime=MPI_Wtime();printf(parallel time=%fn,endwtime-startwtime);startwtime=MPI_Wtime();if(myid=0)quick_sort(xh_a,

13、0, SIZE- 1);endwtime=MPI_Wtime();printf(serial time=%fn,endwtime-startwtime); else printf(线程数超出指定范围n);MPI_Finalize(); /结束计算 6.2.2 执行结果截图（体现串行时间、并行时间和加速比）（1）小数据量验证正确性的执行结果图 4（2）大数据量获得较好加速比的执行结果个数的快速排序，加速比是0./0.=1.98图 5个数的快速排序，加速比是4./1.=2.82图 66.2.3 遇到的问题及解决方案（1）问题一错误代码及后果 int m, i; m=r/2;if(myid=0)fo

14、r(i=0;im;i+)xh_si=xh_ai;if(myid=1)for(i=0;im;i+)xh_si=xh_ai+m;m=m-1;if (l m)xh_si = x;quick_sort(xh_s,l,i - 1); / 递归调用quick_sort(xh_s,i+1, m);正确代码int m, i; m=r/2;if(myid=0)for(i=0;im;i+)xh_si=xh_ai;if(myid=1)for(i=0;im;i+)xh_si=xh_ai+m;m=m-1;if (l m)xh_si = x;quick_sort(xh_s,l,i - 1); / 递归调用quick_so

15、rt(xh_s,i+1, m);m=m+1;分析变量m代表要排序数组长度的一半，由于数组从序号0开始，而在排序中需要m-1的值。排序结束后，必须要将m的值加1，才能将整个数组完整输出，否则会丢掉一个数。6.3 基于Java的并行程序设计6.3.1 代码及注释import java.util.Scanner;public class Quicksort extends Thread public int array; private int array1; private int array2; private int start; private int end; public Quickso

16、rt(int array,int start,int end) super(); this.array=array; this.start=start; this.end=end; public Quicksort(int array, int array1,int array2, int n) this.array = array; this.array1 = array1; this.array2 = array; public void run() quick_sort(array,start,end); public void quick_sort(int xh_s, int l, i

17、nt r ) if (l r) int i = l, j = r, x = xh_sl;while (i j)while(i = x) / 从右向左找第一个小于x的数j-; if(i j) xh_si+ = xh_sj;while(i j & xh_si x) / 从左向右找第一个大于等于x的数i+; if(i j) xh_sj- = xh_si;xh_si = x;quick_sort(xh_s, l, i-1 ); / 递归调用quick_sort(xh_s, i+1, r); public void divide(int xh_d, int xh_b, int xh_c, int n)

18、int j=0,l=0, k = 0; while (l n & j n) if (xh_bl xh_cj) xh_dk = xh_bl; l+; k+; else xh_dk = xh_cj; j+; k+; while (l n) xh_dk = xh_bl; l+; k+; while (j n) xh_dk = xh_cj; j+; k+; public static void main(String args) throws InterruptedException System.out.println(请输入要排序的个数); Scanner sc = new Scanner(Sys

19、tem.in);int size = sc.nextInt();int xh_a=new intsize;int xh_b=new intsize/2;int xh_c=new intsize/2;int xh_d=new intsize;int i;int len=size/2;for(i=0;isize;i+) xh_ai=(int)(Math.random()*10*size);/初始化数组 for(i=0;ilen;i+) xh_bi=xh_ai;xh_ci=xh_ai+len; /*for( i=0;isize;i+)System.out.print(xh_ai+ );System.

20、out.println();*/Quicksort thread1=new Quicksort(xh_b,0,len-1);Quicksort thread2=new Quicksort(xh_c,0,len-1);Quicksort thread=new Quicksort(xh_a,0,size-1);long startTime=System.currentTimeMillis();thread1.start();thread2.start();thread1.join();thread2.join();/*int j=0,k=0,l=0;while(llen&jlen)if(xh_bl

21、xh_cj)xh_dk=xh_bl;l+;k+;else xh_dk=xh_cj;j+;k+;while(llen)xh_dk=xh_bl;l+;k+;while(jlen)xh_dk=xh_cj;j+;k+;*/Quicksort thread3=new Quicksort(xh_d,xh_b,xh_c,len);thread3.divide(xh_d, xh_b, xh_c, len);long endTime=System.currentTimeMillis();System.out.println(并行时间=+(endTime-startTime);startTime=System.c

22、urrentTimeMillis();thread.start();thread.join();endTime=System.currentTimeMillis();System.out.println(串行时间=+(endTime-startTime);/*for( i=0;isize;i+)System.out.print(xh_ai+ );if(i%10=0&i!=0)System.out.println();System.out.println();for( i=0;isize;i+)System.out.print(xh_di+ );if(i%10=0&i!=0)System.out

23、.println(); */ 6.3.2 执行结果截图（体现串行时间、并行时间和加速比）（1）小数据量验证正确性的执行结果图 7（2）大数据量获得较好加速比的执行结果个数的快速排序，加速比是79/47=1.68 图 8个数的快速排序，加速比是 937/515=1.82 图 96.3.3 遇到的问题及解决方案（1）问题一错误代码及后果xh_ai=(int)(Math.random()*1000);/初始化数组 当产生的随机数达到以上时，程序会发生异常，发生堆栈溢出，使逻辑错误图 10正确代码xh_ai=(int)(Math.random()*size);/初始化数组分析size是用户输入的要产生

24、随机数的个数，用自身的个数作为随机数种子的范围，可避免上述错误。随机数的范围也会随着个数的增加而增加，降低数字的重复率。6.4 基于Windows API的并行程序设计6.4.1 代码及注释/ win32_quicksort.cpp : 定义控制台应用程序的入口点。#include stdafx.h#include #include time.h#include #include #define SIZE int xh_aSIZE,xh_dSIZE,xh_bSIZE/2,xh_cSIZE/2,xh_mSIZE;HANDLE finish2;HANDLE finish2;void quick_s

25、ort(int xh_s, int l, int r)if (l r)int i = l, j = r, x = xh_sl;while (i j)while(i = x) / 从右向左找第一个小于x的数j-; if(i j) xh_si+ = xh_sj;while(i j & xh_si x) / 从左向右找第一个大于等于x的数i+; if(i j) xh_sj- = xh_si;xh_si = x;quick_sort(xh_s, l, i - 1); / 递归调用quick_sort(xh_s, i+1, r);DWORD WINAPI ThreadOne(LPVOID param)

26、int i=0;for(i=0;iSIZE/2;i+)xh_bi=xh_ai;quick_sort(xh_b, 0,(SIZE/2)-1);SetEvent(finish0);return 0;DWORD WINAPI ThreadTwo(LPVOID param) int i=0;for(i=0;iSIZE/2;i+)xh_ci=xh_ai+(SIZE/2);quick_sort(xh_c, 0,(SIZE/2)-1);SetEvent(finish1);return 0;DWORD WINAPI ThreadThree(LPVOID param) quick_sort(xh_a, 0,SI

27、ZE-1);SetEvent(finish2);return 0;int _tmain(int argc, _TCHAR* argv)int i=0; srand(unsigned)time(NULL); /初始化随机数种子 for (i = 0; iSIZE; i+) xh_ai = rand();clock_t start=clock();long long sumand=0;finish0=CreateEvent(NULL,false,false,NULL);finish1=CreateEvent(NULL,false,false,NULL);finish2=CreateEvent(NU

28、LL,false,false,NULL);HANDLE thread1=CreateThread(NULL,0,ThreadOne,NULL,0,NULL);HANDLE thread2=CreateThread(NULL,0,ThreadTwo,NULL,0,NULL);WaitForMultipleObjects(2,finish,true,INFINITE);int n=SIZE/2;int j=0,k=0,l=0;while(ln&jn)if(xh_blxh_cj)xh_dk=xh_bl;l+;k+;else xh_dk=xh_cj;j+;k+;while(ln)xh_dk=xh_bl

29、;l+;k+;while(jn)xh_dk=xh_cj;j+;k+;/*for( i=0;iSIZE;i+)printf(%d ,xh_di);printf(n);*/clock_t end=clock();printf(parallel time=%dn,end-start);clock_t start2=clock();HANDLE thread3=CreateThread(NULL,0,ThreadThree,NULL,0,NULL);WaitForSinxheObject(finish2,INFINITE);clock_t end2=clock();printf(serial time

30、=%dn,end2-start2);/*for(int i=0;iSIZE;i+);printf(%d ,xh_ai); printf(n);*/system(pause);return 0;6.4.2 执行结果截图（体现串行时间、并行时间和加速比）（1）小数据量验证正确性的执行结果 图 11（2）大数据量获得较好加速比的执行结果个数的快速排序，加速比是187/78=2.40 图 12 个数的快速排序，加速比是4618/1560=2.96 图 136.4.3 遇到的问题及解决方案此种方式的编程较为简单，没有遇到问题6.5 基于.net的并行程序设计6.5.1 代码及注释using System

31、;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading;using System.Diagnostics; class quicksort static void Main() Console.WriteLine(请输入要排序的个数); int size= int.Parse(Console.ReadLine();int xh_a=new intsize;int xh_b=new intsize/2;int xh_c=new intsize/2;int xh_d=n

32、ew intsize;int i;int len=size/2; Random r = new Random(size);for(i=0;isize;i+) xh_ai = r.Next(); for(i=0;ilen;i+) xh_bi=xh_ai;xh_ci=xh_ai+len; /* Console.WriteLine(待排序数组); for( i=0;isize;i+)Console .Write(xh_ai+ ); Console.WriteLine(); */ Stopwatch stopwatch = new Stopwatch();/测量运行时间 Quicksort work1

33、 = new Quicksort(xh_b, 0, len - 1); ThreadStart thread1 = new ThreadStart(work1.run);/开启线程 Thread newthread1 = new Thread(thread1); Quicksort work2 = new Quicksort(xh_c, 0, len - 1); ThreadStart thread2 = new ThreadStart(work2.run);/开启线程 Thread newthread2 = new Thread(thread2); stopwatch.Start(); ne

34、wthread1.Start(); newthread2.Start(); newthread1.Join(); newthread2.Join(); stopwatch.Stop(); Quicksort work3 = new Quicksort(xh_d, xh_b, xh_c, len); work3.divide(xh_d,xh_b,xh_c,len); TimeSpan timeSpan = stopwatch.Elapsed; double milliseconds = timeSpan.TotalMilliseconds; Console.Write(parallel time

35、=); Console.WriteLine(milliseconds); stopwatch.Start(); Quicksort work4 = new Quicksort(xh_a, 0, size - 1); work4.quick_sort(xh_a, 0, size - 1); stopwatch.Stop(); TimeSpan timeSpan2 = stopwatch.Elapsed; double milliseconds2 = timeSpan2.TotalMilliseconds; Console.Write(serial time=); Console.Write(mi

36、lliseconds2); Console.WriteLine(); /* Console.WriteLine(并行排序结果); for (i = 0; i size; i+) Console.Write(xh_di+ ); Console.WriteLine(); Console.WriteLine(串行排序结果); for (i = 0; i size; i+) Console.Write(xh_ai + ); Console.WriteLine(); */ Console.Read(); class Quicksort public int array; private int arra

37、y1; private int array2; private int start; private int end; public Quicksort(int array,int start,int end) this.array=array; this.start=start; this.end=end; public Quicksort(int array, int array1,int array2, int n) this.array = array; this.array1 = array1; this.array2 = array; public void quick_sort(

38、int xh_s, int l, int r ) if (l r)int i = l, j = r, x = xh_sl;while (i j)while(i = x) / 从右向左找第一个小于x的数j-; if(i j) xh_si+ = xh_sj;while(i j & xh_si x) / 从左向右找第一个大于等于x的数i+; if(i j) xh_sj- = xh_si;xh_si = x;quick_sort(xh_s, l, i - 1); / 递归调用quick_sort(xh_s, i+1, r); public void divide(int xh_d, int xh_b,

39、 int xh_c, int n) int j=0,l=0, k = 0; while (l n & j n) if (xh_bl xh_cj) xh_dk = xh_bl; l+; k+; else xh_dk = xh_cj; j+; k+; while (l n) xh_dk = xh_bl; l+; k+; while (j n) xh_dk = xh_cj; j+; k+; public void run() quick_sort(array, start, end); 6.5.2 执行结果截图（体现串行时间、并行时间和加速比）（1）小数据量验证正确性的执行结果 图 14（2）大数据

40、量获得较好加速比的执行结果个数的快速排序，加速比是296.4015/103.6562=2.86 图 15个数的快速排序，加速比是3208.5916/1035.0556=3.10 图 166.5.3 遇到的问题及解决方案 在这次的编程中，我将归并排序封装成了一个函数 divide（），在主程序中调用该函数，完成归并排序，是的主程序更加简单明了，但是在调用的过程中，调用失败，主程序无法进行归并排序，究其原因是未写构造函数，进行初始化，divide（）函数是有四个参数，但是程序中只有一个三个参数的构造函数，需要增加一个有四个参数的构造函数。正确代码public Quicksort(int array, int array1,int array2, int n) this.array = array; this.array1 = array1; this.array2 = array; this.n=n; Quicksort thread3=new Quicksort(xh_d,xh_b,xh_c,len);thread3.d