燕山大学多核程序设计实验报告(共21页).doc

《燕山大学多核程序设计实验报告(共21页).doc》由会员分享，可在线阅读，更多相关《燕山大学多核程序设计实验报告(共21页).doc（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上 实验一 Windows多线程编程一、实验目的与要求了解windows多线程编程机制掌握线程同步的方法二、实验环境和软件Windows XPVC 6.0三、实验内容创建线程：HANDLE CreateThread (LPSECURITY_ATTRIBUTES lpThreadAttributes,SIZE_T dwStackSize, LPTHREAD_START_ROUTINE lpStartAddress,LPVOID lpParameter, DWORD dwCreationFlags, LPDWORD lpThreadId );四、实验程序 #includes

2、tdafx.h#include#include#include#includeusing namespace std;void ThreadFrunc1(PVOID param)while(1)Sleep(1000);coutThis is ThreadFrunc1endl;void ThreadFrunc2(PVOID param)while(1)Sleep(1000);coutThis is kjj ThreadFrunc2endl;int main()int i=0;_beginthread(ThreadFrunc1,0,NULL);_beginthread(ThreadFrunc2,0

3、,NULL);Sleep(3000);coutendendl;return 0;实验结果 实验二 蒙特卡罗法求PI一、 实验目的和要求蒙特卡洛算法可理解为通过大量实验，模拟实际行为，来收集统计数据。本例中，算法随机产生一系列点，模拟这些点落在如下图所示的正方形区域内的情况。其几何解释如下图1如图1所示，正方形边长为1，左下顶点与原点重合，两边分别与x，y轴重合。曲线为1/4圆弧，圆心位于原点，与正方形左下定点重合，半径为1。正方形面积S1=1，圆弧内面积S2=。算法模拟大量点随机落在此正方形区域内，落在圆弧内的点的数量（n2）与点的总数（n1）的比例与面积成正比关系。即 （1）由此可得 （2）

4、因此，只要计算出落在圆弧内的点的数量在点总数中所占的比例，就能求出的值。由图1可知，所有点均落在正方形范围内，因此点的x坐标满足。又，当点落在圆弧范围内，则点的二维坐标关系满足。检验每一个点是否满足此关系即可判定改点是否落在圆弧内。二、 实验环境和软件编译器：Microsoft Visual Studio C+ 6.0操作系统：Windows XP 三、实验内容3.1 串行算法本项目中使用了标准C语言库中的产生随机数函数。该函数原型为：int rand( void );此函数产生随机数列，每次调用时均返回0到RAND_MAX之间的一个整数。void srand( unsigned int se

5、ed );此函数为rand（）函数所生成的伪随机数序列设置起始点，使之产生不同的伪随机数。算法：产生2n个随机数据，范围0，1，对每个数据点计算其坐标是否满足，统计满足此关系的点的数量count，则 3.2 并行算法描述算法步骤：1、确定需要产生的点的个数n，参与运行的处理器数m；2、对每一个处理器，生成两个随机数x，y，范围0，1；3、判断两个随机数x，y是否满足；4、若满足，则变量COUNTi+；5、重复步骤2-4，直至每个处理器均生成n/m个随机点；6、收集COUNTi的值，并累加至变量COUNT中，此即为随机点落在圆弧内的数量；7、通过（2）式计算的值。3.3 并行算法在Windows

6、下的一个例子#include#include#include /#include #include #include #includeusing namespace std;HANDLE evFinish;long cs=0; /总循环次数long count=0; /主线程有效次数long count_thread=0; /thread线程有效次数time_t start, finish; /定义开始结束时间/thread线程计算量为总数的一半DWORD WINAPI thread(LPVOID param)int i=0;double x,y;for(i=0;ics/2;i+)x=(lon

