Schneller Algorithmus Pi parallel zu berechnen

Question

Ich fange an, CUDA zu lernen, und ich denke, die Berechnung langer Ziffern von Pi wäre ein schönes, einleitendes Projekt.

Ich habe bereits die einfache Monte-Carlo-Methode implementiert, die leicht parallelisiert werden kann. Ich lasse jeden Faden zufällig Punkte auf dem Einheitsquadrat erzeugen, finde heraus, wie viele innerhalb des Einheitskreises liegen, und ordne die Ergebnisse mit einer Reduktionsoperation zusammen.

Aber das ist sicherlich nicht der schnellste Algorithmus zur Berechnung der Konstante. Vorher, als ich diese Übung auf einer Single-Thread-CPU gemacht habe, habe ich Machin-like formulae verwendet, um die Berechnung für eine viel schnellere Konvergenz durchzuführen. Für Interessierte bedeutet dies, dass pi als die Summe der arctangences ausgedrückt wird und Taylor-Reihen verwendet werden, um den Ausdruck zu bewerten.

Ein Beispiel für eine solche Formel:

Leider fand ich, dass Tausende von GPU-Threads, um diese Technik zu parallelisieren ist nicht einfach. Das Problem besteht darin, dass die Mehrzahl der Operationen einfach Hochpräzisions-Mathematik durchführt, im Gegensatz zu Gleitkommaoperationen an langen Datenvektoren.

Also frage ich mich, Was ist die effizienteste Möglichkeit, beliebig lange Ziffern von Pi auf einer GPU zu berechnen?

Answer 1

sollten Sie verwenden die Bailey–Borwein–Plouffe formula

Warum? Zuallererst benötigen Sie einen Algorithmus, der aufgeteilt werden kann. Das erste, was mir in den Sinn kam, ist eine Darstellung von Pi als unendliche Summe. Dann berechnet jeder Prozessor nur einen Begriff, und Sie summieren sie alle am Ende.

Dann ist es vorzuziehen, dass jeder Prozessor Werte mit kleiner Genauigkeit manipuliert, im Gegensatz zu sehr genauen. Wenn Sie beispielsweise eine Milliarde Dezimalstellen verwenden möchten und einige der verwendeten Ausdrücke here verwenden, wie z. B. die Chudnovsky algorithm, muss jeder Ihrer Prozessoren eine Milliarden lange Zahl manipulieren. Das ist einfach nicht die geeignete Methode für eine GPU.

Also, alles in allem, die BBP Formel wird es Ihnen ermöglichen, die Ziffern von pi getrennt zu berechnen (der Algorithmus ist sehr cool), und mit "Low Precision" Prozessoren! Lesen Sie den „BBP digit-Extraktionsalgorithmus für π“

Vorteile des BBP-Algorithmus zur Berechnung von π Dieser Algorithmus berechnet π ohne benutzerdefinierte Datentypen zu erfordern Tausende oder sogar Millionen von Stellen mit. Die Methode berechnet die n-te Ziffer ohne Berechnung der ersten n - 1 Ziffern und kann kleine, effiziente Datentypen verwenden. Der Algorithmus ist der schnellste Weg zur Berechnung der n-ten Ziffer (oder einiger Ziffern in einer Nachbarschaft des n-ten), aber π-Rechenalgorithmen, die große Datentypen verwenden, bleiben schneller, wenn alle Ziffern von 1 bis n berechnet werden sollen.