MPI 求π的程序，谢谢大神

Question

int main(argc,argv)
int argc; char *argv[];
{
    int done = 0, n, myid, numprocs, i, rc;
    double PI25DT = 3.141592653589793238462643;
    double mypi, pi, h, sum, x, a;

    MPI_Init(&argc,&argv);
    MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
    MPI_Comm_rank(MPI_COMM_WORLD,&myid);

    while (!done) {
        if (myid == 0) {
            printf("Enter the number of intervals: (0 quits) ");
            scanf("%d", &n);
        }
                                                     //root
        MPI_Bcast(&n, 1, MPI_INT,  0,  MPI_COMM_WORLD);
        if (n == 0) break;
        h = 1.0 / (double) n;   // width of each sub
        sum = 0.0;
        for (i = myid + 1; i <= n; i += numprocs)  // **这个 for-loop 里面的为什么是 i <= n; i += numprocs?  怎么理解这里？**

        {
            x = h * ((double)i - 0.5);
            sum += 4.0 / (1.0 + x*x);
        }

        mypi = h * sum;
        MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
        if (myid == 0) printf("pi is approximately %.16f, Error is %.16f\n", pi, fabs(pi - PI25DT));
    }

    MPI_Finalize();
}

哪个大神可以给我解释下这个算法的原理吗？ 就好像哪个 for loop 为什么是 i += numprocs， 还有我不是很了解 MPI_BCAST AND MPI_REDUCE 在这里是怎么运行的。谢谢啦

Answer 1

此程序关键在于以下几点：

多进程并行

MPI_Comm_size与MPI_Comm_rank即创建了numprocs个相同的进程，但是给他们赋予了不同的id

Map-Reduce思想

Map: 将一个大任务分解成多个小任务

Reduce： 合并小任务

MPI_Bcast， MPI_Reduce是MPI进程通行、协作的机制。顾名思义，前者将n的值广播给所有进程，使得所有进程使用相同n值；
后者将所有mypi相加到pi，合并得最终结果。

(可以搜索Map-Reduce思想)

任务划分

此程序采用积分法计算PI的近似值，积分法相比你已了解，无需多言，说一下它的任务分解。

首先， 将积分区间(0-1)划分为n个矩形， 编号1 -> n。

然后将n个矩形均分到numprocs个进程：

第1个进程需要计算的矩形编号集： 1, numprocs+1, 2*numprocs+1, ...

第2个进程需要计算的矩形编号集： 2, numprocs+2, 2*numprocs+2, ...

....
(这就是i+=numprocs的原因)