7、g double)rand()/(long double)RAND_MAX;y=(long double)rand()/(long double)RAND_MAX;if(x*x+y*y)=1) count_thread+;/printf(副%d ,i);SetEvent(evFinish);return 0;/主线程计算量为总数的一半int main (void) evFinish=CreateEvent(NULL,FALSE,FALSE,NULL); printf(请输入总循环次数:);scanf(%d,&cs);cs*=;srand( (unsigned)time( NULL ) );/用

8、时间作随机数种子 start=time(NULL); /记录开始时间HANDLE id=CreateThread(NULL,0,thread,NULL,0,NULL); /创建thread线程int i=0;double x,y;for(i=0;ics/2;i+)x=(long double)rand()/(long double)RAND_MAX;y=(long double)rand()/(long double)RAND_MAX;if(x*x+y*y)=1)count+;/printf(主%d,i);/printf(count%d,count);WaitForSingleObject(e

9、vFinish,INFINITE);/两线程同步count+=count_thread; finish=time(NULL); /记录结束时间printf(并行情况：nn); 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=(lon

10、g double)rand()/(long double)RAND_MAX;y=(long double)rand()/(long double)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);printf( 线程有效次数=%d次n,count);printf(pi= %f n,4*(double)count/(double)c

11、s);return(0);实验结果：测试数据集合：由随机数函数产生的数据集合 实验三 并行排序一、 实验目的与要求在单核计算环境中，排序算法关注的核心问题是怎样减少要排序数据之间的比较次数或算法所需要的内存空间。在多核计算环境中，每个核以线程为执行单元，排序程序可以通过生成相互协作的线程来完成排序。与单核计算环境不同的是，在多核计算环境中更关注数据集的合理划分，更致力于识别可并行执行的任务。一旦完成这些工作，程序设计上就可以生成对应的线程去执行任务。理论上，基于相同的串行算法和相同的cache命中率，多核计算速度可以无限接近单核计算速度的P倍，其中P为核的数目。多核上的并行排序算法所面临的问题

12、在于：1.未排序的数据集合理划分到每个线程后，最后怎么汇合，形成完整的排好序的数据集呢？2.怎么保证可并行执行的线程的数目和核的数目相等或稍微多于核的数目，同时也保证这些线程之间的工作量也尽可能的相同呢？在这个实验中，串行的算法采用标准C语言库中的快速排序函数。并行算法中，先将要处理的数据集均等的分到每个线程中，并使用C语言库中的快速排序函数各自排序。然后所有线程开始根据相同的数对自己的数据集进行划分，这个数是依据一定的方法选出来的（详见并行算法描述）。每个线程的数据集都会被分成K份，（其中P= K P2 ，P为核的数目），每份将被称为一桶。很显然这个过程选出了K个数，这些数将被成为bound

13、_value, 记为 X1, X2, X3 XK 。最后每个线程中小于或等于X1的数会被一个独立的线程去归并排序，同样小于或等于X2的数也会被另外一个独立的线程去归并排序，依次类推，直到排好序。需要指出的是：这个并行版本最消耗时间的部分是一开始每个线程各自的排序，时间为：O（）；不过其数据划分和线程生成也相对简单。最后的归并排序所需时间是线性增长的，即：O（），因此即使在最后归并部分线程执行的任务已经是不均衡的，也不会对整个程序的性能产生很大的影响。二、 实验环境和软件编译器：Microsoft Visual Studio C+ 6.0操作系统：Windows XP 三、 实验内容3.1 并行

14、算法描述算法:将原始待排序的数据分成P等份，每个处理器上对N0个数据进行排序，称每个被排序后的子集为B0,Bp-1Remain_data=N，设定第0组归并起始位置全部为0, i=0，设置第0组在目标数组中的起始位置为0循环直至remian_dataL( L=N0/P )3.1 选取所有子集中起始位置后续L个元素的最小值bound_value，并获得bound_value的桶号bucket3.2 在所有子集中从起始位置到后续L个元素中选取边界位置，使得边界位置的最后一个元素小于或等于bound_value，而边界位置后的第一元素大于bound_value。3.3 记录所有的边界位置，并设置所有

