Równoległe generatory liczb pseudolosowych

20

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.XX

  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 .<232

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 .

Jukka Suomela
źródło
6
dlaczego nie miałbyś użyć PRNG z niezależnie próbkowanych nasion? nie rozumiem, jak to nie spełnia 1 i 2, ponieważ nie potrzebujesz koordynacji między różnymi maszynami1000
Sasho Nikolov
Nie jestem ekspertem, ale ostatnio (szukając informacji o pytaniu TCS) znalazłem ten sprzęt: idquantique.com/true-random-number-generator/ ... ... karta PCI, która może generować strumień 16 Mb / s (kwantowe) losowe bity. ... możesz kupić kilka z nich i zaimplementować kilka serwerów generatora liczb losowych ... niezbyt dobre podejście teoretyczne, ale bity są gwarantowane "dobre" :-) :-)
Marzio De Biasi
@Vor: Chciałbym, aby wszystko było powtarzalne i deterministyczne. Biorąc pod uwagę ustalone ziarno, chcę uzyskać dokładnie ten sam wynik, jeśli ponownie przeprowadzę eksperyment. I chcę móc przeprowadzić ten sam eksperyment na jednej maszynie i ponownie uzyskać te same wyniki. (Po pierwsze, bardzo pomaga to przy debugowaniu równoległych algorytmów ...)
Jukka Suomela
@Jukka: ok! ... i przypuszczam, że przechowywanie miliardów nieskomplikowanych dzikich bitów wraz z wynikami eksperymentu nie jest tak wykonalne :-) ... potrzebny jest ekspert PRNG!
Marzio De Biasi
2
Dzięki za dotychczasowe odpowiedzi! Zobaczmy, czy otrzymamy większy udział z nagrodą ...
Jukka Suomela,

Odpowiedzi:

7

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 .2607122160911

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×107

2112131223209124449712232091244497121105031

232

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

Marzio De Biasi
źródło
Powiązane, ale starsze narzędzie to Matsumoto i Nishimura (1998): Dynamiczne tworzenie generatorów liczb pseudolosowych . Ale nie byłem w stanie dowiedzieć się, które z tych narzędzi są tylko dowodem koncepcji, a które są powszechnie stosowanymi pakietami oprogramowania o dużej mocy.
Jukka Suomela,
@Jukka: być może możesz zwrócić się bezpośrednio do autorów algorytmu MTGP. Z ich strony: „... Wszelkie opinie są mile widziane (wyślij wiadomość e-mail do Mutsuo Saito, saito„ at sign ”math.sci.hiroshima-u.ac.jp i m-mat” at sign „math.sci.hiroshima- u.ac.jp) ... ”. Być może nie są w 100% bezstronni, ale z pewnością dobrze znają mocne i słabe strony MTGP i mogą powiedzieć, czy może być odpowiedni dla twoich celów.
Marzio De Biasi,
Wygląda na to, że Mersenne Twister + Dynamic Creation to zalecany sposób na zrobienie tego w Mathematica.
Jukka Suomela,
5×107
@Vor: Jeśli edytujesz swoją odpowiedź i zamieniasz MTGP na dcmt , mogę to zaakceptować.
Jukka Suomela,
12

xi+1=xi2 mod NNxixi+k=xi2k mod N=xi2k mod λ(N)mod NkO(log(N)3)Myxi+1,y=xi2Mmod λ(N) mod Nx0,y=x02y mod λ(N) mod Nx0

MN2M mod λ(N)

Joe Fitzsimons
źródło
1
Myślę, że szybciej byłoby pozwolić każdej maszynie wygenerować ciągłą część sekwencji, rozstawiając je tak daleko od siebie, aby się nie przecinały. W każdym razie używanie Blum Blum Shub do aplikacji niekryptograficznych wydaje mi się nieco przesadne.
Antonio Valerio Miceli-Barone
1
@Antonio: Tak, byłoby to nieco szybsze, szczególnie jeśli wiesz z góry dokładnie, ile prób potrzebujesz. Jeśli nie wiesz, myślę, że i tak uzyskasz takie samo skalowanie. Dziwnie Blum Blum Shub był dokładnie PRNG, którego nauczyliśmy się fizyki obliczeniowej lata temu. Jeśli nie używasz go do celów kryptograficznych, możesz użyć znacznie mniejszego modułu, więc nie jest on tak powolny, a dla wielu zadań będzie szybki w porównaniu do dowolnej funkcji zmiennej losowej, którą musisz obliczyć.
Joe Fitzsimons,
5

snX1000ns1,s2,,s10001i1000sin

X

siiX

Xs1i<j1000sisjs

MS Dousti
źródło
Czy nie jest to zasadniczo to samo podejście, co sugerował @Antonio: użyj PRNG, aby wygenerować nasiona dla siebie. Mam trochę niepokojące przeczucie ... Aby podać trywialny przykład tego, co może pójść nie tak, rozważ PRNG, w którym wyjście = stan wewnętrzny, a ziarno po prostu ustawia stan wewnętrzny.
Jukka Suomela,
@Jukka: Moje podejście jest podobne do Antonio, ale moje jest bardziej ogólne. PRNG w twoim przykładzie (gdzie wyjście = stan wewnętrzny) nie wydaje się być kryptograficznie bezpieczny. PRNG jest kryptograficznie bezpieczny, jeśli jego dane wyjściowe są obliczeniowo nie do odróżnienia od jednolitego rozkładu. Zobacz to, aby uzyskać więcej informacji. PS: Blum-Blum-Shub PRNG spełnia ten warunek.
MS Dousti
2

fM=1000{0,1,,M1}jif(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

prf
źródło
Jeśli nie dbam o siłę kryptograficzną, jak ChaCha (licznik) wypada na przykład z Mersenne Twister? Czy to jest szybsze czy wolniejsze? Czy ma co najmniej tak dobre właściwości statystyczne? Próbowałem google, ale nie udało mi się znaleźć artykułów porównujących te dwa w kontekście niekryptograficznym.
Jukka Suomela,
2

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.

Jukka Suomela
źródło
1

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.

Antonio Valerio Miceli-Barone
źródło
Czyli MT ma jakieś wyjątkowe właściwości, które gwarantują, że wysiew MT innym MT ma sens?
Jukka Suomela,
czy MT ma jakieś udowodnione właściwości pseudolosowe?
Sasho Nikolov
@Jukka: nie jestem tego świadomy. Właśnie dlatego zasugerowałem użycie innego rodzaju PRNG do wysiewu, jeśli szczególnie obawiasz się jakiegoś dziwnego nieznanego rodzaju korelacji.
Antonio Valerio Miceli-Barone
@Sasho: strona Wikipedii wspomina o dystrybucji K i dużym okresie.
Antonio Valerio Miceli-Barone
1
kk