并行计算课程报告庄星.doc

并行计算与多核多线程技术

课程报告

班级 计 1 2 1 - 2

学号 2 0 1 2 5 8 5 0 1 2 1 3

姓名 庄 星

2014 年 11 月 24 日

班级计 121-2 学号201258501213 姓名 庄星 蒙特卡洛球体体积
目录

1. 快速排序 并行算法设计与实现 4
1.1 功能描述与解决方案 4
1.1.1功能描述 4
1.1.2 解决方案 4
1.2算法设计 4
1.2.1 串行算法设计 4
1.2.2 并行算法设计 4
1.2.3 理论加速比分析（选作） 5
1.3 基于OpenMP的并行算法实现 5
1.3.1代码及注释（变量名 名字首字母 开头） 5
1.3.2 执行结果截图（体现串行时间、并行时间和加速比） 7
1.3.3 遇到的问题及解决方案 7
1.3.4 加速比分析（选作） 8
1.4 基于MPI的并行算法实现 8
1.4.1 代码及注释 8
1.4.2 执行结果截图（体现串行时间、并行时间和加速比） 10
1.4.3 遇到的问题及解决方案 11
1.4.4 加速比分析（选作） 11
1.5 基于Windows（API）的并行算法实现 12
1.5.1 代码及注释 12
1.5.2 执行结果截图（体现串行时间、并行时间和加速比） 15
1.5.3 遇到的问题及解决方案 15
1.5.4 加速比分析（选作） 16
1.6 基于Windows（MFC）的并行算法实现 16
1.6.1 代码及注释 16
1.6.2 执行结果截图（体现串行时间、并行时间和加速比） 18
1.6.3 加速比分析（选作） 19
1.7 基于Windows (.net)的并行算法实现（选作） 19
1.7.1 代码及注释 19
1.7.2 执行结果截图（体现串行时间、并行时间和加速比） 21
1.7.3 遇到的问题及解决方案 22
1.7.4 加速比分析（选作） 22
2. 理论基础 22
2.1 并行计算机体系结构、并行计算模型、并行算法的概念 22
2.2并行计算机体系结构、并行计算模型、并行算法的关系 23
2.3实例说明并行计算机体系结构、并行计算模型、并行算法的关系 23

评 价

实践效果（正确度/加速比）

理论基础

难度

工作量

独立性

班级计 121-2 学号201258501213 姓名 庄 星 蒙特卡洛球体体积
1. 快速排序 并行算法设计与实现
1.1 功能描述与解决方案
1.1.1功能描述
本算法是利用蒙特卡洛计算的方法求一个单位为一的球体的体积，计算机根据算法描述在三维坐标轴上随机取数，再根据上述输入，利用给定的球体体积的运算法则，快速实施充分大量的随机抽样，对随机抽样的数据进行必要的数学计算，求出结果。
1.1.2 解决方案
在此算法中我需要随机取得的大量的数据进行随机计算，具体实施方案如下：
（1）首先，使用FOR循环在1~10000000之间取数，分别取X,Y,Z三个方向轴上的值，对所取值分别除以32767即可得到属于0~1的区间内的XYZ的值；
（2）对所求的xyz做平方和运算，若所得值小于1，这个值有效，此时定义另一个变量count，对判断有效的过程执行count+1，在大量随机取数中这个值有效，将这个值保存。
（3）利用蒙塔卡罗算法，对有效值进行数据运算，因为大数据取数，所以所求值一定接进于单位为1的球体的体积。
（4）并行算法中需要对循环次数做并行化，分别在Openmp，MPI，API ，MFC以及C#中使用不同的并行方法对循环函数做变化，在不同的并行方法中，还需要对随机取数的方法做不同的使用。
1.2算法设计
1.2.1 串行算法设计
根据上述所列的具体实现方案设计串行计算方法。
1.2.2 并行算法设计
在1.2.1的基础上，将循环体分成两个等长的循环，分别计算COUNT值，最后调用归并算法，将以计算好的COUNT带入球体积分计算公式，求出单位球的体积。
1.2.3 理论加速比分析（选作）
因为我所用的为Inter双核处理器，理论上对同一个函数进行双核运行是单核速度的两倍，并且由于并行算法是将串行分成两个部分分别运行，理论加速比应该为2，但是由于并行的调用时间还有归并调用的操作，所以加速比应当小于2，且由于机器和随机取数的效率问题，加速比应在1和2之间。
1.3 基于OpenMP的并行算法实现
1.3.1代码及注释（变量名 名字首字母 开头）