15、第i1组的起始位置为第i组的起始位置加上边界位置3.4 累积所有边界值，得到该归并组的大小3.5 根据归并组大小和本组起始位置计算第i+1组在目标数组中的起始位置。4、设置最后一个归并组的边界为N05、对所有归并组进行并行P路归并排序。四、 实验步骤说明：AP和多核处理器的数目相同。比如是双核的，那么P 2；BRemain_data是每个线程处理的数据集中还没有被X1, X2, X3划分过的数据集的总数目。比如，根据X1 每个线程划分出来的数据集为x，y，z,那么Remain_datan x y z. 并行算法在Windows下的一个例子#include #include #include #

16、include #include#include#ifndef _BASIC_SORT_H#define _BASIC_SORT_H#ifndef _SORT_P#define _SORT_Pvoid* sort(void* parameter);void generate_data(int *a,int n);void sort_s(int *a, int n);void view_data(int *a, int n);int check_data_sort(int *a,int n);int compare( const void *arg1, const void *arg2 );#d

17、efine MILLION L#define P 2#define N0 /#define N0 #define N N0*P#define L N0/Pvoid sort_p(int*d, int * b);time_t start, finish; /定义开始结束时间struct merge /归并结构int beginP; /数组beginint countP; /数组countint merge_size; /归并大小int global_pos; /全局位置int merged; /归并是否完成;struct arg_merge_data /归并数据结构int *d; /数组的指针s

18、truct merge* mp; /归并结构int *b; /整数bint k;struct arg_merge_data *tmp2;struct forsort int*d;int k;struct forsort forsortaP;int find_bound_value(int *d,struct merge *mp,int *bucket);int find_min(int *d,struct merge *mp,int *bucket);void find_bound(int *d,struct merge *mp,int bucket,int bound_value);void

19、 do_last_merge_block(struct merge *mp);void merge_data(void* arg);void view_merge(int *d,struct merge *mp,int last_merge_block);int start_time();int diff_time();#endif#endifint k; HANDLE SwaitP;HANDLE PwaitP;HANDLE pthreadP;HANDLE qthreadP;extern int *dP;/void generate_data(int *a, int n) /产生数据int i

20、;for(i=0;in;i+)ai=rand()%10000; /产生数组a 有n个元素for(i=0;ik);/=int kk=forsortb-k;qsort(/*(void*)*/forsortb-d, N0, sizeof(int), compare); SetEvent(Swaitkk);/printf(n%d,kk);return (void*)0;/void view_data(int *a, int n)int i=n,j;int index=0;while(iN0)for(j=0;j0;i-) /输出ai中N0后面的个数printf(%dt,aindex+);printf(n

21、);/int check_data_sort(int *a,int n) /找出不服和大小顺序的位置int i;for(i=0;iai+1) break;return i;/int compare( const void *arg1, const void *arg2 ) /返回arg1与arg2的差int a=*(int *)arg1,b=*(int *)arg2;return a-b;/int aN;/data for parallel sortint bN;/ the result of parallel sortint *dP;/ for parallel sortint sN;/da

