燕山大学多核程序设计实验报告

1实验一Windows多线程编程一、实验目的与要求了解windows多线程编程机制掌握线程同步的方法二、实验环境和软件WindowsXPVC6.0三、实验内容创建线程：HANDLECreateThread(LPSECURITY_ATTRIBUTESlpThreadAttributes,SIZE_TdwStackSize,LPTHREAD_START_ROUTINElpStartAddress,LPVOIDlpParameter,DWORDdwCreationFlags,LPDWORDlpThreadId);四、实验程序#includestdafx.h#includewindows.h#includeprocess.h#includeiostream#includefstreamusingnamespacestd;voidThreadFrunc1(PVOIDparam){2while(1){Sleep(1000);coutThisisThreadFrunc1endl;}}voidThreadFrunc2(PVOIDparam){while(1){Sleep(1000);coutThisiskjjThreadFrunc2endl;}}intmain(){inti=0;_beginthread(ThreadFrunc1,0,NULL);_beginthread(ThreadFrunc2,0,NULL);Sleep(3000);coutendendl;return0;}实验结果实验二蒙特卡罗法求PI一、实验目的和要求3蒙特卡洛算法可理解为通过大量实验，模拟实际行为，来收集统计数据。本例中，算法随机产生一系列点，模拟这些点落在如下图所示的正方形区域内的情况。其几何解释如下X轴Y轴11图1如图1所示，正方形边长为1，左下顶点与原点重合，两边分别与x，y轴重合。曲线为1/4圆弧，圆心位于原点，与正方形左下定点重合，半径为1。正方形面积S1=1，圆弧内面积S2=41412r。算法模拟大量点随机落在此正方形区域内，落在圆弧内的点的数量（n2）与点的总数（n1）的比例与面积成正比关系。即42121SSnn（1）由此可得124nn（2）因此，只要计算出落在圆弧内的点的数量在点总数中所占的比例，就能求出的值。由图1可知，所有点均落在正方形范围内，因此点的x坐标满足10x。又，当点落在圆弧范围内，则点的二维坐标关系满足122yx。检验每一个点是否满足此关系即可判定改点是否落在圆弧内。4二、实验环境和软件编译器：MicrosoftVisualStudioC++6.0操作系统：WindowsXP三、实验内容3.1串行算法本项目中使用了标准C语言库中的产生随机数函数。该函数原型为：intrand(void);此函数产生随机数列，每次调用时均返回0到RAND_MAX之间的一个整数。voidsrand(unsignedintseed);此函数为rand（）函数所生成的伪随机数序列设置起始点，使之产生不同的伪随机数。算法：产生2n个随机数据，范围[0，1]，对每个数据点计算其坐标是否满足122yx，统计满足此关系的点的数量count，则ncount43.2并行算法描述算法步骤：1、确定需要产生的点的个数n，参与运行的处理器数m；2、对每一个处理器，生成两个随机数x，y，范围[0，1]；3、判断两个随机数x，y是否满足122yx；4、若满足，则变量COUNTi++；5、重复步骤2-4，直至每个处理器均生成n/m个随机点；6、收集COUNTi的值，并累加至变量COUNT中，此即为随机点落在圆弧内的数量；7、通过（2）式计算的值。3.3并行算法在Windows下的一个例子5#includestdio.h#includewindows.h#includetime.h//#includeprocess.h#includeiostream#includefstream#includestdlib.husingnamespacestd;HANDLEevFinish;longcs=0;//总循环次数longcount=0;//主线程有效次数longcount_thread=0;//thread线程有效次数time_tstart,finish;//定义开始结束时间//thread线程计算量为总数的一半DWORDWINAPIthread(LPVOIDparam){inti=0;doublex,y;for(i=0;ics/2;i++){x=(longdouble)rand()/(longdouble)RAND_MAX;y=(longdouble)rand()/(longdouble)RAND_MAX;if((x*x+y*y)=1)count_thread++;//printf(副%d,i);}SetEvent(evFinish);return0;}//主线程计算量为总数的一半intmain(void){evFinish=CreateEvent(NULL,FALSE,FALSE,NULL);printf(请输入总循环次数:);scanf(%d,&cs);cs*=1000000;srand((unsigned)time(NULL));//用时间作随机数种子6start=time(NULL);//记录开始时间HANDLEid=CreateThread(NULL,0,thread,NULL,0,NULL);//创建thread线程inti=0;doublex,y;for(i=0;ics/2;i++){x=(longdouble)rand()/(longdouble)RAND_MAX;y=(longdouble)rand()/(longdouble)RAND_MAX;if((x*x+y*y)=1)count++;//printf(主%d,i);//printf(count%d,count);}WaitForSingleObject(evFinish,INFINITE);//两线程同步count+=count_thread;finish=time(NULL);//记录结束时间printf(并行情况：\n\n);printf(用时=%f秒\n,difftime(finish,start));//计算时间差printf(总共的循环次数=%d次\n,cs);printf(线程有效次数=%d次\n,count);printf(pi=%f\n,4*(double)count/(double)cs);printf(串行行情况：\n);count=0;start=time(NULL);//记录开始时间for(i=0;ics;i++){x=(longdouble)rand()/(longdouble)RAND_MAX;y=(longdouble)rand()/(longdouble)RAND_MAX;if((x*x+y*y)=1)count++;//printf(主%d,i);//printf(count%d,count);}finish=time(NULL);//记录结束时间printf(用时=%f秒\n,difftime(finish,start));printf(总共的循环次数=%d次\n,cs);7printf(线程有效次数=%d次\n,count);printf(pi=%f\n,4*(double)count/(double)cs);return(0);}实验结果：测试数据集合：由随机数函数产生的数据集合实验三并行排序一、实验目的与要求在单核计算环境中，排序算法关注的核心问题是怎样减少要排序数据之间的比较次数或算法所需要的内存空间。在多核计算环境中，每个核以线程为执行单元，排序程序可以通过生成相互协作的线程来完成排序。与单核计算环境不同的是，在多核计算环境中更关注数据集的合理划分，更致力于识别可并行执行的任务。一旦完成这些工作，程序设计上就可以生成对应的线程去执行任务。理论上，基于相8同的串行算法和相同的cache命中率，多核计算速度可以无限接近单核计算速度的P倍，其中P为核的数目。多核上的并行排序算法所面临的问题在于：1.未排序的数据集合理划分到每个线程后，最后怎么汇合，形成完整的排好序的数据集呢？2.怎么保证可并行执行的线程的数目和核的数目相等或稍微多于核的数目，同时也保证这些线程之间的工作量也尽可能的相同呢？在这个实验中，串行的算法采用标准C语言库中的快速排序函数。并行算法中，先将要处理的数据集均等的分到每个线程中，并使用C语言库中的快速排序函数各自排序。然后所有线程开始根据相同的数对自己的数据集进行划分，这个数是依据一定的方法选出来的（详见并行算法描述）。每个线程的数据集都会被分成K份，（其中P=KP2，P为核的数目），每份将被称为一桶。很显然这个过程选出了K个数，这些数将被成为bound_value,记为X1,X2,X3……XK。最后每个线程中小于或等于X1的数会被一个独立的线程去归并排序，同样小于或等于X2的数也会被另外一个独立的线程去归并排序，依次类推，直到排好序。需要指出的是：这个并行版本最消耗时间的部分是一开始每个线程各自的排序，时间为：O（lognn）；不过其数据划分和线程生成也相对简单。最后的归并排序所需时间是线性增长的，即：O（n），因此即使在最后归并部分线程执行的任务已经是不均衡的，也不会对整个程序的性能产生很大的影响。二、实验环境和软件编译器：MicrosoftVisualStudioC++6.0操作系统：WindowsXP三、实验内容3.1并行算法描述算法:将原始待排序的数据分成P等份，每个处理器上对N0个数据进行排序，称每个被排序后的子集为B0,…,Bp-1Remain_data=N，设定第0组归并起始位置全部为0,i=0，设置第0组在9目标数组中的起始位置为0循环直至remian_dataL(L=N0/P)3.1选取所有子集中起始位置后续L个元素的最小值bound_value，并获得bound_value的桶号bucket3.2在所有子集中从起始位置到后续L个元素中选取边界位置，使得边界位置的最后一个元素小于或等于bound_value，而边界位置后的第一元素大于bound_value。3.3记录所有的边界位置，并设置所有第i＋1组的起始位置为第i组的起始位置加上边界位置3.4累积所有边界值，得到该归并组的大小3.5根据归并组大小和本组起始位置计算第i+1组在目标数组中的起始位置。4、设置最后一个归并组的边界为N05、对所有归并组进行并行P路归并排序。四、实验步骤说明：A．P和多核处理器的数目相同。比如是双核的，那么P＝2；B．Remain_data是每个线程处理的数据集中还没有被X1,X2,X3……划分过的数据集的总数目。比如，根据X1每个线程划分出来的数据集为x，y，z……,那么Remain_data＝n–x–y–z…..并行算法在Windows下的一个例子#includestdlib.h#includestdio.h#includetime.h#includesearch.h#includewindows.h#includeprocess.h#ifndef_BASIC_SORT_H#define_BASIC_SORT_H#ifndef_SORT_P#define_SORT_Pvoid*sort(void*parameter);voidgenerate_data(int*a,intn);10voidsort_s(int*a,intn);voidview_data(int*a,intn);intcheck_data_sort(int*a,intn);intcompare(constvoid*arg1,constvoid*arg2);#defineMILLION1000000L#defineP2#defi