Algoritmo rápido para calcular Pi en paralelo

Question

Estoy empezando a aprender CUDA y creo que el cálculo de dígitos largos de pi sería un buen proyecto introductorio.

Ya he implementado el método simple de Monte Carlo, que es fácil de paralelizar. Simplemente hago que cada hilo genere aleatoriamente puntos en el cuadrado unitario, calcule cuántos se encuentran dentro del círculo unitario y recuente los resultados usando una operación de reducción.

Pero eso ciertamente no es el algoritmo más rápido para calcular la constante. Antes, cuando hacía este ejercicio en una única CPU con hebras, utilicé Machin-like formulae para hacer el cálculo de una convergencia mucho más rápida. Para los interesados, esto implica expresar pi como la suma de arctangents y usar series de Taylor para evaluar la expresión.

Un ejemplo de tal fórmula:

Desafortunadamente, he encontrado que la paralelización de esta técnica para miles de hilos GPU no es fácil. El problema es que la mayoría de las operaciones simplemente realizan cálculos matemáticos de alta precisión en lugar de realizar operaciones de punto flotante en vectores largos de datos.

Así que me pregunto, ¿cuál es la forma más eficiente de calcular arbitrariamente dígitos largos de pi en una GPU?

Answer 1

Se debe utilizar la Bailey–Borwein–Plouffe formula

¿Por qué? En primer lugar, necesita un algoritmo que pueda descomponerse. Entonces, lo primero que me vino a la mente es tener una representación de pi como una suma infinita. Entonces, cada procesador solo computa un término, y usted suma todos al final.

Luego, es preferible que cada procesador manipule valores de precisión pequeños, a diferencia de los de muy alta precisión. Por ejemplo, si quiere mil millones de decimales y usa algunas de las expresiones utilizadas como here, como Chudnovsky algorithm, cada uno de sus procesadores deberá manipular un número de mil millones de largo. Simplemente no es el método apropiado para una GPU.

Así que, en general, la fórmula BBP le permitirá calcular los dígitos de pi por separado (el algoritmo es muy bueno) y con procesadores de "baja precisión". Lea el "algoritmo de extracción de dígitos BBP, por π"

Ventajas del algoritmo para calcular π BBP Este algoritmo calcula π sin requerir tipos de datos personalizados que tienen miles o incluso millones de dígitos. El método calcula el enésimo dígito sin calcular los primeros n - 1 dígitos, y puede usar tipos de datos pequeños y eficientes. El algoritmo es la forma más rápida de calcular el enésimo dígito (o unos pocos dígitos en un vecindario de la enésima), pero los algoritmos de computación π usan grandes tipos de datos permanecen más rápidos cuando el objetivo es calcular todos los dígitos de 1 a n.