七种方法求水仙花数.doc

并行计算与多核多线程技术课程报告 班级 学号 姓名 _ 水仙花数目 录 1.水仙花数的并行算法设计与实现7 1.1 .1功能描述1.1.2 解决方案1.2算法设计 71.2.1 串行算法设计 1.2.2并行算法设计1.3 基于OpenMP的并行算法实现8 1.3.1 代码及注释（变量名 名字首字母 开头） 1.3.2 执行结果截图（体现串行时间、并行时间和加速比） 1.3.3 遇到的问题及解决方案1.4 基于MPI的并行算法实现11 1.4.1 代码及注释（变量名 名字首字母 开头） 1.4.2 执行结果截图（体现串行时间、并行时间和加速比）1.4.3 遇到的问题及解决方案1.5 基于Java（Runnable）的并行算法实现13 1.5.1 代码及注释（变量名 名字首字母 开头） 1.5.2 执行结果截图（体现串行时间、并行时间和加速比）1.5.3 遇到的问题及解决方案1.6 基于Windows（.NET）的并行算法实现20 1.6.1 代码及注释（变量名 名字首字母 开头） 1.6.2 执行结果截图（体现串行时间、并行时间和加速比） 1.6.3 遇到的问题及解决方案2. 理论基础22 2.1 并行计算机体系结构、并行计算模型、并行算法的概念 2.2并行计算机体系结构、并行计算模型、并行算法的关系 2.3实例说明并行计算机体系结构、并行计算模型、并行算法的关系评价实践效果（正确度/加速比）理论基础难度工作量独立性认证结果1.水仙花数的并行算法设计与实现1.1 .1功能描述水仙花数又称阿姆斯特朗数。是指一种三位数，其各个数之立方和等于该数本身。水仙花数只是自幂数的一种，严格来说三位数的3次幂数才成为水仙花数。1.1.2 解决方案并行思想：并行计算的原理就是把一个任务或者作业分配到多个处理器上并发执行。这样一来可以大大提高计算的效率。在本次课题中，要实现水仙花数的并行计算输出，就是把制定范围内的数用多个处理器进行计算，从而得到水仙花数的并行输出。再和串行执行方法进行比较，观察其优越性。核心算法： int hundreds = n / 100; int tens = n % 100 / 10; int ones = n % 10; Return cube(hundreds) + cube(tens) + cube(ones) = n;1.2算法设计1.2.1 串行算法设计 for(xlh=100;xlh1000;xlh+) j=xlh/100; z=(xlh-100*j)/10; t=xlh%10; if(j*j*j+z*z*z+t*t*t=xlh) printf(%dn,xlh);1.2.2 并行算法设计 for (int xlh=100+ id; xlh 1000; xlh+=2) /1000以内的水仙花数 int j=xlh/100; /判断百位 int z=xlh%100/10;/判断十位 int t=xlh%10;/个位 if(j*j*j+z*z*z+t*t*t =xlh)/确定是否是水仙花数 printf(%dn,xlh);/输出水仙花数 1.3 基于OpenMP的并行算法实现1.3.1 代码及注释（变量名 名字首字母 开头）#include stdafx.h#include Windows.h#include math.h#include #include #includeusing namespace std;int _tmain(int argc, _TCHAR* argv) printf(求水仙花数n); cout并行结果：endl; clock_t t1=clock();/线程1#pragma omp parallel for/并行开始 for(int i=100; i1000; i+)/判断是否为水仙花数 int xlh=i/100; int k=(i-100*xlh)/10; int l=i%10; Sleep(1); if(xlh*xlh*xlh+k*k*k+l*l*l=i) printf(%dn,i); clock_t t2=clock();/并行结束 double pt=t2-t1-0.0; printf(并行时间%fn,pt-0.0);/输出并行时间 clock_t t3=clock();/串行开始 for(int i=100; i1000; i+) int xlh=i/100; int k=(i-100*xlh)/10; int l=i%10; Sleep(1); if(xlh*xlh*xlh+k*k*k+l*l*l=i) printf(%dn,i); clock_t t4=clock();/串行结束 double st=t4-t3-0.0; printf(串行时间%fn,st-0.0); printf(加速比%fn,st/pt); system(pause); return 0;1.3.2 执行结果截图（体现串行时间、并行时间和加速比）1.3.3 遇到的问题及解决方案错误代码int xlh,j,z,t,m,n; int id=omp_get_thread_num(); omp_set_num_threads(NUM_THREADS); clock_t t1=clock(); #pragma omp parallel for(xlh=100+id;xlh1000;xlh+=NUM_THREADS)/判断是否为水仙花数 j=xlh/100; z=(xlh-100*j)/10; t=xlh%10; if(j*j*j+z*z*z+t*t*t=xlh) printf(%dn,xlh); clock_t t2=clock(); printf(并行时间%dn,t2-t1); printf(串行水仙花数：n); clock_t t3=clock();/ for(xlh=100;xlh1000;xlh+) j=xlh/100; z=(xlh-100*j)/10; t=xlh%10; if(j*j*j+z*z*z+t*t*t=xlh) printf(%dn,xlh); clock_t t4=clock();正确代码int _tmain(int argc, _TCHAR* argv) printf(求水仙花数n); cout并行结果：endl; clock_t t1=clock();/线程1#pragma omp parallel for/并行开始 for(int i=100; i1000; i+)/判断是否为水仙花数 int xlh=i/100; int k=(i-100*xlh)/10; int l=i%10; Sleep(1); if(xlh*xlh*xlh+k*k*k+l*l*l=i) printf(%dn,i); clock_t t2=clock();/并行结束 double pt=t2-t1-0.0; printf(并行时间%fn,pt-0.0);/输出并行时间 clock_t t3=clock();/串行开始 for(int i=100; i1000; i+) int xlh=i/100; int k=(i-100*xlh)/10; int l=i%10; Sleep(1); if(xlh*xlh*xlh+k*k*k+l*l*l=i) printf(%dn,i); clock_t t4=clock();/串行结束 分析对并行算法设计不熟悉。逻辑混乱，写代码有错误。1.4 基于MPI的并行算法实现1.4.1 代码及注释（变量名 名字首字母 开头）#include stdafx.h#include #include int main(int argc,char * argv)int id,numpro;double startime01,endtime01,startime02,endtime02;MPI_Init (&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD,&id);MPI_Comm_size(MPI_COMM_WORLD,&numpro);startime01 =MPI_Wtime();printf(水仙花数:n);if(id=0)/并行 for (int xlh=100+ id; xlh 1000; xlh+=2) /1000以内的水仙花数 int j=xlh/100; /判断百位 int z=xlh%100/10;/判断十位 int t=xlh%10;/个位 if(j*j*j+z*z*z+t*t*t =xlh)/确定是否是水仙花数 printf(%dn,xlh);/输出水仙花数 if(id=0) endtime01=MPI_Wtime(); printf(并行时间：%fn,endtime01-startime01);/输出并行时间if(id=0)/串行 startime02=MPI_Wtime(); printf(水仙花数：n); for (int xlh =100; xlh 1000; xlh+=1) int j=xlh/100; int z=xlh%100/10; int t=xlh%10; if(j*j*j+z*z*z+t*t*t =xlh) printf(%dn,xlh); endtime02=MPI_Wtime(); printf(串行时间：%fn,endtime02-startime02);MPI_Finalize();system(pause);return 0;1.4.2 执行结果截图（体现串行时间、并行时间和加速比）1.4.3 遇到的问题及解决方案后果分析环境配置错误，在配置MPI的环境时花了很多时间，在自己电脑上运行一直出错，后来在机房运行成功的。1.5 基于Java（Runnable）的并行算法实现1.5.1 代码及注释（变量名 名字首字母 开头）importjava.lang.Thread;publicclassJavaThreadextendsThreadprivateintstart;privateintend;privateintsum=0;publicJavaThread(intstart,intend)super();this.start=start;this.end=end;publicvoidrun()/并行函数inta,b,c;for(intxlh=start;xlh100&xlh1000)sum+;System.out.println(xlh);publicintFlower()throwsInterruptedException/串行函数inta,b,c;sum=0;for(intxlh=start;xlh100&xlh1000)sum+;System.out.println(xlh);returnsum;publicintgetSum()returnsum;publicstaticvoidmain(String args)throwsInterruptedExceptionJavaThread thread1=newJavaThread(1,1000);/确定开始以及结束值JavaThread thread2=newJavaThread(2,1000);System.out.println(并行结果:);longstartTime=System.currentTimeMillis();/并行开始thread1.start();thread2.start();thread1.join();thread2.join();longendTime=System.currentTimeMillis();System.out.println(并行时间:+(endTime-startTime);doublet1=endTime-startTime;startTime=System.currentTimeMillis();/并行结束System.out.println(串行结果:);JavaThread thread=newJavaThread(1,1000);thread.Flower();endTime=System.currentTimeMillis();System.out.println(串行时间:+(endTime-startTime);doublet2=endTime-startTime;System.out.println(加速比+t2/t1);1.5.2 执行结果截图（体现串行时间、并行时间和加速比）1.5.3 遇到的问题及解决方案错误代码及后果importjava.lang.Thread;classJavaThreadextendsThreadprivateintstart;privateintend;privateintsum=0;publicJavaThread(intstart,intend)super();this.start=start;this.end=end;publicvoidrun()/并行函数inta,b,c;for(intxlh=start;xlh=end;xlh+=2)a=xlh/100;b=(xlh-a*100)/10;c=xlh%10;trysleep(1);catch(InterruptedException e) e.printStackTrace();后果：输出结果错误分析：应声明表明JavaThread类继承Thread类为公共类正确代码importjava.lang.Thread;publicclassJavaThreadextendsThreadprivateintstart;privateintend;privateintsum=0;publicJavaThread(intstart,intend)super();this.start=start;this.end=end;publicvoidrun()/并行函数inta,b,c;for(intxlh=start;xlh=end;xlh+=2)a=xlh/100;b=(xlh-a*100)/10;c=xlh%10;trysleep(1);catch(InterruptedException e) e.printStackTrace();分析对编程掌握不熟悉。1.6 基于Windows（.NET）的并行算法实现1.6.1 代码及注释（变量名 名字首字母 开头） using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading;using System.Diagnostics;class Threads static void Main() Stopwatch t1 = new Stopwatch(); Work work1 = new Work(0); ThreadStart thread1 = new ThreadStart(work1.Work1);/调用work函数 Thread newthread1 = new Thread(thread1); Work work2 = new Work(1); ThreadStart thread2 = new ThreadStart(work2.Work1); Thread newthread2 = new Thread(thread2); Console.Write(并行结果:n); t1.Start();/并行开始 newthread1.Start(); newthread2.Start(); newthread1.XLHoin(); newthread2.XLHoin(); t1.Stop();/并行结束 TimeSpan timeSpan = t1.Elapsed; double pt = timeSpan.TotalMilliseconds; Console.Write(并行时间:0n, pt); Console.Write(串行结果:n); t1.Start();/串行开始 new Work(0).func(); t1.Stop();/串行结束 TimeSpan timeSpan2 = t1.Elapsed; double st = timeSpan2.TotalMilliseconds; Console.WriteLine(串行时间:0, st); Console.WriteLine(加速比:0, st / pt); Console.Read(); class Work private int start; public Work(int start) this.start = start; public void Work1()/并行函数求水仙花数 int m; for (int i = 1; i 10; i+) for (int xlh = 0; xlh 10; xlh+) for (int k = start; k 10; k += 2) if (i * i * i + xlh * xlh * xlh + k * k * k = 100 * i + 10 * xlh + k) m = i * i * i + xlh * xlh * xlh + k * k * k; Console.WriteLine(m); public void func()/串行函数 int m; for (int i = 1; i 10; i+) for (int xlh = 0; xlh 10; xlh+) for (int k = start; k 10; k+) if (i * i * i + xlh * xlh * xlh + k * k * k = 100 * i + 10 * xlh + k) m = i * i * i + xlh * xlh * xlh + k * k * k; Console.Wr