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

xuyuanchao

三、并行算法
3.1 并行算法描述
算法步骤：
1、确定需要产生的点的个数n，参与运行的处理器数m；
2、对每一个处理器，生成两个随机数x，y，范围[0，1]；
3、判断两个随机数x，y是否满足 ；
4、若满足，则变量COUNTi++；
5、重复步骤2-4，直至每个处理器均生成n/m个随机点；
6、收集COUNTi的值，并累加至变量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)
            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)
            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]，平均为 次，因此，相比于串行程序的无状态转换，并行算法的运行时间才会有如此大的波动。



本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/86537/showart_1964951.html