在并行计算中快速计算Pi的算法

Question

在并行计算中快速计算Pi的算法

algorithmparallel-processingcudanumerical-methodspi

25

我开始学习CUDA，认为计算圆周率长数字会是一个不错的入门项目。

我已经实现了简单的蒙特卡罗方法，这很容易并行化。我让每个线程在单位正方形上随机生成点，计算有多少个点在单位圆内，并使用约简操作累积结果。

但这显然不是计算该常数的最快算法。以前，在单线程CPU上做这个练习时，我使用Machin-like formulae来进行远比较快的收敛计算。对于那些感兴趣的人，这涉及将pi表示为反正切的和，并使用泰勒级数来评估表达式。

其中一种公式如下：

enter image description here

不幸的是，我发现将此技术并行化到数千个GPU线程不容易。问题在于大部分操作只是进行高精度数学运算，而不是在长数据向量上执行浮点运算。

因此，我想知道在GPU上计算任意长的圆周率数字的最有效方法是什么？

- tskuzzy

你看过这个吗：https://sites.google.com/a/nirmauni.ac.in/cudacodes/ongoing-projects/automatic-conversion-of-source-code-for-c-to-cuda-c/converted-programs/calculate-value-of-pi - James Black

我认为这个程序不能进行任意精度计算。 - tskuzzy

2

@JamesBlack：你链接的代码完全是胡说八道。它似乎是将一段串行的C代码毫无头绪地自动翻译成了GPU代码，其中许多线程计算了级数展开式相同的前1000个元素。该代码执行的计算量实际上是99.99%的冗余。 - talonmies

Erlang？我认为它可以用于并行处理。不确定它是否有助于算法实现。 - Code Droid

参见：https://dev59.com/aHVD5IYBdhLWcg3wXamd 和 https://dev59.com/smYq5IYBdhLWcg3wrihD - assylias

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- B. Decoster · Accepted Answer

你应该使用贝利-博尔温-普劳夫公式。

为什么呢？首先，你需要一个可以分解的算法。所以，我首先想到的是将pi表示为无限和。然后，每个处理器只计算一个项，最后将它们全部相加。

其次，最好让每个处理器操作小精度值，而不是非常高精度的值。例如，如果你想要十亿位小数，并且使用这里使用的一些表达式，比如Chudnovsky算法，每个处理器都需要操作一个十亿位长的数字。这对于GPU来说显然不是合适的方法。

总之，BBP公式可以让你单独计算圆周率的数字（这个算法非常酷），并且使用“低精度”处理器！请阅读“用于π的BBP数字提取算法”。

BBP算法计算π的优点是不需要自定义数据类型来计算数千甚至数百万位数。该方法计算第n位数字而无需计算前n-1个数字，并且可以使用小型高效的数据类型。该算法是计算第n位数字（或第n位数字附近的几个数字）的最快方法，但在目标是计算从1到n的所有数字时，使用大型数据类型的π计算算法仍然更快。