Algoritmo veloce per calcolare Pi in parallelo

Question

Sto iniziando ad apprendere CUDA e penso che il calcolo di lunghe cifre di pi sarebbe un bel progetto introduttivo.

Ho già implementato il semplice metodo Monte Carlo che è facilmente parallelizzabile. Semplicemente, ogni thread ha generato in modo casuale punti sul quadrato di unità, capire quanti giacciono all'interno del cerchio unitario e calcolare i risultati utilizzando un'operazione di riduzione.

Ma questo non è certamente l'algoritmo più veloce per il calcolo della costante. Prima, quando ho fatto questo esercizio su una singola CPU con thread, ho usato Machin-like formulae per fare il calcolo per una convergenza molto più veloce. Per chi è interessato, ciò implica esprimere pi come la somma degli arcotangenti e usare la serie di Taylor per valutare l'espressione.

Un esempio di una tale formula:

Purtroppo, ho trovato che parallelizzare questa tecnica per migliaia di fili GPU non è facile. Il problema è che la maggior parte delle operazioni sta semplicemente facendo matematica ad alta precisione anziché eseguire operazioni in virgola mobile su lunghi vettori di dati.

Quindi mi chiedo, qual è il modo più efficiente per calcolare cifre arbitrariamente lunghe di pi su una GPU?

Answer 1

si dovrebbe usare il Bailey–Borwein–Plouffe formula

Perché? Prima di tutto, hai bisogno di un algoritmo che possa essere suddiviso. Quindi, la prima cosa che mi è venuta in mente è di avere una rappresentazione del pi come una somma infinita. Quindi, ogni processore calcola un solo termine e li sommi tutti alla fine.

Quindi, è preferibile che ciascun processore manipoli valori di precisione piccola, rispetto a quelli di altissima precisione. Ad esempio, se si desidera un miliardo di decimali e si utilizzano alcune espressioni utilizzate here, come lo Chudnovsky algorithm, ciascun processore dovrà manipolare un miliardo di numeri. Questo non è semplicemente il metodo appropriato per una GPU.

Quindi, tutto sommato, la formula BBP vi permetterà di calcolare le cifre di pi greco a parte (l'algoritmo è molto fresco), e con i processori "low precisione"! Leggi la "algoritmo di cifre-estrazione BBP per π"

Vantaggi dell'algoritmo BBP per calcolare π Questo algoritmo calcola π senza la necessità di tipi di dati personalizzati con migliaia o addirittura milioni di cifre. Il metodo calcola l'ennesima cifra senza calcolare le prime n - 1 cifre e può utilizzare tipi di dati piccoli ed efficienti. L'algoritmo è il modo più veloce per calcolare l'ennesima cifra (o alcune cifre in un quartiere dell'ennesimo), ma gli algoritmi di calcolo π che usano grandi tipi di dati rimangono più veloci quando l'obiettivo è calcolare tutte le cifre da 1 an.