并行计算课程设计（报告+代码+可执行文件）

1. 设计目的、意义（功能描述） 蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。本次大作业主要是对蒙特·卡罗方法进行并行处理，通过OpenMP、MPI、.NET、Java、Win32API等一系列并行技术和并行机制对该算法进行并行处理，从而也进一步熟悉了蒙特·卡罗方法的串行算法和并行算法，实现了用蒙特·卡罗方法计算出半径为1单位的球体的体积，体会到了并行技术在实际生活中的应用。 2. 方案分析（解决方案） 蒙特·卡罗方法（Monte Carlo method）是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。球的体积可以估算为：位于点模型内随机点个数与全体随机点个数的比值乘以包围盒的体积算的。 3. 设计分析 3.1 串行算法设计 假定球体用B表示，半径r=1单位，B1是包含B的参考立方体（在本例中是边长为2的正方体），在B1中产生N个均匀分布的伪随机点。对每个随机点检测其是否在B内，假设位于B内的随机点个数为N（in）（<=N），应用蒙特卡洛算法，则B的体积为 V=V1（N（in）/N） 其中V1是B1的体积。如果产生足够多的随机点，理论上可以获得任意逼近精度。 算法描述如下： BEGIN N=_MAX; FOR I=0;I<_MAX;I++ X=RANDOM(); Y=RANDOM(); Z=RANDOM(); IF (X*X+Y*Y+Z*Z)<=1 COUNT++; END IF; END FOR; BULK=V1*（COUNT/_MAX）; END; 本算法主要是在参考立方体的选取上和定义的_MAX的值对结果影响较大，所以应该选择合适的数。 3.2 并行算法设计 对FOR循环进行划分使用两个处理器完成计算。例如对一个长为n的序列，首先划分得到两个长为n/2的序列，将其交给两个处理器分别处理；而后进一步划分得到四个长为n/4的序列，再分别交给四个处理器处理；如此递归下去最终得到结果。当然这是理想的划分情况，如果划分步骤不能达到平均分配的目的，那么结果的效率会相对较差。 伪代码如下： BEGIN N=_MAX; FOR1 I=0;I<_MAX/2;I++ X1=RANDOM(); Y1=RANDOM(); Z1=RANDOM(); IF (X1*X1+Y1*Y1+Z1*Z1)<=1 COUNT1++; END IF; END FOR1; FOR2 I=_MAX/2+1;I<_MAX;I++ X2=RANDOM(); Y2=RANDOM(); Z2=RANDOM(); IF (X2*X2+Y2*Y2+Z2*Z2)<=1 COUNT2++; END IF; END FOR2; BULK=V1*(（COUNT1+ COUNT2）/_MAX）; END; 3.3 理论加速比分析 实验中大量数据所产生的加速比比小量数据所产生的加速比要体现得更明显，并且数据生成的并行加速比随着处理器核的增加而增加。设处理器个数为p，数据量为n，由于正常情况下该快速排序算法的复杂度为O(nlogn),并行处理的时间复杂度为O(klogk),其中k=n/p,所以并行算法的时间复杂度为O((n/p)log(n/p)),理论加速比为nlogn/((n/p)log(n/p))=p+logp. 4. 功能模块实现与最终结果分析 4.1 基于OpenMP的并行算法实现 4.1.1 主要功能模块与实现方法 利用了OpenMP里面的#omp parallel sections将对两个for循环用两个线程并行化执行，以多线程方式并行运行程序，并行的算法步骤如下： （1）初始化_max = 10000000； （2）创建两个线程； （3）由OpenMP编译指导语句控制产生并行执行代码区段； （4）将数据存放到tianqing_count; （5）各线程调用算法得出结果； 并行算法的部分代码如下： #pragma omp parallel for private(tianqing_x,tianqing_y,tianqing_z) reduction(+:tianqing_count2) for (tianqing_i = 0; tianqing_i<tianqing_max; tianqing_i++) { tianqing_x = rand(); tianqing_x = tianqing_x / 32767; tianqing_y = rand(); tianqing_y = tianqing_y / 32767; tianqing_z = rand(); tianqing_z = tianqing_z / 32767; if ((tianqing_x*tianqing_x + tianqing_y*tianqing_y + tianqing_z*tianqing_z) <= 1) tianqing_count2++; } tianqing_bulk = 8 * ((double)(tianqing_count2) / tianqing_max); 4.1.2 实验加速比分析 实验中创建了两个线程，通过多次测试，得出实验结果：由上面的理论加速比分析可知，当线程数为2时，理论加速比为2+log2=3.但由于实际操作中硬件设备以及内存分配的影响，实验加速比达不到理论值3.实验加速比在1.9左右，比较符合常理。 4.2 基于MPI的并行算法实现 4.2.1 主要功能模块与实现方法 主要利用了MPI的MPI_Bcast（）函数和MPI_Recv()函数进行各个进程之间的通信，算法步骤如下： （1）初始化_max = 10000000； （2）动态申请2个数组，分别记录分块的起始地址、各个进程所获得的数据个数； （3）各个进程之间进行通信，发送接收各个进程的起始地址与数据大小； （4）并行执行算法; （5）得出结果； 伪代码如下： //初始化MPI执行环境 MPI_Init(&argc, &argv); //用MPI_Comm_rank 获得进程的rank，该rank值为到p-1间的整数,相当于进程的ID MPI_Comm_rank(MPI_COMM_WORLD, &myid); //用MPI_Comm_size 获得进程个数 int MPI_Comm_size(MPI_Comm comm, int *size); MPI_Comm_size(MPI_COMM_WORLD, &numprocs); MPI_Get_processor_name(processor_name, &namelen)； MPI_Bcast(&tianqing_n,1,MPI_INT,0,MPI_COMM_WORLD);//将tianqing_n值广播出去 算法执行； MPI_Reduce(&tianqing_bulk, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);//各个进程并行计数得到的计数总和 获得结果。 4.2.2 实验加速比分析 实验中使用了两个处理器，因此理论加速比应该为2，通过多次测试，得出实验结果：加速比：1.976906139262282，由于客观因素的影响，结果合理。 4.3 基于Java的并行算法实现 4.3.1 主要功能模块与实现方法 在Java中，创建用户自己的线程类，使用启动线程的start()方法启动线程对象，使之从新建状态转入就绪状态，定义线程操作的run()方法，并定义新的run()方法覆盖原来的run()方法。 伪代码如下: And thread1=new And(1,10000000); And thread2=new And(2,10000000); long startTime=System.currentTimeMillis(); 启动线程1和线程2; 等待进程结束； And and=new And(a，10000000); bulk1=8*((b*1.0)/tianqing_n); 4.3.2 实验加速比分析 实验中创建了两个线程，通过多次测试，得出实验结果：由上面的理论加速比分析可知，当线程数为2时，理论加速比为2+log2=3.但由于实际操作中硬件设备以及内存分配的影响，实验加速比达不到理论值3.实验加速比在1.9左右，比较符合常理。 4.4 基于Windows API的并行算法实现 4.4.1 主要功能模块与实现方法 这里主要用到了Win32 API的进入点函数，在进程中创建一个线程时，也必须给这个线程提供一个进入点函数。线程函数必须返回一个值，它将成为该线程的退出代码。使用CreateThread()函数创建线程，用WaitForMultipleObject()函数管理线程来监测多个对象。采用SetEvent来设置事件处理线程间的同步问题。 伪代码如下： DWORD WINAPI ThreadOne(LPVOID param) { 对前一半数据进行处理； SetEvent(finish[0]); return 0; } DWORD WINAPI ThreadTwo(LPVOID param) { 对后一半数据进行处理； SetEvent(finish[1]); return 0; } 创建两个事件； HANDLE thread1=CreateThread(NULL,0,ThreadOne,NULL,0,NULL);//两个并行线程 HANDLE thread2=CreateThread(NULL,0,ThreadTwo,NULL,0,NULL); WaitForMultipleObjects(2,finish,true,INFINITE); 得出结果； 4.4.2 实验加速比分析 实验中创建了两个线程，通过多次测试，得出实验结果：由上面的理论加速比分析可知，当线程数为2时，理论加速比为2+log2=3.但由于实际操作中硬件设备以及内存分配的影响，实验加速比达不到理论值3.实验加速比在1.6左右。 4.5 基于.net的并行算法实现 4.5.1 主要功能模块与实现方法 先创建ThreadStart代理，指定要由该线程执行的线程函数，然后将ThreadStart代理传递给Thread类的构造函数，调用Thread类的Start方法启动新的线程然后调用Join()方法保证应用程序域等待异步程序结束后才终止运行。 伪代码如下: Stopwatch stopwatch = new Stopwatch(); 创建Work类的对象work1; ThreadStart thread1 = new ThreadStart(() => work1.pSumto(b, 0, MAXN - 1)); Thread newthread1 = new Thread(thread1); 创建Work类的对象work2; ThreadStart thread2 = new ThreadStart(() => work2.pSumto(c, 0, MAXN - 1)); Thread newthread2 = new Thread(thread2); stopwatch.Start(); 启动线程1和线程2; 等待进程结束； stopwatch.Stop(); 得到结果; 4.5.2 实验加速比分析 实验中创建了两个线程，通过多次测试，得出实验结果：由上面的理论加速比分析可知，当线程数为2时，理论加速比为2+log2=3.但由于实际操作中硬件设备以及内存分配的影响，实验加速比达不到理论值3.实验加速比在2.6~2.7左右。 4.6 并行计算技术在实际系统中的应用 4.6.1 主要功能模块与实现方法 该飞机订票系统主要实现了对机票的一些基本信息进行存储和管理的功能。在系统中实现了对机票信息的增删改查，考虑到查询的方便性，对机票按照航班号进行排序，而此排序方法用并行快速排序运用进来。利用OpenMP的并行技术，对机票信息按顺序排列好，并分析了实验过程中的加速比。 4.6.2 实验加速比分析 实验中创建了两个线程，通过多次测试，得出实验结果：当数据量比较大时，加速比理论在1.9左右。数据量较大时体现出来的加速比更准确。由上面的理论加速比分析可知，当线程数为2时，理论加速比为2+log2=3.但由于实际操作中硬件设备以及内存分配的影响，实验加速比达不到理论值3.实验加速比在2.2~2.4左右。 5. 设计体会 虽然没有按时完成作业，但这份报告花了我好几天的时间，从开始的搭建并行计算平台到最后的程序运行成功可以说是对我的一个锻炼。每一次的遇到问题与每一次的解决问题都是一个成长。每一次遇到问题和解决问题都是一种锻炼，一种尝试，从我们上并行计算课我懂得了很多电脑硬件和软件的知识，这些可能对于我们这个专业以后都是没有机会接触的，所以我觉得选择了并行计算与多核多线程技术这门课是非常正确的。对OpenMP、MPI、WIN32API、Java、.NET的并行技术有了一定的了解。在搭建MPI并行程序这块，学习的知识尤为增加，这些都是在不断的摸索、学习中学会的。 这次的大作业虽然是对以前实验的整合，但它加深了我对并行计算的印象，也使我对并行计算知识的理解更加深刻，也使我认识到了自己很多不足之处。学习并行计算的历程不会因为完成本次大作业而停止，我们是为了用知识武装大脑而学习，通过学习充实自己的生活，要努力学习，争取以后能够完成规模更大的程序。