高性能计算导论课程设计

1、高性能课程设计一、 问题描述用OpenMP完成查找MAX_VALU以内的所有“完全数”的程序，输出完数及其个数。并且将单线程串行计算与多线程并行计算进行比较，结合所选的硬件的平台对实验结果进行分析。二、 算法描述1. 概念：若一个数恰好等于其所有的真因子（即除了自身以外的约数）的和，则称该数为“完全数”。2. 举例：前5个完全数分别为6、28、496、8128、。6 = 1+2+3、28 =1+2+3+4+5+6+73. 算法设计：设计一个双重循环，外层循环次数为MAX_VALU，即对每一个小于MAX_VALU的数index进行验证。由于一个数index除了其本身外没有比index/2+1大的

2、约数，所以内层循环次数设置为index/2+1，对于内层循环的每一个i值，若index能够被i整除，则说明i是index的因子。计算index的所有真因子的和s，若s与index相等，则index为“完全数”。该算法程序代码如下：for(index=1;index=MAX_VALUE;index+) /外层循环MAX_VALUE次int s=0;for(int i=1;i index/2+1;i+) /内层循环 index/2+1次if(index % i=0) /判断i是否是index的约数s = s + i; /计算index的因子的和if(s = index) /若和与该数相等，则ind

3、ex是“完全数”printf(“%d是完全数n”,index);4. 算法流程图三、 程序流程图四、 OpenMP代码#include stdafx.h#include #include #include time.h#define MAX_VALUE 10000#define THREAD 2int main() omp_set_num_threads(THREAD ); int index= 0; double startTime = 0.0; double endTime = 0.0; /串行部分 startTime = clock(); /开始计时 int count1 = 0;for

4、(index=1;index=MAX_VALUE;index+) /外层循环MAX_VALUE次 int s=0;for(int i=1;i index/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 =

5、%d ,time1 = %.10fn, 1 ,MAX_VALUE ,count1,(endTime - startTime)/CLOCKS_PER_SEC); /并行部分 startTime = clock(); /开始计时int count2 = 0,id=0; #pragma omp parallel private(id,index)reduction(+:count2) /并行计算 id = omp_get_thread_num(); /获取当前线程编号 for(index=id+1; index = MAX_VALUE; index=index+THREAD) / 循环分配 int

6、s=0; for(int i=1;i index/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 = %.10fn, THREAD ,MAX_VALUE ,count2,(e

7、ndTime - startTime)/CLOCKS_PER_SEC); return 0;五、 并行化关键代码分析#pragma omp parallel private(id,index)reduction(+:count2) /并行计算 id = omp_get_thread_num(); /获取当前线程编号 for(index=id+1; index = MAX_VALUE; index=index+THREAD) / 循环分配 int s=0; for(int i=1;i index/2+1;i+) /内层循环 index/2+1次 if(index % i=0) /判断i是否是in

8、dex的约数 s = s + i; /计算index的因子的和 if(s = index) /若和与该数相等，则是“完全数”，个数加1并输出 count2+; printf(%d ,index); 分析：#pragma omp parallel private(id,index)reduction(+:count2)指令使程序在执行下面的代码时每个线程能够并行执行，并且reduction使得每个线程都要保存变量count2的拷贝，循环结束后，所有线程把自己的count2累加起来作为最后的count2.id = omp_get_thread_num()语句获取本线程的编号，使得在循环语句for(

9、index=id+1; index = MAX_VALUE; index=index+THREAD)中能够为每个线程分配计算，将MAX_VALUE次循环分成MAX_VALUE/ THREAD组，每一个线程负责每组中的一次循环计算，因此当THREAD个线程并行计算完一次即可完成THREAD次循环的计算，所以每个线程最多只需完成MAX_VALUE/ THREAD次循环计算，即可完成全部的计算任务，大大减少了计算所用的时间。六、 实验结果截屏与分析第一部分：计算规模为5000时，改变并行线程数，观察串行计算和并行计算所用时间此时可以看出并行计算比串行计算所用的时间稍微还多一点，这是因为此时计算规模太

10、小，使用串行计算的速度已经很快了，而且使用并行计算还需要将循环进行分配，这个过程也需要一定的时间，所以当问题规模小的时候串行计算可能还更快一些。第二部分：计算规模为10000时，改变并行线程数，观察串行计算和并行计算所用时间此时可以看出并行计算比串行计算所花的时间少，速度更快。这是由于所用的计算机为多核的，能够同时支持多个线程，并且线程间共享内存，当增加线程数时，由于多个线程共同分配计算，所以计算速度更快。但是当线程数增加到3之后再增加线程数，计算时间并没有太多的变化。这是由于此时的计算规模还是偏小，当线程数为3时，计算速度已经很快了，当继续增加线程数时，计算速度已经没有明显的增大了。第三部分

11、：计算规模为40000时，改变并行线程数，观察串行计算和并行计算所用时间此时可以看出并行计算比串行计算所花的时间少很多，当线程数由2增加到4时，所用的时间越来越少，并且当线程数为4时，计算速度最快，计算所用时间最少，当线程数继续增加时，计算所用的时间较最小时间稍微有所增加。这是由于实验所用的计算机的核数为4，每个核都能独立支撑一个线程，并且使用线程间共享内存的方式协调并行计算，所以当线程数为4时，有效地利用的CPU的资源，计算的速度最快。当线程数继续增加时，由于这个时候线程数大于计算机的核数，所以线程轮流使用CPU的资源，并且操作系统需要对这些线程进行管理，有管理就会有开销，所以此时所用的时间比4线程所用的时间会稍微增加一些。七、 实验总结本实验中采用OpenMP并行计算，完成查找MAX_VALU以内的所有“完全数”的程序。并且将单线程串行计算所用的时间与多线程并行计算所用的时间进行比较，结合所选的硬件的平台对实验结果进行分析。得出多线程的并行计算较单线程串行计算所用的时间少，计算速度快的结论。由于所用的计算机为多核计算机，每个核都能独立支撑一个线程，并且OpenMP使