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

Question

在任何快速回答之前，我想解释一下我的需求。我正在从事一个 C-Posix 项目，该项目专注于使用 Pthreads 进行并行计算。我做了研究，发现了几十种计算 Pi 的算法：Bailey–Borwein–Plouffe 公式、Machin-like 公式、Leibniz formula for π、Chudnovsky algorithm、monte-carlo、Ramanujan 等。问题是我不需要 "Best" 算法在速度收敛或每次迭代的数字方面，因为获得 pi 不是项目本身 [=22] 的 objective =].该项目的真正 objective 是比较使用 pthreads 串行和并行解决的同一编程问题的性能。例如，在项目结束时，我希望得到这样的比较 table：

在说了所有这些之后，我需要一个尽可能简单的算法，在 pthreads（不是 MPI、OpenMP 或类似的东西）中编码很简单（令人尴尬的并行将是一个完美的选择）最后但不是至少算法必须是 suitable 以显示对并行化的巨大影响

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

谢谢！

Answer 1

Monte Carlo 近似 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 对于每个线程都是独立的，否则运行多个线程不会带来任何改进。

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

Need an algorithm to calculate pi in parallel with pthreads in c

c

algorithm

parallel-processing

pi

pthreads