蒙特卡洛算法求 pi项目(2)

三、并行算法

3.1 并行算法描述

算法步骤：

1、确定需要产生的点的个数n，参与运行的处理器数m；

2、对每一个处理器，生成两个随机数x，y，范围[0，1]；

3、判断两个随机数x，y是否满足 ；

4、若满足，则变量COUNT_i++；

5、重复步骤2-4，直至每个处理器均生成n/m个随机点；

6、收集COUNT_i的值，并累加至变量COUNT中，此即为随机点落在圆弧内的数量；

7、通过（2）式计算 的值。

3.2 并行算法的一个例子

在这个实验中，采用Linux操作系统pthread接口来实现程序的并行化。这些接口函数和数据类型都在头文件中声明。因为pthread并没有包含在C的标准库中，编译的时候需要加上-­lpthread选项，使程序链接到libpthread，才能编译成功。

例子程序参见附件Parallel.c。

#include

#include

#include

#include

#include

#include

 

long cs=0; //总循环次数

long count=0; //主线程有效次数

long count_thread=0; //thread线程有效次数

struct timeval start, finish; //定义开始结束时间

double diffsec,diffusec;

//thread线程计算量为总数的一半

void thread(void)

{  

    int i=0;

    double x,y;

    for(i=0;i

    {      

        x=(long double)rand()/(long double)RAND_MAX;

        y=(long double)rand()/(long double)RAND_MAX;

        if((x*x+y*y)<=1)

            count_thread++;

    }

}

 

//主线程计算量为总数的一半

int main (void)

{

    printf("Please input the number:");

    scanf("%d",&cs);

    cs=cs*1000000;

    pthread_t id;

    int ret;

    srand( (unsigned)time( NULL ) );

    ret=pthread_create(&id,NULL,(void *) thread,NULL); //创建thread线程

    gettimeofday(&start,NULL); //记录开始时间   

    int i=0;

    double x,y;

    for(i=0;i

    {      

        x=(long double)rand()/(long double)RAND_MAX;

        y=(long double)rand()/(long double)RAND_MAX;   

        if((x*x+y*y)<=1)

            count++;

    }

    pthread_join(id,NULL); //两线程同步

    count+=count_thread;

    gettimeofday(&finish,NULL); //记录结束时间

    //计算时间差

    diffsec=(double)finish.tv_sec-start.tv_sec;

    diffusec=(double)(finish.tv_usec-start.tv_usec)/(double)1000000;

    diffsec+=diffusec;

    //输出结果

    printf("Cost time=%f second \n",diffsec); 

    printf("roop times=%d \n",cs);

    printf("effective times=%d \n",count);

    printf("pi= %f \n",4*(double)count/(double)cs);

    return(0);

}

 

 

3.3 并行算法正确性证明

本并行算法只是简单的把独立的任务进行分派，经多次试验测试，结果正确。

四、实验结果

硬件平台：惠普刀片集群

编译器：gcc&g++

操作系统：Linux

测试数据集合：由随机数函数产生的数据集合

 

4.1 算法运行时间

N（千万）	串行算法运行时间（秒）	并行算法运行时间（秒）	加速比
1	0.814	0.959	0.8488
2.5	1.618	2.673	0.6053
5	4.024	5.716	0.7039
7.5	6.069	7.376	0.8228
10	8.089	10.001	0.8088
12.5	10.105	12.227	0.8264
15	12.115	14.842	0.8162
17.5	14.119	19.522	0.7232
20	16.121	22.033	0.7316
30	24.183	32.592	0.7419
40	32.259	41.542	0.7765
50	40.726	49.725	0.8109

表1

[注]： N：算法生成随机点的个数

算法运行时间为某一次运行时间，非多次运行之平均时间

4.2 算法计算量时间比、加速比

并行、串行算法运算量时间比、加速比如下图所示图2图3

五、实验结果分析

       如表1、图3所示，加速比在（0.6,0.9）区间，与理论上的值2相去甚远。

对同一运算量多次运行并行算法得到如下表2所示结果。（图4）

 

规模	1	2	3	4	5	6	7
1	0.959	1.205	0.963	1.043	1.002	1.053	1.011
5	5.716	4.877	5.094	4.761	5.212	4.875	5.296
10	10.001	9.892	9.990	10.151	9.941	10.168	10.169
20	22.033	20.757	20.120	20.647	19.918	20.798	20.160
50	49.725	49.785	51.535	49.420	50.992	52.379	47.015

表2

图4

 

而对同样的运算量多次运行串行算法得到如下表3所示结果。（图5）

 

规模	1	2	3	4	5	6	7
1	0.814	0.814	0.814	0.813	0.810	0.815	0.813
5	4.024	4.053	4.062	4.057	4.044	4.090	4.053
10	8.089	8.152	8.153	8.134	8.160	8.095	8.108
20	16.121	16.289	16.290	16.318	16.288	16.245	16.292
50	40.726	40.721	40.701	40.696	40.706	40.695	40.694

表3

 

图5

 

如图4图5所示，对同一计算量，串行算法每次运行时间相差较小，而并行算法则相差明显。因此，通过分析源代码可得出以下结论：

       程序所用的rand（）函数在同一时间只允许一个处理器调用，当两个处理器都需调用rand（）函数时，后调用的将被挂起，等待另一个处理器运行完毕。两线程在就绪和执行态之间不断变化，浪费了大量CPU时间，因此对同一运算量，并行程序运行时间反而比串行程序慢，而且线程状态转换次数范围为[0，n]，平均为 次，因此，相比于串行程序的无状态转换，并行算法的运行时间才会有如此大的波动。