// zx_para.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<stdlib.h>
#include<time.h>
#include <stdio.h>
#include<windows.h>
#include<omp.h>

void serial()//串行程序
{
long int zx_max=10000000;
long int zx_i1,zx_count1=0;
double zx_x1,zx_y1,zx_z1,zx_bulk;//start_time1,end_time1;

//start_time1=clock();
time_t zx_t1;

srand((unsigned) time(&zx_t1));//函数产生一个以当前时间开始的随机种子

for(zx_i1=0;zx_i1<zx_max;zx_i1++)
{
zx_x1=rand();//从~MAX中任取一个数进行随机计算

zx_x1=zx_x1/32767;

zx_y1=rand();
zx_y1=zx_y1/32767;

zx_z1=rand();
zx_z1=zx_z1/32767;

if((zx_x1*zx_x1+zx_y1*zx_y1+zx_z1*zx_z1)<=1)//球体的体积
zx_count1++;
}

zx_bulk=8*((double)(zx_count1)/zx_max);
//end_time1=clock();

printf("球体的体积为%0.6f\n",zx_bulk);
//printf("串行运算时间为%0.3f ms\n",(end_time1-start_time1));

}

int _tmain(int argc, _TCHAR* argv[])
{

long long zx_max=10000000;

long long zx_i,zx_count=0;

double zx_x,zx_y,zx_z,zx_bulk,start_time2,end_time2;
double start_time1,end_time1;//串行时间

start_time2=clock();
time_t zx_t2;

//srand((unsigned) time(&zx_t2));//函数产生一个以当前时间开始的随机种子

#pragma omp parallel for private(zx_x,zx_y,zx_z) reduction(+:zx_count) //reduction字句并行求圆的体积，同数值积分

for(zx_i=0;zx_i<zx_max;zx_i++) //计算半径为1 单元的球体体积
{
zx_x=rand();//生成~1000000之间的一个随机数
zx_x=zx_x/32767;//将生成的数转化为0-1之间

zx_y=rand();
zx_y=zx_y/32767;

zx_z=rand();
zx_z=zx_z/32767;

if((zx_x*zx_x+zx_y*zx_y+zx_z*zx_z)<=1)
zx_count++;
}
zx_bulk=8*((double)(zx_count)/zx_max);
end_time2=clock();

printf("球体的体积为%0.6f\n",zx_bulk);
printf("并行运算时间为%0.3f ms\n",(end_time2-start_time2));

start_time1=clock();
serial();//串行程序的计算
end_time1=clock();
printf("串行运算时间为%0.3f ms\n",(end_time1-start_time1));
printf("并行加速比为%0.3f \n",((end_time1-start_time1)/(end_time2-start_time2))); system("pause");
return 0;
}
1.3.2 执行结果截图（体现串行时间、并行时间和加速比）

1.3.3 遇到的问题及解决方案
（1）问题一：串行程序在主函数中直接编写，导致变量名混乱，时间函数无法求得，无法计算加速比。
解决方案：对串行程序单独设计serial函数，在主函数中直接调用。
1.3.4 加速比分析（选作）
并行算法将串行分成两个部分分别运行，理论加速比应该为2，但是由于并行还有归并的操作，所以加速比应在1和2之间。
1.4 基于MPI的并行算法实现
1.4.1 代码及注释
#include "stdafx.h"
#include<stdlib.h>
#include<time.h>
#include<stdio.h>
#include"mpi.h"
#include <stdio.h>
#include <iostream>
using namespace std;

long long int MC(long long int mynumber,int myrank)
{
int mycount=0;
double x,y,z;
int i=0;
for(i;i<mynumber;i++)
{
x==((double)rand()/RAND_MAX);
y==((double)rand()/RAND_MAX);
z==((double)rand()/RAND_MAX);
if(x*x+y*y+z*z<1.0)
mycount++;
}
return mycount;
}

void serial() //串行程序
{
int Allnumber=10000000;
int count=0;
double x,y,z,bulk;
double stime,etime,atime;
stime=clock();
for(int i=0;i<Allnumber;i++)
{
x=（(double)rand()/RAND_MAX);//随机取数
y=（(double)rand()/RAND_MAX);
z=（(double)rand()/RAND_MAX)；
if(x*x+y*y+z*z<1.0)
{count++;}
}
bulk=8.0*count/Allnumber;
etime=clock();
atime=(etime-stime)/1000;
cout<<"bulk="<<bulk<<endl;
cout<<"serial time="<<atime<<endl;
//printf("pi= %12.12f ,alltime=%.3f ",pi,atime);
}