22、ta for serial sortstruct merge m_listP*P;/record of partitionint merge_block; / the number of partitionDWORD thr_idP*P;long timedif;/ for estimate the exection time/struct timeval end; / ./struct timeval start;/ .void inite()int i;/forsorta=(struct forsort *) calloc(P, sizeof (struct forsort);for(i=

23、0;iP;i+)Swaiti=CreateEvent(NULL,FALSE,FALSE,NULL);Pwaiti=CreateEvent(NULL,FALSE,FALSE,NULL);/*for(int j=0;jP;j+)forsortai.dj=dj;/printf(forsorta%d.d%d=%dn,i,j,forsortai.dj);*/void main()int data;int i;generate_data(a, N); /产生数组anfor(i=0;ib%dn,data,data+1);/int start_time() /记录开始时间函数start=time(NULL);

24、 /记录开始时间return 0;/int diff_time() /记录结束时间并算时间差函数finish=time(NULL); /记录结束时间printf(用时=%f 秒 n,difftime(finish,start); /输出结果return 0;/void sort_p(int *d, int *b)/tmp2=(arg_merge_data *) calloc(merge_block + l, sizeof (struct arg_merge_data); int i;int remain_data=N; /剩余数据初始化 merge_block=0;/归并块=0start_ti

25、me(); for(i=0;iP;i+) /m_list0中的两个数组初始化m_list0.begini=0;m_list0.counti=0;m_list0.merge_size=0; /m_list0中的归并大小初始化m_list0.global_pos=0; /m_list0中的全局位置初始化for(i=0; iL*P) /剩余数据大于L*Pint bound_value;int bucket;bound_value=find_bound_value(d,&(m_listmerge_block),&bucket);find_bound(d,&(m_listmerge_block),buc

26、ket,bound_value);remain_data-=m_listmerge_block.merge_size; m_listmerge_block.merged=0;merge_block+;if(merge_block=P*P) /溢出处理printf(block partition is greater than P2n);break;printf(P路线程分别找出对应的最小值并重新划分L长，直至全部划分完毕时n);diff_time();start_time();do_last_merge_block(&(m_listmerge_block);/struct arg_merge_

27、data *tmp2;tmp2=(struct arg_merge_data *) calloc(merge_block, sizeof (struct arg_merge_data);/结构体数组分配空间for(i=0;i=merge_block;i+) tmp2i.k=i;tmp2i.d = d;tmp2i.mp = &(m_listi);tmp2i.b= &(bm_listi.global_pos);/pthread_create(&(thr_idi), NULL, &(merge_data), tmp2+i);/k=i;qthreadi=CreateThread(NULL,0, (LP

28、THREAD_START_ROUTINE)merge_data, tmp2+i,0,&(thr_idi);WaitForMultipleObjects (P, Pwait,TRUE,INFINITE); /pthread_join (thr_idi, NULL);printf(P路线程归并完成时n);diff_time();/int find_bound_value(int *d,struct merge *mp,int *bucket) /找出本块中的追小值赋给bucketint i;int min;int first=1;for(i=0;ibegini+Lbegini+L;*bucket=

29、i;first=0;elseif(min=dimp-begini+L)min=dimp-begini+L;*bucket=i;return min;/void find_bound(int *d,struct merge *mp,int bucket,int bound_value)int i;for(i=0;ibegini+Lbegini-1;dp=&(dimp-begini);if(tcount=1)if(dp0bound_value)tcount=0;elseif(dp0bound_value)tcount=0;else if(dptcountbegini+Lbegini-1;/mayb

30、e here has some problemelseint b=0,e=tcount;while(!(dp(e+b)/2bound_value)if(dp(e+b)/2bound_value)e=(e+b)/2;elseb=(e+b)/2;tcount=(e+b)/2+1;mp-counti=tcount;elsemp-counti=L+1;mp-merge_size=0;for(i=0;imerge_size+=mp-counti;mp1.begini=mp-begini+mp-counti;mp1.global_pos=mp-global_pos+mp-merge_size;/void

31、do_last_merge_block(struct merge *mp)int i;mp-merge_size=0;for(i=0;ibegini=N0)mp-counti=0;elsemp-counti=N0-mp-begini;mp-merge_size+=mp-counti;/void merge_data(void* arg)struct arg_merge_data* tmp = (struct arg_merge_data*)arg;struct merge temp_mp;int* b_temp = tmp-b;int i;int count;for(i=0;imp)-begini;temp_mp.counti=(tmp-mp)-counti;for(count=0;countmp)-merge_size;count+)int bucket;b_tempcount=find_min(tmp-d),&temp_mp,&bucket);temp_mp.beginbucket+;temp_mp.countbucket-;SetEvent(Pwaittmp-k);/int find_min(int *d,struct merge *mp,int *bucket)int i;int first=1;int min_value;for(i=0;i