Szybki algorytm obliczania Pi równolegle

Question

Zaczynam się uczyć CUDA i myślę, że obliczanie długich cyfr pi byłoby miłym, wstępnym projektem.

Zaimplementowałem już prostą metodę Monte Carlo, która jest łatwa do zrównoleglenia. Po prostu każę nić losowo generować punkty na kwadracie jednostki, dowiedzieć się, ile znajduje się w kółku jednostki, i porównać wyniki za pomocą operacji redukcji.

Ale to z pewnością nie jest najszybszy algorytm do obliczania stałej. Wcześniej, kiedy robiłem to ćwiczenie na pojedynczym procesorze z gwintem, użyłem Machin-like formulae, aby wykonać obliczenia dla znacznie szybszej konwergencji. Dla zainteresowanych, obejmuje to wyrażanie pi jako sumę arcus tangensów i wykorzystanie serii Taylora do oceny ekspresji.

Przykładem takiego wzoru:

Niestety, okazało się, że parallelizing tę technikę do tysięcy wątków GPU nie jest łatwe. Problem polega na tym, że większość operacji polega po prostu na wykonywaniu precyzyjnych obliczeń matematycznych, a nie wykonywaniu operacji zmiennoprzecinkowych na długich wektorach danych.

Zastanawiam się, jaki jest najbardziej efektywny sposób obliczania dowolnie długich cyfr pi na GPU?

Answer 1

Należy użyć Bailey–Borwein–Plouffe formula

Dlaczego? Przede wszystkim potrzebujesz algorytmu, który można zepsuć. Tak więc pierwszą rzeczą, jaka przyszła mi do głowy, jest przedstawienie pi jako nieskończonej sumy. Następnie każdy procesor po prostu oblicza jeden termin, a na końcu sumuje je wszystkie.

Następnie zaleca się, aby każdy procesor manipulował wartościami o małej dokładności, w przeciwieństwie do bardzo precyzyjnych. Na przykład, jeśli chcesz mieć miliard dziesiętnych, a używasz niektórych wyrażeń używanych jako here, takich jak Chudnovsky algorithm, każdy z procesorów będzie musiał manipulować liczbą o wartości miliarda. To po prostu nie jest odpowiednia metoda dla GPU.

Podsumowując, formuła BBP pozwoli na obliczenie cyfr pi oddzielnie (algorytm jest bardzo fajny) i procesorów "niskiej precyzji"! Przeczytaj „BBP-cyfrowy algorytm ekstrakcji dla Õ”

Zalety algorytmu BBP do obliczania gatunku Ten algorytm oblicza gatunku bez konieczności niestandardowe typy danych o tysiące lub nawet miliony cyfr. Metoda oblicza n-tą cyfrę bez obliczania pierwszych n-1 cyfr i może użyć małych, wydajnych typów danych. Algorytm jest najszybszym sposobem obliczenia n-tej cyfry (lub kilku cyfr w sąsiedztwie n-tego), ale algorytmy obliczania π używające dużych typów danych zachowują się szybciej, gdy celem jest obliczenie wszystkich cyfr od 1 do n.