Równoległe generatory liczb pseudolosowych

Pytanie to dotyczy przede wszystkim praktycznego problemu z inżynierią oprogramowania, ale z ciekawością dowiedziałbym się, czy teoretycy mogliby uzyskać wgląd w ten problem.

Mówiąc prościej, mam symulację Monte Carlo, która korzysta z generatora liczb pseudolosowych i chciałbym go zrównoleglić, aby 1000 komputerów działało równolegle z tą samą symulacją. Dlatego potrzebuję 1000 niezależnych strumieni liczb pseudolosowych.

Czy możemy mieć 1000 równoległych strumieni o następujących właściwościach? Tutaj powinien być bardzo dobrze znanym i szeroko badanym PRNG o wszelkiego rodzaju ładnych właściwościach teoretycznych i empirycznych.$X$

1. Strumienie są tak dobre, jak to, co bym otrzymał, gdybym po prostu użył i podzielił strumień wygenerowany przez X na 1000 strumieni.$X$$X$

2. Generowanie następny numer w każdym strumieniu jest (prawie) tak szybko jak generowanie następny numer z .$X$

Innymi słowy: czy możemy uzyskać wiele niezależnych strumieni „za darmo”?

Oczywiście, gdybyśmy po prostu użyli , zawsze odrzucając 999 liczb i wybierając 1, wtedy z pewnością mielibyśmy właściwość 1, ale stracilibyśmy w czasie działania o współczynnik 1000.$X$

Prostym pomysłem byłoby użycie 1000 kopii , z nasionami 1, 2, ..., 1000. To z pewnością byłoby szybkie, ale nie jest oczywiste, czy strumienie mają dobre właściwości statystyczne.$X$

Po pewnym Googlingu znalazłem na przykład:

• SPRNG biblioteka wydaje się być zaprojektowany do tego celu dokładnie i obsługuje wiele PRNGs .

• Wydaje się, że Mersenne Twister jest obecnie popularnym PRNG, i znalazłem kilka odniesień do wariantu, który jest w stanie wytwarzać wiele strumieni równolegle.

Ale to wszystko jest tak dalekie od moich własnych obszarów badawczych, że nie mogłem dowiedzieć się, co tak naprawdę jest najnowocześniejsze i które konstrukcje działają dobrze nie tylko w teorii, ale także w praktyce.

Kilka wyjaśnień: Nie potrzebuję żadnych właściwości kryptograficznych; to jest do obliczeń naukowych. Potrzebuję miliardów liczb losowych, abyśmy mogli zapomnieć o dowolnym generatorze z okresem .$< 2^{32}$

Edycja: Nie mogę użyć prawdziwego RNG; Potrzebuję deterministycznego PRNG. Po pierwsze, bardzo pomaga w debugowaniu i sprawia, że ​​wszystko jest powtarzalne. Po drugie, pozwala mi to np. Bardzo efektywnie wyszukiwać medianę, wykorzystując fakt, że mogę korzystać z modelu wieloprzebiegowego (patrz to pytanie ).

Edycja 2: Istnieje ściśle powiązane pytanie @ StackOverflow: Generator liczb pseudolosowych dla środowiska klastrowego .

Możesz użyć ewolucji algorytmu Mersenne Twister opracowanego przez Saito i Matsumoto:

Zorientowany na SIMD szybki Mersenne Twister (SFMT)

SFMT jest generatorem LFSR (Linear Feedbacked Shift Register), który generuje 128-bitową liczbę całkowitą pseudolosową w jednym kroku. SFMT został zaprojektowany z wykorzystaniem najnowszych równoległości współczesnych procesorów, takich jak wielostopniowe potokowanie i instrukcje SIMD (np. 128-bitowa liczba całkowita). Obsługuje 32-bitowe i 64-bitowe liczby całkowite, a także zmiennoprzecinkowy podwójnej precyzji jako wynik. SFMT jest znacznie szybszy niż MT, na większości platform. Poprawiona jest nie tylko prędkość, ale także wymiary równomiernych rozkładów z dokładnością v-bit. Ponadto odzyskiwanie ze stanu początkowego z nadwyżką 0 jest znacznie szybsze. Szczegóły w pracy magisterskiej na temat Mutsuo Saito .

