2022年燕山大学多核程序设计实验报告 .pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《2022年燕山大学多核程序设计实验报告 .pdf》由会员分享,可在线阅读,更多相关《2022年燕山大学多核程序设计实验报告 .pdf(21页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1 实验一Windows多线程编程一、实验目的与要求了解 windows 多线程编程机制掌握线程同步的方法二、实验环境和软件Windows XP VC 6.0 三、实验内容创建线程:HANDLE CreateThread ( LPSECURITY_ATTRIBUTES lpThreadAttributes, SIZE_T dwStackSize, LPTHREAD_START_ROUTINE lpStartAddress, LPVOID lpParameter, DWORD dwCreationFlags, LPDWORD lpThreadId ); 四、实验程序#includestdafx.
2、h #include #include #include #include using namespace std; void ThreadFrunc1(PVOID param) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 21 页 - - - - - - - - - 2 while(1) Sleep(1000); coutThis is ThreadFrunc1endl; void ThreadFrunc2(PVOID param) while(1) Sleep(1
3、000); coutThis is kjj ThreadFrunc2endl; int main() int i=0; _beginthread(ThreadFrunc1,0,NULL); _beginthread(ThreadFrunc2,0,NULL); Sleep(3000); coutendendl; return 0; 实验结果实验二蒙特卡罗法求PI 一、实验目的和要求名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 21 页 - - - - - - - - -
4、3 蒙特卡洛算法可理解为通过大量实验,模拟实际行为,来收集统计数据。本例中,算法随机产生一系列点,模拟这些点落在如下图所示的正方形区域内的情况。其几何解释如下X 轴Y轴11图 1 如图 1 所示,正方形边长为1,左下顶点与原点重合,两边分别与x,y 轴重合。曲线为1/4 圆弧,圆心位于原点,与正方形左下定点重合,半径为1。正方形面积S1=1,圆弧内面积S2=41412r。算法模拟大量点随机落在此正方形区域内,落在圆弧内的点的数量(n2) 与点的总数 (n1)的比例与面积成正比关系。即42121SSnn(1)由此可得124nn(2)因此,只要计算出落在圆弧内的点的数量在点总数中所占的比例,就能求
5、出的值。由图 1 可知,所有点均落在正方形范围内,因此点的x 坐标满足10 x。又,当点落在圆弧范围内,则点的二维坐标关系满足122yx。检验每一个点是否满足此关系即可判定改点是否落在圆弧内。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 21 页 - - - - - - - - - 4 二、实验环境和软件编译器: Microsoft Visual Studio C+ 6.0 操作系统: Windows XP 三、实验内容3.1 串行算法本项目中使用了标准C语言库中的产生
6、随机数函数。该函数原型为:int rand( void ); 此函数产生随机数列,每次调用时均返回0 到 RAND_MAX之间的一个整数。void srand( unsigned int seed ); 此函数为rand()函数所生成的伪随机数序列设置起始点,使之产生不同的伪随机数。算法:产生 2n 个随机数据, 范围 0 ,1 ,对每个数据点计算其坐标是否满足122yx, 统 计 满 足 此 关 系 的 点 的数 量count, 则ncount43.2 并行算法描述算法步骤:1、确定需要产生的点的个数n,参与运行的处理器数m ;2、对每一个处理器,生成两个随机数x,y,范围 0 ,1 ;3、
7、判断两个随机数x,y 是否满足122yx;4、若满足,则变量COUNTi+ ;5、重复步骤2-4 ,直至每个处理器均生成n/m个随机点;6、收集 COUNTi的值,并累加至变量COUNT 中,此即为随机点落在圆弧内的数量;7、通过( 2)式计算的值。3.3 并行算法在 Windows下的一个例子名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 21 页 - - - - - - - - - 5 #include #include #include /#include #inc
8、lude #include #include using 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=(long double)rand()/(long double)RAND_MAX;
9、 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*=1000000; srand( (unsigned)time( NULL ) );/用时间作随机数种子名师资料总结 - - -精
10、品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 21 页 - - - - - - - - - 6 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 do
11、uble)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(并行情况: nn); printf(用时 =%f 秒n,difftime(finish,start); / 计算时间差printf(总共的循环次数=%d次n,cs); printf( 线程有效次数 =%d次n,count); printf(pi
12、= %f n,4*(double)count/(double)cs); printf(串行行情况:n); count=0; start=time(NULL); /记录开始时间for(i=0;ics;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); finish=time(NULL); /记录结束时间 printf(用时 =%f 秒n
13、,difftime(finish,start); printf(总共的循环次数=%d次n,cs); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 21 页 - - - - - - - - - 7 printf( 线程有效次数 =%d次n,count); printf(pi= %f n,4*(double)count/(double)cs); return(0); 实验结果:测试数据集合:由随机数函数产生的数据集合实验三并行排序一、实验目的与要求在单核计算环境中,排序算法
14、关注的核心问题是怎样减少要排序数据之间的比较次数或算法所需要的内存空间。在多核计算环境中,每个核以线程为执行单元,排序程序可以通过生成相互协作的线程来完成排序。与单核计算环境不同的是,在多核计算环境中更关注数据集的合理划分,更致力于识别可并行执行的任务。一旦完成这些工作,程序设计上就可以生成对应的线程去执行任务。理论上,基于相名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 21 页 - - - - - - - - - 8 同的串行算法和相同的cache 命中率,多核计算速
15、度可以无限接近单核计算速度的P倍,其中P为核的数目。多核上的并行排序算法所面临的问题在于:1. 未排序的数据集合理划分到每个线程后,最后怎么汇合,形成完整的排好序的数据集呢?2. 怎么保证可并行执行的线程的数目和核的数目相等或稍微多于核的数目,同时也保证这些线程之间的工作量也尽可能的相同呢?在这个实验中,串行的算法采用标准C语言库中的快速排序函数。并行算法中,先将要处理的数据集均等的分到每个线程中,并使用C语言库中的快速排序函数各自排序。然后所有线程开始根据相同的数对自己的数据集进行划分, 这个数是依据一定的方法选出来的(详见并行算法描述) 。每个线程的数据集都会被分成K份, (其中 P= K
16、 P2 ,P为核的数目) ,每份将被称为一桶。很显然这个过程选出了K 个数,这些数将被成为bound_value, 记为 X1, X2, X3 XK 。最后每个线程中小于或等于X1的数会被一个独立的线程去归并排序,同样小于或等于X2的数也会被另外一个独立的线程去归并排序,依次类推,直到排好序。需要指出的是:这个并行版本最消耗时间的部分是一开始每个线程各自的排序,时间为:O (lognn) ;不过其数据划分和线程生成也相对简单。最后的归并排序所需时间是线性增长的,即:O (n) ,因此即使在最后归并部分线程执行的任务已经是不均衡的,也不会对整个程序的性能产生很大的影响。二、实验环境和软件编译器:
17、 Microsoft Visual Studio C+ 6.0 操作系统: Windows XP 三、实验内容3.1 并行算法描述算法 : 将原始待排序的数据分成P等份,每个处理器上对N0个数据进行排序, 称每个被排序后的子集为B0,Bp-1 Remain_data=N,设定第0 组归并起始位置全部为0, i=0,设置第0 组在名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 21 页 - - - - - - - - - 9 目标数组中的起始位置为0 循环直至remian_
18、dataL( L=N0/P ) 3.1 选取所有子集中起始位置后续L 个元素的最小值bound_value ,并获得 bound_value 的桶号 bucket 3.2 在所有子集中从起始位置到后续L 个元素中选取边界位置,使得边界位置的最后一个元素小于或等于bound_value ,而边界位置后的第一元素大于 bound_value 。3.3 记录所有的边界位置, 并设置所有第i 1 组的起始位置为第i 组的起始位置加上边界位置3.4 累积所有边界值,得到该归并组的大小3.5 根据归并组大小和本组起始位置计算第i+1 组在目标数组中的起始位置。4、设置最后一个归并组的边界为N0 5、对所有
19、归并组进行并行P路归并排序。四、实验步骤说明:AP和多核处理器的数目相同。比如是双核的,那么P 2 ;BRemain_data 是每个线程处理的数据集中还没有被X1, X2, X3划分过的数据集的总数目。比如,根据 X1 每个线程划分出来的数据集为x, y, z , 那么 Remain_data n x y z . 并行算法在Windows下的一个例子#include #include #include #include #include #include #ifndef _BASIC_SORT_H #define _BASIC_SORT_H #ifndef _SORT_P #define _
20、SORT_P void* sort(void* parameter); void generate_data(int *a,int n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 21 页 - - - - - - - - - 10 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
21、*arg1, const void *arg2 ); #define MILLION 1000000L #define P 2 #define N0 4332539 /#define N0 1000000 #define N N0*P #define L N0/P void sort_p(int*d, int * b); time_t start, finish; /定义开始结束时间struct merge /归并结构int beginP; /数组 begin int countP; /数组 count int merge_size; /归并大小int global_pos; /全局位置int
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年燕山大学多核程序设计实验报告 2022 燕山 大学 多核 程序设计 实验 报告
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内