并行计算Pi的快速算法
tsk*_*zzy 20 algorithm parallel-processing pi cuda numerical-methods
我开始学习CUDA,我认为计算pi的长数字将是一个很好的介绍性项目.
我已经实现了简单的蒙特卡罗方法,该方法很容易并行化.我只是让每个线程在单位正方形上随机生成点,计算单位圆内有多少点,并使用缩小操作计算结果.
但这当然不是计算常数的最快算法.以前,当我在单线程CPU上进行此练习时,我使用类似Machin的公式来进行计算,以便更快地收敛.对于那些感兴趣的人,这涉及将pi表示为反复数组的总和并使用泰勒级数来评估表达式.
这样一个公式的一个例子:
不幸的是,我发现将这种技术并行化到数千个GPU线程并不容易.问题是大多数操作只是在进行高精度数学运算,而不是对长数据向量进行浮点运算.
所以我想知道,在GPU上计算pi的任意长数字的最有效方法是什么？
Fez*_*vez 14
为什么？首先,您需要一个可以分解的算法.所以,我想到的第一件事就是将pi表示为无限和.然后,每个处理器只计算一个术语,最后将它们全部加起来.
然后,优选地,每个处理器操纵小精度值,而不是非常高精度的值.例如,如果你想要十亿个小数,并且你使用这里使用的一些表达式,比如Chudnovsky算法,那么你的每个处理器都需要操作十亿个长数.这根本不适合GPU.
所以,总而言之,BBP公式将允许您分别计算pi的数字(算法非常酷),以及"低精度"处理器!阅读"π的BBP数字提取算法"
BBP算法用于计算π的优点该算法计算π 而不需要具有数千甚至数百万个数字的自定义数据类型.该方法在不计算前n-1个数字的情况下计算第n个数字,并且可以使用小的,有效的数据类型.该算法是计算第n个数字(或第n个邻域中的几个数字)的最快方法,但是当目标是计算从1到n的所有数字时,使用大数据类型的π计算算法保持更快.
- 所以我理解你在（令人尴尬的）并行计算你想要的所有数字的想法。但这并不能保证该算法*有效*；每个处理器/GPU 可能正在计算其他人可以共享的信息。也许这个算法是有效的，你只是没有告诉我们如何。但如果不是，您不会因为可以并行化一个低效的算法。（也许更有用的度量是数字/晶体管或数字/瓦特产生）。 (2认同)
- 嗯，这是一个“体面的”算法。它不是最好的（记录由其他算法保存），但仍然不错。让我们也记住，OP 不希望打破记录，但是`我开始学习 CUDA，我认为计算 pi 的长数字将是一个很好的介绍性项目。` (2认同)