int main(int argc,char* argv[])
{
int myrank,size;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&size);
MPI_Comm_rank(MPI_COMM_WORLD,&myrank);

long long int topinnumber,myinnumber,mynumber,allnumber;
double bulk,stime,etime,atime;
stime=MPI_Wtime();
allnumber=10000000;
mynumber=allnumber/size;
if(myrank!=0)
{
myinnumber=MC(mynumber,myrank);
MPI_Send(&myinnumber,1,MPI_LONG_LONG,0,0,MPI_COMM_WORLD);
cout<<myrank<<" of "<<size<<" : "<<myinnumber<<endl;
//printf("%d of %d : %d\n",myrank,size,myinnumber);
}
else
{
myinnumber=MC(mynumber,myrank);
//cout<<myrank<<" of "<<size<<" : "<<myinnumber<<endl;
topinnumber=myinnumber;
for(int source=1;source<size;source++)
{
MPI_Recv(&myinnumber,1,MPI_LONG_LONG,source,0,MPI_COMM_WORLD,MPI_STATUS_IGNORE);
topinnumber+=myinnumber;
}
bulk=8.0*topinnumber/allnumber;
}
etime=MPI_Wtime();
atime=etime-stime;
if(myrank==0)
cout<<"bulk="<<bulk<<endl;
cout<<"parallel time="<<atime<<endl;
MPI_Finalize();
serial();
system("pause");
return 0;
}
1.4.2 执行结果截图（体现串行时间、并行时间和加速比）
单倍运行双核运行
1.4.3 遇到的问题及解决方案
（1）问题一：函数运行中随机取数方法无法运行，
代码及后果
x=rand();运行出现错误，无法运行。
正确代码
x=（(double)rand()/RAND_MAX);
分析
在xyz的定义中，我的定义是double类型，rand（）取数时所得数为int类型，需要对所取值进行强制类型转换。
（2）问题二：#include "stdafx.h"未定义在mpi.h之前，程序错误
错误代码及后果
#include “mpi.h”
#include "stdafx.h"
正确代码
将mpi.h与stdafx.h进行位置交换。
分析
当头文件调用时，程序执行完mpi.h以后不执行stdafx.h。
1.4.4 加速比分析（选作）
当随机取数少时，运行速度极快，但是因为取值太少，计算结果出现不确定性。
MPI调用双核计算，理论速度是单核的两倍。实际速度达不到两倍，也应当在1~2之间，数据较大时接近于2，数据较小时，接近于1。并且应当数据量达到一定值后基本保持恒定。
1.5 基于Windows（API）的并行算法实现
1.5.1 代码及注释
(1)API
// zx_api.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<Windows.h>
#include<omp.h>
#include<math.h>
#include<time.h>
#include<iostream>
using namespace std;

HANDLE finish[2];
double zx_parall[2]={0.0,0.0};
static long zx_max=10000000;

void serial()//串行程序
{
long double zx_count=0;
long double zx_squar;
for(int i=1;i<=zx_max;i++){
double x,y,z;
x=rand();
x=x/32767;
y=rand();
y=y/32767;
z=rand();
z=z/32767;
if(x*x+y*y+z*z<=1)//单位体积为
{zx_count++;}
}
zx_squar=8*(zx_count/zx_max);
printf("球体的体积为%0.6f\n",zx_squar);

}

