并行计算课程设计报告剖析.docx
- 文档编号:17141669
- 上传时间:2023-07-22
- 格式:DOCX
- 页数:59
- 大小:322.77KB
并行计算课程设计报告剖析.docx
《并行计算课程设计报告剖析.docx》由会员分享,可在线阅读,更多相关《并行计算课程设计报告剖析.docx(59页珍藏版)》请在冰点文库上搜索。
并行计算课程设计报告剖析
并行计算与多核多线程技术
课程报告
专业
班级
学号
姓名
成绩___________________
年月日
课程报告要求
手写内容:
设计目的、意义,设计分析,方案分析,功能模块实现,最终结果分析,设计体会等。
允许打印内容:
设计原理图等图形、图片,电路图,源程序。
硬件类的设计,要有最终设计的照片图;软件类设计,要有各个功能模块实现的界面图、输入输出界面图等。
评价
理论基础
实践效果(正确度/加速比)
难度
工作量
独立性
1.设计目的、意义(功能描述)
设计一个计算向量夹角的WinForm窗体应用,用户只需要在窗体上输入向量的维度,系统随机产生两个向量并将计算结果显示在窗体上。
求两个n维向量的夹角,要用到求向量夹角的数学公式,当向量维度较小时计算量不大,而当维度过大时特别是百万级甚至千万级别的时候计算量就很大了,用并行计算求向量夹角,可以将任务分配给多个处理器,减小运算时间。
所以要设计一个并行计算夹角的方法,提高计算速度,把并行和串行计算时间做个比较显示在窗体上。
窗体应用比控制台程序更方便用户操作,简单直观,页面也更加友好。
2.方案分析(解决方案)
定义两个数组分别存放两个向量,用for循环将产生的随机数赋值给数组。
假设有两个向量X,YX=(x1,x2,……,xn),Y=(y1,y2,……,yn)计算X,Y夹角的公式是:
cos(X,Y)=XY/(|X|·|Y|)=(x1·y1+x2·y2+…+xn·yn)/[(x1²+x2²+…+xn²)1/2·(y1²+y2²+…+yn²)1/2]。
由3个for循环分别实现求向量积和两个向量的模,最后用公式计算即可。
3.设计分析
3.1串行算法设计
输入:
向量的维度n
输出:
两个随机向量的夹角syy_angle
Begin
给存放向量的数组动态分配内存空间
Fori=0toi=n-1do
产生随机数给数组x赋值
endFor
Fori=0toi=n-1do
产生随机数给数组y赋值
endFor
Fori=0toi=n-1do
计算向量积
endFor
Fori=0toi=n-1do
计算向量X模
endFor
Fori=0toi=n-1do
计算向量Y模
endFor
利用公式计算夹角
End
3.2并行算法设计
输入:
向量的维度n
输出:
两个随机向量的夹角syy_angle
Begin
给存放向量的数组动态分配内存空间
Fori=0toi=n-1do
产生随机数给数组x赋值
endFor
Fori=0toi=n-1do
产生随机数给数组y赋值
endFor
3个for循环串行执行,每个for循环由p个核并行执行:
p个核同时执行第一个for循环
Fori=0toi=n-1do
计算向量积
endFor
p个核同时执行第二个for循环
Fori=0toi=n-1do
计算向量X模
endFor
p个核同时执行第三个for循环
Fori=0toi=n-1do
计算向量Y模
endFor
利用公式计算夹角
End
3.3理论加速比分析
设加速比为S,串行运行时间为Ts,并行的运行时间为Tp。
假设一次运算作为一个时间单位,对于串行算法来说其时间复杂度为O(n)即Ts=O(n),对于并行算法来说,由于有p个处理器同时运行,则其时间复杂度为O(n/p)即Tp=O(n/p),所以理论加速比S=Ts/Tp=O(n)/O(n/p)=p。
4.功能模块实现与最终结果分析
4.1基于OpenMP的并行算法实现
4.1.1主要功能模块与实现方法
1:
向量x,y赋值,用产生的随机数对存放向量的数组赋值,得到两个随机向量
srand((int)time(0));
//数组X赋值
for(i=0;i { j=(int)(100*rand()/(RAND_MAX+1.0));//随机产生的数 x[i]=j; } //数组Y赋值 for(i=0;i { j=(int)(100*rand()/(RAND_MAX+1.0));//随机产生的数 y[i]=j; } 2: 计算向量积,向量x,y的模用并行实现。 设置两个线程,用reduction实现并行计算,两个线程都会创建一个reduction变量的私有副本,在OPENMP区域结束后,将各个线程的计算结果相加赋值给原来的变量。 #pragmaompparallelforreduction(+: syy_outer_product) for(i=0;i { syy_outer_product=syy_outer_product+x[i]*y[i];//计算向量积 } 计算向量X,Y的模方法与上面类似 4.1.2实验加速比分析 线程数设置为2时,向量维数小时,由于精度问题,运行时间显示为0,加速比无法计算。 向量维数到达百万级以上,加速比介于1到2之间,根据向量维数的变化,加速比有一定的变化但不会超过范围。 4.2基于MPI的并行算法实现 4.2.1主要功能模块与实现方法 使用MPI群集通信,由0进程接收输入的数组长度n,给数组动态分配内存后,用产生的随机数给数组赋值。 用MPI_Bcast先将数组长度广播给其他进程,由其他进程给数组动态分配内存后,再将数组值广播给其他进程。 求向量积,向量模的for由多个进程同时执行,将0到n-1次循环分配给P个进程,每个进程从i=myid开始执行,循环一次i加进程数。 将每个进程的计算结果用MPI_Reduce函数规约。 1: 由0进程进行随机数组动态分配内存和赋值操作 if(myid==0) { ……… //为数组x,y动态分配空间 x=(int*)malloc(n*sizeof(int)); y=(int*)malloc(n*sizeof(int)); srand((int)time(0)); //数组X赋值 for(i=0;i { j=(int)(10*rand()/(RAND_MAX+1.0));//随即产生的数 x[i]=j; } 数组y赋值同上 } starttime=MPI_Wtime(); } 2: 用MPI_Bcast()函数将数组长度和值广播给其他进程 MPI_Bcast(&n,1,MPI_LONG,0,MPI_COMM_WORLD);//将n值广播出去 MPI_Bcast(x,n,MPI_INT,0,MPI_COMM_WORLD);//将x值广播出去 MPI_Bcast(y,n,MPI_INT,0,MPI_COMM_WORLD);//将y值广播出去 3: 用MPI_Reduce()函数对各个进程的计算结果规约 MPI_Reduce(&my_product,&syy_outer_product,1,MPI_LONG_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD); MPI_Reduce(&my_mol_x,&syy_mol_x,1,MPI_LONG_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD); MPI_Reduce(&my_mol_y,&syy_mol_y,1,MPI_LONG_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD); 4: 多个进程同时执行for循环 for(i=syy_myid;i { product+=x[i]*y[i];//计算向量积 } 计算向量x,y模与上面类似 5: 串行部分由0进程完成,在执行完并行计算后,再由0进程单独完成串行操作.if(syy_myid==0)里执行的串行操作 4.2.2实验加速比分析 并行时间比串行时间要长,加速比低于1,MPI并行是进程间相互通信传递数据。 设置两个进程时,在0进程里输入向量维度,由0进程对向量数组赋值。 再将n值和x,y动态数组广播给其他进程。 串行计算只有0进程独立完成,可能是进程间通信过多使并行额外开销太大。 4.3基于Java的并行算法实现 4.3.1主要功能模块与实现方法 1: 继承Thread类,创建两个线程thread1,thread2。 用start方法开始线程。 使用join()方法等待线程结束后再继续执行。 javaandthread1=newjavaand(0,n,x,y); javaandthread2=newjavaand(1,n,x,y); startTime=System.currentTimeMillis(); thread1.start(); thread2.start(); thread1.join(); thread2.join(); 2: 两个线程同时执行run函数,thread1循环从0到n-1,每次循环i加2,thread2循环从1到n-1,每次循环i加2.最后两个线程的计算结果相加 publicvoidrun(){ for(longi=start;i syy_outer_product+=x[(int)i]*y[(int)i];//计算向量积 } for(longi=start;i syy_mol_x+=x[(int)i]*x[(int)i];//计算向量X模 } for(longi=start;i syy_mol_y+=y[(int)i]*y[(int)i];//计算向量Y模 } } 3: 用count函数实现串行计算,循环从0到n-1,每次循环i加1.循环部分代码与run方法中类似。 分别用三个循环计算向量积,向量X,Y模后再根据公式计算向量夹角,最后返回运算结果。 4.3.2实验加速比分析 数据量较小时,串并行显示的时间都为0,因此无法计算加速比,当数据量较大时加速比控制在1-2之间。 输入向量的维度超过100000000时,出现内存溢出,无法计算加速比。 数组长度定义过大时,程序消耗内存过大会出现内存溢出,即使是修改JVM-Xmx参数后,向量维度也不能超过100000000 4.4基于WindowsAPI的并行算法实现 4.4.1主要功能模块与实现方法 1: 创建两个线程thread1,thread2,分别指定线程函数为ThreadOneThreadTwo创建成功后返回线程的句柄,等待两个线程计算完后将两个线程的执行结果相加 HANDLEthread1=CreateThread(NULL,0,ThreadOne,NULL,0,NULL); HANDLEthread2=CreateThread(NULL,0,ThreadTwo,NULL,0,NULL); WaitForMultipleObjects(2,finish,true,INFINITE); for(inti=0;i<2;i++) { syy_outer_product+=product[i]; syy_mol_x+=mol_x[i]; syy_mol_y+=mol_y[i]; } 2: 并行线程函数,将n次循环分成两部分,线程函数ThreadOne执行前半部分操作,函数ThreadTwo执行后半部分操作 Thread1线程函数负责for循环从0到(n/2)-1: DWORDWINAPIThreadOne(LPVOIDparam) Thread2线程函数负责for循环从n/2到n-1: DWORDWINAPIThreadTwo(LPVOIDparam) 3: 线程函数ThreadThree作为单线程执行,for循环从0到n-1 DWORDWINAPIThreadThree(LPVOIDparam) 4.4.2实验加速比分析 串行和并行运算结果相同,但并行比串行时间大。 从理论上分析,两个线程同时执行for循环,加速比应该在1-2之间,而实际情况是并行比串行时间还久。 WaitForMultipleObjects(2,finish,true,INFINITE);这句运行时间长,使用WaitForMultipleObjects 函数是让线程进入等待状态,直到finishi指向的内核对象都变为已通知状态。 先完成工作的处理器要等待未完成工作的处理器,处理器空闲时间太大可能会造成并行比串行时间大。 4.5基于.net的并行算法实现 4.5.1主要功能模块与实现方法 1: 创建ThreadStart代理,即thread1,thread2。 指定Work类的sum函数作为两个线程执行的线程函数。 将thread1,thread2代理传递给Thread类的构造函数,最后调用Thread类的Start方法开启线程。 Join方法可以保证应用程序域等待异步线程结束后才终止运行。 Workwork1=newWork(0,n,x,y); ThreadStartthread1=newThreadStart(work1.Sum); Threadnewthread1=newThread(thread1); Workwork2=newWork(1,n,x,y); ThreadStartthread2=newThreadStart(work2.Sum); Threadnewthread2=newThread(thread2); 2: 用于实现并行计算的Work类的Sum函数。 newthread1执行的循环是从0到n-1,每次循环i加2。 newthread2执行的循环是从1到n-1,每次循环i加2。 计算向量积的for循环如下: for(longi=start;i { syy_outer_product+=x[i]*y[i];//计算向量积 } 3: 调用Work类的sumto函数实现串行计算,并返回计算得到的夹角。 用3个for循环分别计算向量积和x,y的模,循环从0到n-1,每次i加1,最后用公式计算夹角。 4.5.2实验加速比分析 设置两个线程同时计算,能得到较理想的加速比,数据量为十几时,加速比在1.8左右,数据量达到10000000000时,加速比能接近1.9.从总体的运行结果看,加速比在1.7到1.9之间,符合理论加速比的分析。 4.6并行计算技术在实际系统中的应用 4.6.1主要功能模块与实现方法 1: 确认按钮点击事件函数,当点击确认按钮后从文本框中获取向量的维度,传递给count函数: privatevoidconfirm_Click(objectsender,EventArgse) 2: 从窗体中获取向量维度后用count函数计算夹角,并把结果返回给窗体。 用并行和串行方法计算的代码全部放在count函数里进行 publicvoidcount(longn) 3: 创建两个线程实现并行计算 创建两个线程代理thread1,thread2指定线程函数Work类里的Sum函数,然后将ThreadStart代理传递给Thread类的构造函数 Workwork1=newWork(0,n,x,y); ThreadStartthread1=newThreadStart(work1.Sum); Threadnewthread1=newThread(thread1); Workwork2=newWork(1,n,x,y); ThreadStartthread2=newThreadStart(work2.Sum); Threadnewthread2=newThread(thread2); 4: 用于实现并行计算的Work类的Sum函数。 newthread1执行的循环是从0到n-1,每次循环i加2。 newthread2执行的循环是从1到n-1,每次循环i加2。 计算向量积的for循环如下: for(longi=start;i { syy_outer_product+=x[i]*y[i];//计算向量积 } 5: 调用Work类的sumto函数实现串行计算,并返回计算得到的夹角。 用3个for循环分别计算向量积和x,y的模,循环从0到n-1,每次i加1,最后用公式计算夹角。 4.6.2实验加速比分析 当数据量较小时加速比接近于1,比较小。 当数据量大的时候,加速比有时会超过2,甚至接近于3,与理论分析的加速比有出入。 可能跟WinForm窗体运行环境有关,用C#语言写的程序占用内存小加速比高。 5.设计体会 这次课程设计是用了5种不同的方法实现求n维随机向量的夹角,在具体的编程过程中遇到了很多问题,在解决问题过程中也有不少收获,下面我就这五种实现方法谈谈我的设计体会。 用OpenMP编程时为了解决数据竞争的问题,我使用了reduction字句,在进入并行区域后两个线程就有各自的变量的副本,只要变量不公用,就不存在数据竞争的问题。 OpenMP的编程是在parallel并行区内并行计算,我觉得相比其他四个编程方法这个更简单。 在MPI编程中,我遇到了最大的问题是不知道如何广播动态数组,后来上网查询,找到了一个解决方案是先将数组长度广播出去,然后非0进程动态非配空间后再广播该数组。 用java语言编写程序时,很多程序语言需要利用外部的线程软件包来实现多线程,而java语言则内在支持多线程,它的所有类都是在多线程的思想下定义的。 Java编程中实现多线程有两种办法: 一种是用户在自己定义的类中使用Runnable接口,另一种是继承Thread类。 我用的就是第二种方法,在run函数中实现并行,在count函数中实现串行。 .net编程有很多地方与java相似,用两个线程做并行计算,都要先创建进程,但.net创建线程首先需要创建ThreadStart代理,指定线程执行的线程函数,然后再创建Thread类线程,将ThreadStart代理传递给Thread类的构造函数。 线程函数有点类似于javaThread类里的run函数,都是两个线程同时执行的函数。 Win32API编程不需要配置编程环境,应用程序只需要调用相关的函数就行,Win32API提供了一系列处理线程的函数接口,向应用程序提供多线程的功能。 总之,每种实现方法都各有特点。 用不同的语言实现同一种算法,在具体的编程过程中也会有细小的差异,每一次修正错误都是一次学习。 6.附录 6.1基于OpenMP的并行程序设计 6.1.1代码及注释 (变量名名字首字母开头) #include"stdafx.h" #include #include #include #include #include #include #defineNUM_THREADS2 int_tmain(intargc,_TCHAR*argv[]) { intj;//随机数 longlongi; longlongn; longdoublesyy_outer_product=0,syy_mol_x=0,syy_mol_y=0,syy_angle;//向量积 clock_tt1,t2,t3,t4; printf("两条n维随即向量的夹角串并行计算\n"); printf("请输入向量的维度: \n"); scanf("%lld",&n); //为数组x,y动态分配空间 int*x=(int*)malloc(n*sizeof(int)); int*y=(int*)malloc(n*sizeof(int)); srand((int)time(0)); //数组X赋值 for(i=0;i { j=(int)(100*rand()/(RAND_MAX+1.0));//随即产生到的数 x[i]=j; } //数组Y赋值 for(i=0;i { j=(int)(100*rand()/(RAND_MAX+1.0));//随即产生到的数 y[i]=j; } /*串行区域*/ t1=clock(); for(i=0;i { syy_outer_product=syy_outer_product+x[i]*y[i];//计算向量积 } for(i=0;i { syy_mol_x=syy_mol_x+x[i]*x[i];//计算向量X模 } for(i=0;i { syy_mol_y=syy_mol_y+y[i]*y[i];//计算向量Y模 } t2=clock(); t3=t2-t1;//串行时间 syy_mol_x=sqrt(syy_mol_x); syy_mol_y=sqrt(syy_mol_y); syy_angle=syy_outer_product/(syy_mol_x*syy_mol_y); printf("随即产生两个向量,向量的夹角cos(x,y)=%f\n",syy_angle); printf("串行时间=%d\n",(t2-t1)); syy_mol_x=0; syy_mol_y=0; syy_outer_product=0; omp_set_num_threads(NUM_THREADS);//设置线程数 t1=clock(); /*并行区域*/ #pragmaompparallelforreduction(+: syy_outer_product) for(i=0;i { syy_outer_product=syy_outer_product+x[i]*y[i];//计算向量积 } #pragmaompparallelforreduction(+: syy_mol_x) for(i=0;i { syy_mol_x=syy_mol_x+x[i]*x[i];//计算向量X模 } #pragmaompparallelforreduction(+: syy_mol_y) for(i=0;i { syy_mol_y=syy_mol_y+y[i]*y[i];//计算向量Y模 } t2=clock(); t4=t2-t1;//并行时间 syy_mol_x=sqrt(syy_mol_x); syy_mol_y=sqrt(syy_mol_y); syy_angle=syy_outer_product/(syy_mol_x*syy_m
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 并行 计算 课程设计 报告 剖析