Okres wynosi od do 2 216091 - 1 .$2^{607}-1$$2^{216091}-1$

Korzystanie z tego samego generatora liczb pesudorandomowych do generowania wielu niezależnych strumieni przez zmianę wartości początkowych może powodować problem (z nieistotnym małym prawdopodobieństwem). Aby uniknąć problemu, preferowane jest stosowanie różnych parametrów dla każdej generacji. Ta technika nazywa się dynamicznym tworzeniem parametrów MT.

W kodzie źródłowym SFMT można znaleźć kilka przykładów zestawów parametrów (okresów zmiennych) i skrypt awk do konwersji pliku CSV na kompilowalny zestaw parametrów. Istnieje również narzędzie o nazwie „ Dynamiczne tworzenie generatorów Mersenne Twister ”.

$5 \times 10^7$

$2^{11213}-1$$2^{23209}-1$$2^{44497}-1$$2^{23209}-1$$2^{44497}-1$$2^{110503}-1$

$2^{32}$

Algorytm przechodzi główne testy losowości, takie jak Diehard i NIST.

Wstępny artykuł jest także dostępny na arXiv: wariant Mersenne Twister odpowiedni dla procesorów graficznych

$x_{i+1} = x_i^2 \mbox{ mod }N$$N$$x_i$$x_{i+k} = x_i^{2^k}\mbox{ mod }N = x_i^{2^k \mbox{ mod } \lambda(N)}\mbox{mod }N$$k$$O(\log(N)^3)$$M$$y$$x_{i+1,y} = x_i^{2^M \mbox{mod }\lambda(N)}\mbox{ mod }N$$x_{0,y} = x_0^{2^y \mbox{ mod }\lambda(N)}\mbox{ mod }N$$x_0$

$M$$N$$2^M \mbox{ mod }\lambda(N)$

$s$$n$$X$$1000n$$s_1,s_2,\ldots,s_{1000}$$1\le i \le 1000$$s_i$$n$

$X$

$s_i$$i$$X$

$X$$s$$1 \le i < j \le 1000$$s_i$$s_j$$s$

$f$$M = 1000$$\{ 0, 1, \ldots, M - 1 \}$$j$$i$$f(i + jM)$$M$

Zapewni to kryptograficzne RNG na każdym procesie, ale niekoniecznie wiąże się to z kosztem wydajności. AES jest szybki, jeśli masz sprzęt, który go obsługuje, a ChaCha jest szybki niezależnie. Oczywiście, aby to upewnić, będziesz chciał zmierzyć to w swoich konkretnych ustawieniach.

$f$

Dostępna jest teraz funkcja skoku dla SFMT (szybka implementacja Mersenne Twister).

To pozwala mi zainicjować 1000 MT, aby cykl się nie nakładał. A SFMT powinien być szybszy niż MTGP. Prawie idealny do moich celów.

Możesz po prostu użyć 1000 instancji Mersenne Twister zainicjowanych różnymi nasionami.

Możesz próbkować nasiona z innego Mersenne Twister lub, aby być pewnym ich niezależności, z systemu kryptograficznego generatora liczb pseudolosowych (/ dev / urandom w Linuksie).

Mersenne Twister zawsze działa w tej samej sekwencji cyklicznej, kontrola nasion rozpoczyna się w miejscu, w którym zaczniesz go generować. W przypadku niezależnie próbkowanych nasion, każdy generator uruchomi się w różnych, zazwyczaj bardzo odległych punktach, z bardzo małym prawdopodobieństwem przecięcia.