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

燕山大学多核程序设计实验报告计划燕山大学多核程序设计实验报告计划PAGE24燕山大学多核程序设计实验报告计划WORD格式实验一Windows多线程编程一、实验目的与要求认识windows多线程编程体系掌握线程同步的方法二、实验环境和软件WindowsXP三、实验内容创办线程：HANDLECreateThread(LPSECURITY_ATTRIBUTESlpThreadAttributes,SIZE_TdwStackSize,LPTHREAD_START_ROUTINElpStartAddress,LPVOIDlpParameter,DWORDdwCreationFlags,LPDWORDlpThreadId);四、实验程序#include"stdafx.h"#include<windows.h>#include<process.h>#include<iostream>#include<fstream>usingnamespacestd;voidThreadFrunc1(PVOIDparam){1专业资料整理格式while(1){Sleep(1000);cout<<"ThisisThreadFrunc1"<<endl;}}voidThreadFrunc2(PVOIDparam){while(1){Sleep(1000);cout<<"ThisiskjjThreadFrunc2"<<endl;}}intmain(){inti=0;_beginthread(ThreadFrunc1,0,NULL);_beginthread(ThreadFrunc2,0,NULL);Sleep(3000);cout<<"end"<<endl;return0;}实验结果实验二蒙特卡罗法求PI一、实验目的和要求2专业资料整理格式蒙特卡洛算法可理解为经过大量实验，模拟实质行为，来收集统计数据。本例中，算法随机产生一系列点，模拟这些点落在以以下图所示的正方形地域内的情况。其几何讲解以下1轴YX轴1图1如图1所示，正方形边长为1，左下极点与原点重合，两边分别与x，y轴重合。曲线为1/4圆弧，圆心位于原点，与正方形左下定点重合，半径为1。正方形面积S1=1，圆弧内面积121r。算法模拟大量S2=44点随机落在此正方形地域内，落在圆弧内的点的数量（n2）与点的总数（n1）的比率与面积成正比关系。即nS4（1）11nS22由此可得4n2（2）n1因此，只要计算出落在圆弧内的点的数量在点总数中所占的比率，就能求出的值。由图1可知，全部点均落在正方形范围内，因此点的x坐标满足0x1。圆弧范围内，则点的二维坐标关系满足x1。2y2又，当点落在检验每一个点可否满足此关系即可判断改点可否落在圆弧内。专业资料整理WORD格式3专业资料整理格式二、实验环境和软件编译器：操作系统：WindowsXP三、实验内容串行算法本项目中使用了标准C语言库中的产生随机数函数。该函数原型为：intrand(void);此函数产生随机数列，每次调用时均返回0到RAND_MA之X间的一个整数。voidsrand(unsignedintseed);此函数为rand（）函数所生成的伪随机数序列设置初步点，使之产生不同样的伪随机数。算法：产生2n个随机数据，范围[0，1]，对每个数据点计算其坐标可否满足2y2x1，统计满足此关系的点的数量count，则count4n并行算法描述算法步骤：1、确定需要产生的点的个数n，参加运行的办理器数m；2、对每一个办理器，生成两个随机数x，y，范围[0，1]；2y23、判断两个随机数x，y可否满足x1；4、若满足，则变量COUNTi++；5、重复步骤2-4，直至每个办理器均生成n/m个随机点；6、收集COUNTi的值，并累加至变量COUNT中，此即为随机点落在圆弧内的数量；7、经过（2）式计算的值。并行算法在Windows下的一个例子专业资料整理WORD格式4专业资料整理WORD格式#include<stdio.h>#include<windows.h>#include<time.h>//#include<process.h>#include<iostream>#include<fstream>#include<stdlib.h>usingnamespacestd;HANDLEevFinish;longcs=0;//总循环次数longcount=0;//主线程有效次数longcount_thread=0;//thread线程有效次数time_tstart,finish;//定义开始结束时间//thread线程计算量为总数的一半DWORDWINAPIthread(LPVOIDparam){inti=0;doublex,y;for(i=0;i<cs/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));//用时间作随机数种子5专业资料整理WORD格式start=time(NULL);//记录开始时间HANDLEid=CreateThread(NULL,0,thread,NULL,0,NULL);//创办thread线程inti=0;doublex,y;for(i=0;i<cs/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;i<cs;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);6专业资料整理格式printf("线程有效次数=%d次\n",count);printf("pi=%f\n",4*(double)count/(double)cs);return(0);}实验结果：测试数据会集：由随机数函数产生的数据会集实验三并行排序一、实验目的与要求在单核计算环境中，排序算法关注的核心问题是怎样减少要排序数据之间的比较次数或算法所需要的内存空间。在多核计算环境中，每个核以线程为执行单元，排序程序可以经过生成相互协作的线程来达成排序。与单核计算环境不同样的是，在多核计算环境中更关注数据集的合理划分，更致力于鉴别可并行执行的任务。一旦达成这些工作，程序设计上就可以生成对应的线程去执行任务。理论上，基于相7专业资料整理WORD格式同的算速度的P倍，其中P为核的数量。串多行核上的并行排序算法所面对的问题在于：算1.未排序的数据会集理划分到每个线程后，最后怎么会集，形成完满的法排好序的数据集呢？和2.相怎么保证可并行执行的线程的数量和核的数量相等或稍微多于核的数同目，同时也保证这些线程之间的工作量也尽可能的同样呢？的c在这个实验中，串行的算法采用准标C语言库中的快速排序函数。ac并行算法中，先将要办理的数据集均等的分到每个线程中，并使用C语言库中的快速排序函数各自排序。尔后全部线程开始依照同样的数对自己h的e数据集进行划分，这个数是依照必然的方法选出来的（详见并行算法描述）。命每中个线程的数据集都会被分成K份，（其中P<=K<P2，P为核的数量），率每份将被称为一桶。很显然这个过程选出了K个数，这些数将被成为，bound多_value,记为X1,X2,X3??XK。最后每个线程中小于或等于X1核的数会被一个独立的线程去归并排序，同样小于或等于X2的数也会被别的计一个独立的线程去归并排序，依次类推，直到排好序。算速需要指出的是：这个并行版本最耗资时间的部分是一开始每个线程各自的度可排序，时间为：O（nlogn）；但是其数据划分和线程生成也相对简单。最以无后的归并排序所需时间是线性增添的，即：On限（），因此即使在最后归并核计生很大部分线程执行的任务已经是不均衡的，也不会对整个程序的性能产的影响。二、实验环境和件软编译器：操作系统：WindowsXP三、实验内容并行算法描述算法:将原始待排序的数据分成P等份，每个办理器上对N0个数据进行排序，称每个被排序后的子集为B0,?,Bp-1Remain_data=N，设定第0组归并初步地址全部为0,i=0，设置第0组在8专业资料整理WORD格式目标循环直至remian_data<L(L=N0/P)数3组.1采用全部子集中初步地址后续L个元素的最小值bound_value，并获中得bound_value的桶号bucket的在全部子集中从初步地址到后续L个元素中采用界线地址，使得界线起始地址的最后一个元素小于或等于bound_value，而界线地址后的第一元素0大于bound_value。记录全部的界线地址，并设置全部第i＋1组的初步地址为第i组的起始地址加上界线地址累积全部界线值，获取该归并组的大小依照归并组大小和本组初步地址计算第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下的一个例子#include<stdlib.h>#include<stdio.h>#include<time.h>#include<search.h>#include<windows.h>#include<process.h>#ifndef_BASIC_SORT_H#define_BASIC_SORT_H#ifndef_SORT_P#define_SORT_Pvoid*sort(void*parameter);voidgenerate_data(int*a,intn);9专业资料整理WORD格式voidsort_s(int*a,intn);voidview_data(int*a,intn);intcheck_data_sort(int*a,intn);intcompare(constvoid*arg1,constvoid*arg2);#defineMILLION1000000L#defineP2#defineN04332539//#defineN01000000#defineNN0*P#defineLN0/Pvoidsort_p(intd,int*b);time_tstart,finish;//定义开始结束时间structmerge{//归并结构intbegin[P];//数组beginintcount[P];//数组countintmerge_size;//归并大小intglobal_pos;//全局地址intmerged;//归并可否达成};structarg_merge_data{//归并数据结构intd;//数组的指针structmerge*mp;//归并结构int*b;//整数bintk;};structarg_merge_data*tmp2;structforsort{int*d;intk;};structforsortforsorta[P];intfind_bound_value(intd,structmerge*mp,int*bucket);intfind_min(intd,structmerge*mp,int*bucket);voidfind_bound(intd,structmerge*mp,intbucket,intbound_value);voiddo_last_merge_block(structmerge*mp);voidmerge_data(void*arg);10专业资料整理WORD格式voidview_merge(intd,structmerge*mp,intlast_merge_block);intstart_time();intdiff_time();#endif#endifintk;HANDLESwait[P];HANDLEPwait[P];HANDLEpthread[P];HANDLEqthread[P];externint*d[P];///////////////////////////////////////////////////////////////////voidgenerate_data(int*a,intn){//产生数据inti;for(i=0;i<n;i++){a[i]=rand()%10000;//产生数组a有n个元素}for(i=0;i<P;i++){d[i]=&(a[i*N0]);//产生数组d对应a[i]中每个n0块的第i个元素}}////////////////////////////////////////////////////////////////////voidsort_s(int*a,intn){//快排a[i]qsort((void*)a,n,sizeof(int),compare);}////////////////////////////////////////////////////////////////////void*sort(void*parameter){//快排参数（数组）的前N0个元素structforsort*forsortb=(structforsort*)parameter;//printf("\nSetEvent(Swait[%d])",forsortb->k);/////////////////=====================intkk=forsortb->k;qsort(/*(void*)*/forsortb->d,N0,sizeof(int),compare);11专业资料整理WORD格式SetEvent(Swait[kk]);//printf("\n%d",kk);return(void*)0;}///////////////////////////////////////////////////////////////////voidview_data(int*a,intn){inti=n,j;intindex=0;while(i>N0){for(j=0;j<N0;j++){printf("%d\t",a[index++]);//输出a[i]中前N0个数}printf("\n");i-=N0;}for(;i>0;i--){//输出a[i]中N0后边的个数printf("%d\t",a[index++]);}printf("\n");}//////////////////////////////////////////////////////////////////////intcheck_data_sort(int*a,intn){//找出不服和大小序次的地址inti;for(i=0;i<n-1;i++){if(a[i]>a[i+1])break;}returni;}//////////////////////////////////////////////////////////////////////intcompare(constvoid*arg1,constvoid*arg2){//返回arg1与arg2的差inta=*(int*)arg1,b=*(int*)arg2;returna-b;}////////////////////////////////////////////////////////////////12专业资料整理WORD格式////inta[N];//dataforparallelsortintb[N];//theresultofparallelsortint*d[P];//forparallelsortints[N];//dataforserialsortstructmergem_list[P*P];//recordofpartitionintmerge_block;//thenumberofpartitionDWORDthr_id[P*P];longtimedif;//forestimatetheexectiontime//structtimevalend;//...//structtimevalstart;//...voidinite(){inti;//forsorta=(structforsort*)calloc(P,sizeof(structforsort));for(i=0;i<P;i++){Swait[i]=CreateEvent(NULL,FALSE,FALSE,NULL);Pwait[i]=CreateEvent(NULL,FALSE,FALSE,NULL);/*for(intj=0;j<P;j++){forsorta[i].d[j]=d[j];//printf("forsorta[%d].d[%d]=%d\n",i,j,forsorta[i].d[j]);}*/}}voidmain(){intdata;inti;generate_data(a,N);//产生数组a[n]for(i=0;i<N;i++)//数组s=as[i]=a[i];inite();printf("请稍等\n");//start_time();13专业资料整理WORD格式sort_p(d,b);//diff_time();start_time();sort_s(s,N);printf("单线程快排所用时间\n");diff_time();if((data=check_data_sort(b,N))==N-1)printf("SortisOK\n");else{printf("b[%d]>b[%d]\n",data,data+1);}}//////////////////////////////////////////////////////////////////////////intstart_time(){//记录开始时间函数start=time(NULL);//记录开始时间return0;}/////////////////////////////////////////////////////////////////////////intdiff_time(){//记录结束时间并算时间差函数finish=time(NULL);//记录结束时间printf("用时=%f秒\n",difftime(finish,start));//输出结果return0;}///////////////////////////////////////////////////////////////////////////voidsort_p(intd,int*b){//tmp2=(arg_merge_data*)calloc(merge_block+l,sizeof(structarg_merge_data));inti;14专业资料整理WORD格式intremain_data=N;//节余数据初始化merge_block=0;//归并块=0start_time();for(i=0;i<P;i++){//m_list[0]中的两个数组初始化m_list[0].begin[i]=0;m_list[0].count[i]=0;}m_list[0].merge_size=0;//m_list[0]中的归并大小初始化m_list[0].global_pos=0;//m_list[0]中的全局地址初始化for(i=0;i<P;i++){forsorta[i].k=i;forsorta[i].d=d[i];structforsort*forsortb=&forsorta[i];pthread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)sort,forsortb,0,&(thr_id[i]));}//产生p个线程（线程id，使用sort函数，参数传达d[i]）WaitForMultipleObjects(P,Swait,TRUE,INFINITE);//等待全部线程结束/////////////printf("每个线程先对自己快排时\n");diff_time();start_time();while(remain_data>L*P){//节余数据大于L*Pintbound_value;intbucket;bound_value=find_bound_value(d,&(m_list[merge_block]),&bucket);find_bound(d,&(m_list[merge_block]),bucket,bound_value);remain_data-=m_list[merge_block].merge_size;m_list[merge_block].merged=0;merge_block++;if(merge_block>=P*P){//溢出办理printf("blockpartitionisgreaterthanP^2\n");15专业资料整理WORD格式break;}}printf("P路线程分别找出对应的最小值并重新划分L长，直至全部划分达成时\n");diff_time();start_time();do_last_merge_block(&(m_list[merge_block]));//structarg_merge_data*tmp2;tmp2=(structarg_merge_data*)calloc(merge_block,sizeof(structarg_merge_data));//结构体数组分配空间for(i=0;i<=merge_block;i++){tmp2[i].k=i;tmp2[i].d=d;tmp2[i].mp=&(m_list[i]);tmp2[i].b=&(b[m_list[i].global_pos]);//pthread_create(&(thr_id[i]),NULL,&(merge_data),tmp2+i);//k=i;qthread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)merge_data,tmp2+i,0,&(thr_id[i]));}WaitForMultipleObjects(P,Pwait,TRUE,INFINITE);/////////////////////////pthread_join(thr_id[i],NULL);printf("P路线程归并达成时\n");diff_time();}////////////////////////////////////////////////////////////////////////////intfind_bound_value(intd,structmerge*mp,int*bucket){//找出本块中的追小值赋给bucketinti;intmin;intfirst=1;16专业资料整理WORD格式for(i=0;i<P;i++){if(mp->begin[i]+L<N0){//本块中小于NO的部分if(first==1){min=d[i][mp->begin[i]+L];*bucket=i;first=0;}else{if(min>=d[i][mp->begin[i]+L]){min=d[i][mp->begin[i]+L];*bucket=i;}}}}returnmin;}//////////////////////////////////////////////////////////////////////////////voidfind_bound(intd,structmerge*mp,intbucket,intbound_value){inti;for(i=0;i<P;i++){if(i!=bucket){inttcount;int*dp;if(mp->begin[i]+L<N0)tcount=L+1;elsetcount=N0-mp->begin[i]-1;dp=&(d[i][mp->begin[i]]);if(tcount==1){if(dp[0]>bound_value)tcount=0;}else{17专业资料整理WORD格式if(dp[0]>bound_value){tcount=0;}elseif(dp[tcount]<=bound_value){if(mp->begin[i]+L<N0)tcount=L+1;elsetcount=N0-mp->begin[i]-1;//maybeherehassomeproblem}else{intb=0,e=tcount;while(!((dp[(e+b)/2]<=bound_value)&&(dp[(e+b)/2+1]>bound_value))){if(dp[(e+b)/2]>bound_value)e=(e+b)/2;elseb=(e+b)/2;}tcount=(e+b)/2+1;}}mp->count[i]=tcount;}else{mp->count[i]=L+1;}}mp->merge_size=0;for(i=0;i<P;i++){mp->merge_size+=mp->count[i];mp[1].begin[i]=mp->begin[i]+mp->count[i];mp[1].global_pos=mp->global_pos+mp->merge_size;}}////////////////////////////////////////////////////////////////18专业资料整理WORD格式///////////////////voiddo_last_merge_block(structmerge*mp){inti;mp->merge_size=0;for(i=0;i<P;i++){if(mp->begin[i]>=N0)mp->count[i]=0;elsemp->count[i]=N0-mp->begin[i];mp->merge_size+=mp->count[i];}}///////////////////