DWORD WINAPI ThreadOne(LPVOID param){//线程一
//double t=0;
long double zx_count=0;
for(int i=0;i<=(zx_max/2);i++){
double x,y,z;
x=rand();
x=x/32767;
y=rand();
y=y/32767;
z=rand();
z=z/32767;
if(x*x+y*y+z*z<=1)
{zx_count++;}
}
zx_parall[0]=zx_count;
SetEvent(finish[0]);
return 0;
}
DWORD WINAPI ThreadTwo(LPVOID param){//线程二
//double t=0;
long double zx_count=0;
for(int i=(zx_max/2)+1;i<=zx_max;i++){
double x,y,z;
x=rand();
x=x/32767;
y=rand();
y=y/32767;
z=rand();
z=z/32767;
if(x*x+y*y+z*z<=1){zx_count++;}
}
zx_parall[1]=zx_count;
SetEvent(finish[1]);
return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
double zx_tmp=0,zx_squar;
clock_t start,end;
clock_t start1,end1;
//int t1,t2;

start=clock();
finish[0]=CreateEvent(NULL,false,false,NULL);
finish[1]=CreateEvent(NULL,false,false,NULL);
HANDLE thread1=CreateThread(NULL,0,ThreadOne,NULL,0,NULL);
HANDLE thread2=CreateThread(NULL,0,ThreadTwo,NULL,0,NULL);
WaitForMultipleObjects(2,finish,true,INFINITE);
for(int i=0;i<3;i++){//线程分支相加
zx_tmp+=zx_parall[i];
}
zx_squar=8*(zx_tmp/zx_max);//计算体积
end=clock();
//t1=end-start;
printf("球体的体积为%0.6f\n",zx_squar);
printf("并行时间计算=%d\n",end-start);
start1=clock();
serial();
end1=clock();
//t2=end1-start1;
printf("串行运算时间为=%d\n",(end1-start1));

system("pause");
return 0;
}

1.5.2 执行结果截图（体现串行时间、并行时间和加速比）

1.5.3 遇到的问题及解决方案
（1）问题一：线程名定义重复
错误代码及后果
HANDLE thread1=CreateThread(NULL,0,ThreadOne,NULL,0,NULL);
HANDLE thread2=CreateThread(NULL,0,ThreadOne,NULL,0,NULL);
正确代码
HANDLE thread1=CreateThread(NULL,0,ThreadOne,NULL,0,NULL);
HANDLE thread2=CreateThread(NULL,0,ThreadTwo,NULL,0,NULL);
分析
CreateThread（）中调用的是不同的线程，若使用同一个线程，程序不执行

（1）问题二：函数名定义错误
错误代码及后果
Wait (2,finish,true,INFINITE);
正确代码
WaitForMultipleObjects(2,finish,true,INFINITE);
分析
此函数为API中的线程调用的固定函数，不能改函数体名称。
1.5.4 加速比分析（选作）
函数使用了双线程运行，理论加速比是单线程的两倍，实际加速比应当在1~2之间，接近于2.

1.6 基于Windows（MFC）的并行算法实现
1.6.1 代码及注释
//ZX_MFC.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<afxmt.h>
#include<iostream>
#include<afxwin.h>
#include<time.h>

CEvent faxEvent1(false);
CEvent faxEvent2(false);
double zx_parall[2]={0.0,0.0};
static long zx_max=100000000;
void serall(){
double zx_squar;
long double zx_count=0;
for(int i=0;i<=zx_max;i++){
double x,y,z;
x=rand();
x=x/32767;
y=rand();
y=y/32767;
z=rand();
z=z/32767;
if(x*x+y*y+z*z<=1)
{zx_count++;}
}
zx_squar=8*(zx_count/zx_max);
printf("squar=%.8f\n",zx_squar);
}

UINT ThreadOne(LPVOID param){
//double t=0;
long double zx_count=0;
for(int i=0;i<=(zx_max/2);i++){
double x,y,z;
x=rand();
x=x/32767;
y=rand();
y=y/32767;
z=rand();
z=z/32767;
if(x*x+y*y+z*z<=1)
{zx_count++;}
}
zx_parall[0]=zx_count;
SetEvent(faxEvent1);
return 0;
}
UINT ThreadTwo(LPVOID param){
//double t=0;
long double zx_count=0;
for(int i=(zx_max/2)+1;i<=zx_max;i++){
double x,y,z;
x=rand();
x=x/32767;
y=rand();
y=y/32767;
z=rand();
z=z/32767;
if(x*x+y*y+z*z<=1){zx_count++;}
}
zx_parall[1]=zx_count;
SetEvent(faxEvent2);
return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
double zx_tmp=0,zx_squar;
clock_t zx_start,zx_end;
clock_t zx_start1,zx_end1;

zx_start=clock();
AfxBeginThread(ThreadOne,NULL);
AfxBeginThread(ThreadTwo,NULL);
WaitForSingleObject(faxEvent1,INFINITE);
WaitForSingleObject(faxEvent2,INFINITE);

for(int i=0;i<3;i++){
zx_tmp+=zx_parall[i];
}
zx_squar=8*(zx_tmp/zx_max);
zx_end=clock();
printf("球体体积=%.8f\n",zx_squar);
printf("并行时间=%d\n",zx_end-zx_start);

zx_start1=clock();
serall();
zx_end1=clock();
printf("串行时间=%d\n",zx_end1-zx_start1);

system("pause");
return 0;
}
1.6.2 执行结果截图（体现串行时间、并行时间和加速比）

