高性能计算导论课程设计

高性能课程设计一、问题描述用OpenMP完成查找MAX_VALU以内的所有“完全数”的程序，输出完数及其个数。并且将单线程串行计算与多线程并行计算进行比较，结合所选的硬件的平台对实验结果进行分析。二、算法描述1.概念：若一个数恰好等于其所有的真因子（即除了自身以外的约数）的和，则称该数为“完全数”。2.举例：前5个完全数分别为6、28、496、8128、33550336。6=1+2+3、28=1+2+3+4+5+6+73.算法设计：设计一个双重循环，外层循环次数为MAX_VALU，即对每一个小于MAX_VALU的数index进行验证。由于一个数index除了其本身外没有比index/2+1大的约数，所以内层循环次数设置为index/2+1，对于内层循环的每一个i值，若index能够被i整除，则说明i是index的因子。计算index的所有真因子的和s，若s与index相等，则index为“完全数”。该算法程序代码如下：for(index=1;index=MAX_VALUE;index++){//外层循环MAX_VALUE次ints=0;for(inti=1;iindex/2+1;i++){//内层循环index/2+1次if(index%i==0){//判断i是否是index的约数s=s+i;//计算index的因子的和}}if(s==index){//若和与该数相等，则index是“完全数”printf(“%d是完全数\n”,index);}}4.算法流程图开始设置外层循环次数为MAX_VALUE，变量intindex=1设置真因子的和变量ints=0设置内层循环次数为index/2+1，定义变量inti=1Index%i=0?s=s+iS=index？输出index是完数index=MAX_VALUEYiindex/2+1结束NYYNYindex=index+1Ni=i+1N三、程序流程图开始变量初始化获取串行计算的开始时间循环MAX_VALUE次，对每个数验证其是否是完全数，若是完全数则输出输出完全数的个数、时间、线程数、问题规模获取并行计算的开始时间程序将MAX_VALUE个循环次数分配给THREAD个线程并行执行，每个执行完之后进行传递汇总输出完全数的个数、时间、线程数、问题规模结束四、OpenMP代码#includestdafx.h#includestdio.h#includeomp.h#includetime.h#defineMAX_VALUE10000#defineTHREAD2intmain(){omp_set_num_threads(THREAD);intindex=0;doublestartTime=0.0;doubleendTime=0.0;//串行部分startTime=clock();//开始计时intcount1=0;for(index=1;index=MAX_VALUE;index++){//外层循环MAX_VALUE次ints=0;for(inti=1;iindex/2+1;i++){//内层循环index/2+1次if(index%i==0){//判断i是否是index的约数s=s+i;//计算index的因子的和}}if(s==index){//若和与该数相等，则是“完全数”，个数加1并输出count1++;printf(%d,index);}}endTime=clock();//串行计算结束printf(\n串行：THREAD=%d,MAX_VALUE=%d,count1=%d,time1=%.10f\n,1,MAX_VALUE,count1,(endTime-startTime)/CLOCKS_PER_SEC);//并行部分startTime=clock();//开始计时intcount2=0,id=0;#pragmaompparallelprivate(id,index)reduction(+:count2)//并行计算{id=omp_get_thread_num();//获取当前线程编号for(index=id+1;index=MAX_VALUE;index=index+THREAD){//循环分配ints=0;for(inti=1;iindex/2+1;i++){//内层循环index/2+1次if(index%i==0){//判断i是否是index的约数s=s+i;//计算index的因子的和}}if(s==index){//若和与该数相等，则是“完全数”，个数加1并输出count2++;printf(%d,index);}}}endTime=clock();//并行计算结束printf(\n并行：THREAD=%d,MAX_VALUE=%d,count2=%d,time1=%.10f\n,THREAD,MAX_VALUE,count2,(endTime-startTime)/CLOCKS_PER_SEC);return0;}五、并行化关键代码分析#pragmaompparallelprivate(id,index)reduction(+:count2)//并行计算{id=omp_get_thread_num();//获取当前线程编号for(index=id+1;index=MAX_VALUE;index=index+THREAD){//循环分配ints=0;for(inti=1;iindex/2+1;i++){//内层循环index/2+1次if(index%i==0){//判断i是否是index的约数s=s+i;//计算index的因子的和}}if(s==index){//若和与该数相等，则是“完全数”，个数加1并输出count2++;printf(%d,index);}}}分析：#pragmaompparallelprivate(id,index)reduction(+:count2)指令使程序在执行下面的代码时每个线程能够并行执行，并且reduction使得每个线程都要保存变量count2的拷贝，循环结束后，所有线程把自己的count2累加起来作为最后的count2.id=omp_get_thread_num()语句获取本线程的编号，使得在循环语句for(index=id+1;index=MAX_VALUE;index=index+THREAD)中能够为每个线程分配计算，将MAX_VALUE次循环分成MAX_VALUE/THREAD组，每一个线程负责每组中的一次循环计算，因此当THREAD个线程并行计算完一次即可完成THREAD次循环的计算，所以每个线程最多只需完成MAX_VALUE/THREAD次循环计算，即可完成全部的计算任务，大大减少了计算所用的时间。六、实验结果截屏与分析第一部分：计算规模为5000时，改变并行线程数，观察串行计算和并行计算所用时间此时可以看出并行计算比串行计算所用的时间稍微还多一点，这是因为此时计算规模太小，使用串行计算的速度已经很快了，而且使用并行计算还需要将循环进行分配，这个过程也需要一定的时间，所以当问题规模小的时候串行计算可能还更快一些。第二部分：计算规模为10000时，改变并行线程数，观察串行计算和并行计算所用时间此时可以看出并行计算比串行计算所花的时间少，速度更快。这是由于所用的计算机为多核的，能够同时支持多个线程，并且线程间共享内存，当增加线程数时，由于多个线程共同分配计算，所以计算速度更快。但是当线程数增加到3之后再增加线程数，计算时间并没有太多的变化。这是由于此时的计算规模还是偏小，当线程数为3时，计算速度已经很快了，当继续增加线程数时，计算速度已经没有明显的增大了。第三部分：计算规模为40000时，改变并行线程数，观察串行计算和并行计算所用时间此时可以看出并行计算比串行计算所花的时间少很多，当线程数由2增加到4时，所用的时间越来越少，并且当线程数为4时，计算速度最快，计算所用时间最少，当线程数继续增加时，计算所用的时间较最小时间稍微有所增加。这是由于实验所用的计算机的核数为4，每个核都能独立支撑一个线程，并且使用线程间共享内存的方式协调并行计算，所以当线程数为4时，有效地利用的CPU的资源，计算的速度最快。当线程数继续增加时，由于这个时候线程数大于计算机的核数，所以线程轮流使用CPU的资源，并且操作系统需要对这些线程进行管理，有管理就会有开销，所以此时所用的时间比4线程所用的时间会稍微增加一些。七、实验总结本实验中采用OpenMP并行计算，完成查找MAX_VALU以内的所有“完全数”的程序。并且将单线程串行计算所用的时间与多线程并行计算所用的时间进行比较，结合所选的硬件的平台对实验结果进行分析。得出多线程的并行计算较单线程串行计算所用的时间少，计算速度快的结论。由于所用的计算机为多核计算机，每个核都能独立支撑一个线程，并且OpenMP使用线程间共享内存的方式协调并行计算，所以当计算规模较大时，设置合理的线程数目，使计算机进行并行计算，能够提高计算的速率，更加充分合理的使用CPU的资源。但是线程数也不宜设置得过大，因为当线程数大于核数时，线程间是轮流使用CPU资源的，所以计算速度不会随着线程数的增大而无限增大，而且当线程数太多的时候，还需要对这些线程进行管理，有管理就会有开销，需要消耗一定的时间。