并行计算课程报告 (1)

并行计算与多核多线程技术课程报告班级： 计 125 学号：201258501144姓名： 李燕飞2014 年 11 月 19 日班级：计 125_ 学号:201258501144 姓名:李燕飞 约数和素数 评 价实践效果（正确度/加速比）理论基础难度工作量独立性认证结果班级：计 125_ 学号:201258501144 姓名:李燕飞 约数和素数 目录1. 约数和素数 并行算法设计与实现 .11.1 功能描述与解决方案 .11.1.1 功能描述 .11.1.2 解决方案 .11.2 算法设计 .11.2.1 串行算法设计 .11.2.2 并行算法设计 .21.2.3 理论加速比分析 .31.3 基于 OPENMP 的并行算法实现 .31.3.1 代码及注释 .31.3.2 执行结果截图 .61.3.3 遇到的问题及解决方案 .61.3.4 加速比分析 .71.4 基于 MPI 的并行算法实现 .81.4.1 代码及注释 .81.4.2 执行结果截图（体现串行时间、并行时间和加速比） .101.4.4 加速比分析 .121.5 基于 JAVA（TREAD）的并行算法实现 .121.5.1 代码及注释 .121.5.2 执行结果截图 .161.5.3 遇到的问题及解决方案 .171.5.4 加速比分析 .171.6 基于 JAVA（RUNNABLE）的并行算法实现 .181.6.1 代码及注释 .181.6.2 执行结果截图 .211.6.3 遇到的问题及解决方案 .221.6.4 加速比分析 .231.7 基于 WINDOWS API 的并行算法实现 .231.7.1 代码及注释 .231.7.2 执行结果截图 .271.7.4 加速比分析 .281.8 基于 WINDOWS MFC 的并行算法实现 .281.8.1 代码及注释 .281.8.2 执行结果截图 .331.8.3 遇到的问题及解决方案 .341.8.4 加速比分析 .351.9 基于 WINDOWS .NET 的并行算法实现 .351.9.1 代码及注释 .351.6.2 执行结果截图 .381.9.3 遇到的问题及解决方案 .391.9.4 加速比分析 .40班级：计 125_ 学号:201258501144 姓名:李燕飞 约数和素数 2. 理论基础 .412.1 并行计算机体系结构、并行计算模型、并行算法的概念 .412.2 并行计算机体系结构、并行计算模型、并行算法的关系 .412.3 实例说明并行计算机体系结构、并行计算模型、并行算法的关系 .423. 数据存储与处理技术 .43班级：计 125_ 学号:201258501144 姓名: 李燕飞 约数和素数 11. 约数和素数 并行算法设计与实现1.1 功能描述与解决方案1.1.1 功能描述给出一个正整数num ，求这个正整数 num的约数个数，约数的和，以及在2-num之间的素数个数。1.1.2 解决方案利用两个for 循环，外循环计算约数的个数以及约数的和（如果在num以内的正整数能整除num ，那么约数个数加 1，并且和累加。否则，不加入计算。）内循环统计素数的个数（num除以从2到它的平方根的每一个整数，若有一项余数为0则其不是素数，若均不为0，则是素数。则素数个数加 1）。1.2 算法设计1.2.1 串行算法设计输入：上限数num输出：约数个数j1，约数和sum，素数个数countBeginfor long lyf_i=2 to lyf_num do/求正整数的约数if lyf_num%lyf_i=0 thenlyf_sum=lyf_sum+lyf_i;lyf_j1+;班级：计 125_ 学号:201258501144 姓名: 李燕飞 约数和素数 2end if/求正整数的素数个数long lyf_k=sqrt(double)lyf_i);flag=true;for long lyf_j to lyf_k do/判断是不是素数if lyf_i%lyf_j=0 thenflag=false;break;end ifif flag thenlyf_count+;end ifend for end forEnd1.2.2 并行算法设计(1)for long lyf_i=2 to lyf_num/2 do/求正整数的约数if lyf_num%lyf_i=0 thenlyf_sumto=lyf_sumto+lyf_i;lyf_j1to+;end if/求正整数的素数个数long lyf_k=sqrt(double)lyf_i);flag=true;for long lyf_j to lyf_k do/判断是不是素数if lyf_i%lyf_j=0 thenflag=false;break;end ifif flag thenlyf_countto+;end ifend for end for班级：计 125_ 学号:201258501144 姓名: 李燕飞 约数和素数 3End（2）for long lyf_i=1+num/2 to lyf_num do/求正整数的约数if lyf_num%lyf_i=0 thenlyf_sumto=lyf_sumto+lyf_i;lyf_j1to+;end if/求正整数的素数个数long lyf_k=sqrt(double)lyf_i);flag=true;for long lyf_j to lyf_k do/判断是不是素数if lyf_i%lyf_j=0 thenflag=false;break;end ifif flag thenlyf_countto+;end ifend for end forEnd1.2.3 理论加速比分析随着输入数据的增大，加速比也会随着逐渐增大到最大，然后会随着输入数据的增大再逐渐减小。1.3 基于 OpenMP 的并行算法实现1.3.1 代码及注释/ Prime1.cpp : 定义控制台应用程序的入口点。/#include “stdafx.h“班级：计 125_ 学号:201258501144 姓名: 李燕飞 约数和素数 4#include#include#include“omp.h“using namespace std;#include#define NUM_THREADS 2int _tmain(int argc, _TCHAR* argv)omp_set_num_threads(NUM_THREADS);long long lyf_count=0;long lyf_num,lyf_sum=0,lyf_j1=0; printf(“请输入一个正整数：“);scanf(“%d“,clock_t lyf_t1=clock();#pragma omp parallel reduction(+:lyf_count) bool flag;#pragma omp forfor(long lyf_i=2;lyf_i=lyf_num;lyf_i=lyf_i+1) if(lyf_num%lyf_i=0)lyf_sum+=lyf_i;lyf_j1+;long lyf_k=sqrt(long )lyf_num);flag=true;for(long lyf_j=2;lyf_j=lyf_k;lyf_j+)if(lyf_i%lyf_j=0)flag=false;break; if(flag)lyf_count+;clock_t lyf_t2=clock();班级：计 125_ 学号:201258501144 姓名: 李燕飞 约数和素数 5printf(“这个正整数的所有约数之和为：“);printf(“lyf_sum=%dn“,lyf_sum+1);printf(“这个正整数的所有约数有：%d个n“,lyf_j1+1);printf(“在num范围内的素数个数是：“);printf(“lyf_count=%lldn“,lyf_count);printf(“parallel time=%dn“,(lyf_t2-lyf_t1);cout“*“endl;clock_t lyf_t3 =clock();lyf_count=0;bool flag;lyf_sum=0;lyf_j1=0;for(long lyf_i=2;lyf_i=lyf_num;+lyf_i) if(lyf_num%lyf_i=0)lyf_sum+=lyf_i;lyf_j1+;long lyf_k=sqrt(double)lyf_num);flag=true;for(long lyf_j=2;lyf_j=lyf_k;+lyf_j)if(lyf_i%lyf_j=0)flag=false;break;if(flag)lyf_count+; clock_t lyf_t4=clock();printf(“这个正整数的所有约数之和为：“);printf(“lyf_sum=%dn“,lyf_sum+1);printf(“这个正整数的所有约数有：%d个n“,lyf_j1+1);printf(“在num范围内的素数个数是：“);printf(“lyf_count=%lldn“,lyf_count);printf(“serial time=%dn“,(lyf_t4-lyf_t3);long lyf_x1,lyf_x2;lyf_x1=lyf_t2-l