c - 需要一种算法来与 c 中的 pthread 并行计算 pi

Question

在快速回答之前，我想先解释一下我的需求。我正在开发一个 C-Posix 项目，专注于使用 Pthreads 进行并行计算。我做了研究，发现了几十种计算 Pi 的算法:Bailey–Borwein–Plouffe 公式、Machin-like 公式、Leibniz π 公式、Chudnovsky 算法、monte-carlo、Ramanujan 等。 问题是，就速度收敛或每次迭代的位数而言，我不需要“最佳”算法，因为获取 pi 本身并不是项目的目标。该项目的真正目标是比较使用 pthreads 解决串行和并行的相同编程问题的性能。 例如，在项目结束时，我希望得到这样的比较表:

说完所有这些之后，我需要一个尽可能简单的算法，可以简单地在 pthreads 中进行编码(不是 MPI、OpenMP 或类似的)(令人尴尬的并行将是一个完美的选择)，最后但并非最不重要的算法必须合适才能表现出对并行化有很大影响

PD:如果任何人能够提出适合该项目的任何其他并行计算，我也将不胜感激。

谢谢!

Answer 1

用于逼近 pi(任意精度)的蒙特卡罗方法很容易并行化。在伪代码中:

total=0;
inside=0;
while(total<whatever) {
    double1=random(0,1); //Random number from zero to 1
    double2=random(0,1);
    total++;
    if(double1**2 + double2**2 < 1) {inside++;}
}
pi=4*inside/total;

循环内的所有内容都可以在任意数量的线程上并行化，您只需在最后将结果相加即可。

编辑:正如 caf 在评论中提到的那样，RNG 对于每个线程都是独立的，这一点很重要，否则运行多个线程不会带来任何改进。