1.6.3 加速比分析（选作）
MFC的使用方法近似于API，理论加速比应当和API一致，同样是双线程计算，加速比在1—2之间，接近于2.

1.7 基于Windows (.net)的并行算法实现（选作）
1.7.1 代码及注释
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;
class zx_NET
{
static void Main()
{
double zx_bulk;
Stopwatch stopwatch = new Stopwatch();
Work work1 = new Work(1);
ThreadStart thread1 = new ThreadStart(work1.pSumto);
Thread newthread1 = new Thread(thread1);
Work work2 = new Work(2);
ThreadStart thread2 = new ThreadStart(work2.pSumto);
Thread newthread2 = new Thread(thread2);

stopwatch.Start();
newthread1.Start();
newthread2.Start();

newthread1.Join();
newthread2.Join();
stopwatch.Stop();

TimeSpan timeSpan = stopwatch.Elapsed;
zx_bulk = work1.getSum() + work2.getSum();
double millseconds = timeSpan.TotalMilliseconds;
Console.WriteLine("bulk={0}", zx_bulk);
Console.Write("parallel time=");
Console.WriteLine(millseconds);

stopwatch.Start();
zx_bulk = work1.sumto();
stopwatch.Stop();
timeSpan = stopwatch.Elapsed;
millseconds = timeSpan.TotalMilliseconds;
Console.WriteLine("bulk={0}", zx_bulk);
Console.Write("serial time=");
Console.Write(millseconds);
Console.Read();

}
}

class Work
{
private long start;
private double[] zx_sum = new double[2];
private static long zx_max = 10000000;
public Work(long i)
{
this.start = i;
}

public void pSumto()
{
double zx_count = 0;
for (long i = start; i <= zx_max; i = i + 2)
{
int x, y, z;
Random random = new Random();
x = random.Next();
x = x / 32767;
y = random.Next();
y = y / 32767;
z = random.Next();
z = z / 32767;
if ((x * x + y * y + z * z) <= 1)
zx_count++;
}
zx_sum[0] = zx_count;
}
public double sumto()
{
double zx_sumto = 0;
double zx_count = 0;
for (long i = start; i <= zx_max; i++)
{
int x, y, z;
Random random = new Random();
x = random.Next();
x = x / 32767;
y = random.Next();
y = y / 32767;
z = random.Next();
z = z / 32767;
if ((x * x + y * y + z * z) <= 1)
zx_count++;
}
zx_sumto = 8 * (zx_count / zx_max);
return zx_sumto;

}
public double getSum()
{
double zx_bulk;
zx_bulk = 8 * ((zx_sum[0] + zx_sum[1]) / zx_max);
return (zx_bulk);
}
}
1.7.2 执行结果截图（体现串行时间、并行时间和加速比）

1.7.3 遇到的问题及解决方案
（1）问题一:无法调用rand（）方法
错误代码及后果
X=rand（）；
程序提示rand()未定义。
正确代码
Random random = new Random();
x = random.Next();
分析
在c#中随机调用方法与c++中不同，有固定的调用方法。
1.7.4 加速比分析（选作）
C#并行方法中，函数将循环体分为两部分，加速比应当为两倍，实际运行中考虑计算机调用函数的时间和随机取数的时间，应小于2，接近于2.
2. 理论基础
2.1 并行计算机体系结构、并行计算模型、并行算法的概念

1.计算机体系结构：简单地讲，并行计算机就是由多个处理单元(CPU)组成的计算机系统，这些处理单元相互通信和协作能快速、高效的求解大型复杂问题
（1）结点，每个结点由多个处理器构成，可以直接输入/输出;
（2）互联网路，所有结点通过互联网络相互连接相互通信；
（3）内存，由多个储存模块组成；这些模块可以与结点对称地分布在互联网的两侧，也可以位于各个节点的内部。
（4）空间上的并行导致了两类并行机的产生，按照Flynn的说法分为：单指令流多数据流（SIMD）和多指令流多数据流（MIMD）。我们常用的串行机也叫做单指令流单数据流（SISD）。MIMD类的机器又可分为以下常见的五类：并行向量处理机（PVP）、对称多处理机（SMP）、大规模并行处理机（MPP）、工作站机群（COW）、分布