Parallele Pseudozufallszahlengeneratoren

20

Diese Frage bezieht sich in erster Linie auf ein praktisches Software-Engineering-Problem, aber ich wäre gespannt, ob Theoretiker weitere Einblicke in dieses Problem gewähren könnten.


Einfach gesagt, ich habe eine Monte-Carlo-Simulation, die einen Pseudozufallszahlengenerator verwendet, und ich möchte sie parallelisieren, damit 1000 Computer dieselbe Simulation parallel ausführen. Deshalb brauche ich 1000 unabhängige Ströme von Pseudozufallszahlen.

Können wir 1000 parallele Streams mit den folgenden Eigenschaften haben? Hier sollte ein sehr bekanntes und weit verbreitetes PRNG mit allen Arten von guten theoretischen und empirischen Eigenschaften sein.X

  1. Die Streams sind nachweislich so gut wie das, was ich bekommen würde, wenn ich einfach und den von erzeugten Stream in 1000 Streams aufteilen würde .XX

  2. Erzeugen die nächste Nummer in jedem Stream ist (fast) so schnell wie die nächste Nummer mit der Erzeugung .X

Anders ausgedrückt: Können wir mehrere unabhängige Streams "kostenlos" erhalten?

Wenn wir einfach , immer 999 Zahlen verwerfen und 1 auswählen, dann hätten wir natürlich Eigenschaft 1, aber wir würden in der Laufzeit um den Faktor 1000 verlieren.X

Eine einfache Idee wäre, 1000 Kopien von mit den Startwerten 1, 2, ..., 1000 zu verwenden. Dies wäre sicherlich schnell, aber es ist nicht offensichtlich, ob die Streams gute statistische Eigenschaften haben.X


Nach einigem googeln habe ich zum Beispiel folgendes gefunden:

  • Die SPRNG- Bibliothek scheint genau für diesen Zweck konzipiert zu sein und unterstützt mehrere PRNGs .

  • Mersenne Twister scheint heutzutage ein beliebtes PRNG zu sein, und ich habe einige Hinweise auf eine Variante gefunden, die mehrere Streams gleichzeitig erzeugen kann.

Aber all dies ist so weit von meinen eigenen Forschungsgebieten entfernt, dass ich nicht herausfinden konnte, was wirklich auf dem neuesten Stand ist und welche Konstruktionen nicht nur in der Theorie, sondern auch in der Praxis gut funktionieren.


Einige Erläuterungen: Ich benötige keinerlei kryptografische Eigenschaften. Dies ist für die wissenschaftliche Berechnung. Ich brauche Milliarden von Zufallszahlen, damit wir jeden Generator mit einer Periode von vergessen können <232.

Bearbeiten: Ich kann kein echtes RNG verwenden. Ich brauche einen deterministischen PRNG. Erstens hilft es sehr beim Debuggen und macht alles wiederholbar. Zweitens ermöglicht es mir, z. B. das Median-Finden sehr effizient durchzuführen, indem ich die Tatsache ausnutze, dass ich das Multi-Pass-Modell verwenden kann (siehe diese Frage ).

Bearbeiten 2: Es gibt eine eng verwandte Frage @ StackOverflow: Pseudo-Zufallszahlengenerator für Cluster-Umgebung .

Jukka Suomela
quelle
6
Warum würden Sie PRNG nicht mit unabhängig voneinander beprobten Samen verwenden? Ich verstehe nicht, wie dies nicht 1 und 2 befriedigt, da Sie keine Koordination zwischen den verschiedenen Maschinen benötigen1000
Sasho Nikolov
Ich bin kein Experte, aber kürzlich (bei der Suche nach Informationen zu einer TCS-Frage) habe ich diese Hardware gefunden: idquantique.com/true-random-number-generator/… ... eine PCI- Karte , die einen 16-Mbit / s-Stream von erzeugen kann (Quanten-) Zufallsbits. ... Sie können ein paar davon kaufen und ein paar Zufallszahlengenerator-Server implementieren ... kein großartiger theoretischer Ansatz, aber die Bits sind garantiert "gut" :-) :-)
Marzio De Biasi
@Vor: Ich möchte alles wiederholbar und deterministisch halten. Bei einem festgelegten Startwert möchte ich genau dasselbe Ergebnis erzielen, wenn ich das Experiment erneut durchführe. Und ich möchte in der Lage sein, dasselbe Experiment auf einer einzelnen Maschine durchzuführen und wieder die gleichen Ergebnisse zu erzielen. (Zum einen hilft es sehr beim Debuggen paralleler Algorithmen ...)
Jukka Suomela
@Jukka: ok! ... und ich nehme an, dass das Speichern von Milliarden nicht entpackbarer Wildbits zusammen mit den Versuchsergebnissen nicht so einfach ist :-) ... ein PRNG-Experte wird benötigt!
Marzio De Biasi
2
Vielen Dank für die bisherigen Antworten! Mal sehen, ob wir mehr Beteiligung mit einem Kopfgeld bekommen ...
Jukka Suomela

Antworten:

7

Sie können eine Weiterentwicklung des von Saito und Matsumoto entwickelten Mersenne Twister-Algorithmus verwenden:

SIMD-orientierter Fast Mersenne Twister (SFMT)

SFMT ist ein LFSR-Generator (Linear Feedbacked Shift Register), der in einem Schritt eine 128-Bit-Pseudozufallszahl generiert. SFMT wurde mit der neuesten Parallelität moderner CPUs entwickelt, beispielsweise mit mehrstufigen Pipelining- und SIMD-Befehlen (z. B. 128-Bit-Integer-Befehle). Es unterstützt 32-Bit- und 64-Bit-Ganzzahlen sowie Gleitkommazahlen mit doppelter Genauigkeit als Ausgabe. SFMT ist auf den meisten Plattformen viel schneller als MT. Nicht nur die Geschwindigkeit, sondern auch die Dimensionen von Gleichverteilungen mit v-Bit-Genauigkeit werden verbessert. Darüber hinaus ist die Wiederherstellung von einem Nullüberschuss-Anfangszustand viel schneller. Siehe Masterarbeit von Mutsuo Saito für Details .

Der Zeitraum variiert zwischen und 2 216091 - 1 .2607-12216091-1

Die Verwendung desselben Pesudorandom-Zahlengenerators zum Erzeugen mehrerer unabhängiger Datenströme durch Ändern der Anfangswerte kann ein Problem verursachen (mit vernachlässigbar geringer Wahrscheinlichkeit). Um das Problem zu vermeiden, wird die Verwendung unterschiedlicher Parameter für jede Generation bevorzugt. Diese Technik wird als dynamische Erstellung der MT-Parameter bezeichnet.

Im SFMT-Quellcode finden Sie einige Beispiele für Parametersätze (variabler Perioden) und ein awk-Skript zum Konvertieren einer CSV-Datei in einen kompilierbaren Parametersatz. Es gibt auch ein Tool namens " Dynamische Erstellung von Mersenne Twister-Generatoren ".

Die Autoren haben kürzlich eine andere modifizierte Version des Mersenne Twister entwickelt - Mersenne Twister für Grafikprozessoren -, die für die Ausführung in GPUs und die Nutzung ihrer nativen parallelen Ausführungsthreads ausgelegt ist. Das Hauptmerkmal ist die Geschwindigkeit: zufällige Ganzzahlen alle 4,6 ms auf einer GeForce GTX 260.5×107

Die Perioden der generierten Sequenz sind , 2 23209 - 1 und 2 44497 - 1 für die 32-Bit-Version und 2 23209 - 1 , 2 44497 - 1 , 2 110503 - 1 für die 64-Bit-Version. Es unterstützt 128 Parametersätze für jede Periode, mit anderen Worten, es kann 128 unabhängige Pseudozufallszahlensequenzen für jede Periode erzeugen. Wir haben Dynamic Creator für MTGP entwickelt, das mehr Parametersätze generiert211213-1223209-1244497-1223209-1244497-12110503-1

In der Tat bieten sie ein MTGPDC-Tool zum Erstellen von bis zu Parametersätzen (dh unabhängigen Streams).232

Der Algorithmus besteht die wichtigsten Zufallstests wie Diehard und NIST.

Ein vorläufiges Papier ist auch für arXiv erhältlich: Eine Variante von Mersenne Twister, die für Grafikprozessoren geeignet ist

Marzio De Biasi
quelle
Ein verwandtes, aber älteres Werkzeug ist Matsumoto und Nishimura (1998): Dynamische Erzeugung von Pseudozufallszahlengeneratoren . Aber ich konnte nicht herausfinden, welche dieser Tools nur ein Proof-of-Concept sind und welche weit verbreitete Softwarepakete von branchenführender Stärke sind.
Jukka Suomela
@Jukka: Vielleicht kannst du es direkt bei den Autoren des MTGP-Algorithmus erfragen. Von ihrer Website: "... Jedes Feedback ist willkommen (senden Sie eine E-Mail an Mutsuo Saito, saito" unter "math.sci.hiroshima-u.ac.jp" und m-mat "unter" math.sci.hiroshima- ". u.ac.jp) ... ". Vielleicht sind sie nicht zu 100% unparteiisch, aber sie kennen die Stärken und Schwächen von MTGP mit Sicherheit gut und können Ihnen sagen, ob es für Ihre Zwecke geeignet ist.
Marzio De Biasi
Es scheint, dass Mersenne Twister + Dynamic Creation der empfohlene Weg ist, dies in Mathematica zu tun.
Jukka Suomela
@Jukka: MT + DC-Paket kann auch auf Matsumotos Website gefunden werden ( math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html ); und ich denke, dass MTGP nur eine für GPUs geeignete Variante ist. Also scheint MT + DC eine bessere (und getestete / stabile) Wahl zu sein (es sei denn, Sie benötigen unbedingt zufällige Ganzzahlen alle 4,6 ms in jedem Stream :-)))5×107
Marzio De Biasi
@Vor: Wenn Sie Ihre Antwort bearbeiten und MTGP durch dcmt ersetzen , kann ich sie akzeptieren.
Jukka Suomela
12

Es scheint viele Möglichkeiten zu geben, um dieses Problem anzugehen, aber eine einfache Möglichkeit wäre die Verwendung des Blum Blum Shub PRNG. Dieses PRNG wird durch die Wiederholungsrelation , wobei N ein Semiprime ist. Um ein zufälliges Bit daraus zu ziehen, können Sie einfach die Bitparität von x i nehmen . Das Schöne daran ist, dass x i + k = x 2 k i  mod  N = x 2 k  mod  λ ( N ) i istxi+1=xi2 mod NNxi Sie können direkt jeden Schritt in der Zeitkonstante in k (dh O ( log ( N ) 3 ) oder schneller berechnen, je nachdem, welchen Multiplikationsalgorithmus Sie für das modulare Exponential verwenden. Wenn Sie also M Maschinen haben, können Sie für die von y indizierte Maschineden Generator x i + 1 verwenden , y = x 2 M mod  λ ( N ) i  mod  N , wobei x 0 , y = xxi+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

This isn't the fastest of PRNGs, though, so it will only be useful if the overhead of whatever you are doing in the simulation is significantly more than the cost of the PRNG. However it is worth pointing out that it will be much faster for certain combinations of M and N than others, particularly if the binary representation of 2M mod λ(N) contains few 1s or is small.

Joe Fitzsimons
quelle
1
I think it would be faster to let each machine generate a contiguous portion of the sequence, spacing them so far apart that they will not intersect. Anyway, using the Blum Blum Shub for non-cryptographic applications seems to me a bit an overkill.
Antonio Valerio Miceli-Barone
1
@Antonio: Yes, that would be slightly faster, particularly if you know ahead of time exactly how many trials you need. If you don't know, then I think you'll get the same scaling either way. Wierdly Blum Blum Shub was exactly the PRNG we were thaught in computational physics years ago. If you aren't using it for cryptographic purposes you can use a much smaller modulus, so it's not really that slow, and for many tasks the it will be fast compared to whatever function of the random variable you need to compute.
Joe Fitzsimons
5

How about a preprocessing phase? Given a random seed s (of size n), run X to get a pseudorandom stream of size 1000n. Denote this stream by s1,s2,,s1000, where for 1i1000, si is a contiguous portion of the stream of size n.

This preprocessing phase can be done with a very low overhead, given the fact that X is an efficient PRNG (today, we have very fast PRNG's).

Now, give si as the seed to the ith machine, which uses X to generate its own pseudorandom stream.

Given the nice properties of X, unless s is known, for any 1i<j1000, the seeds si and sj are computationally independent. Moreover, you only have to generate and save one small seed (i.e. s); therefore, this approach does not need a great deal of true randomness or storage.

M.S. Dousti
quelle
Isn't this essentially the same approach as what @Antonio suggested: use a PRNG to generate seeds for itself. I have a bit uneasy feeling about this... To give a trivial example of what might go wrong, consider a PRNG where output = internal state and the seed simply sets the internal state.
Jukka Suomela
@Jukka: My approach is similar to Antonio's, yet mine is more general. The PRNG in your example (where output = internal state) does not seem to be cryptographically secure. A PRNG is cryptographically secure if its output is computationally indistinguishable from the uniform distribution. See this for more info. PS: The Blum-Blum-Shub PRNG satisfies this condition.
M.S. Dousti
2

You could use a pseudorandom function f such as AES or ChaCha with a single random key, encrypting a counter. Assign each of the M=1000 parallel processes a unique starting value in {0,1,,M1}, and then compute the jth random block of bits for process i as f(i+jM), i.e. increment the counter in each process by M for every subsequent block of random bits.

This will give you a cryptographic RNG on every process, but it does not necessarily come with a performance cost. AES is fast if you have hardware that supports it, and ChaCha is fast regardless. Of course, you'll want to measure this in your specific setting to be sure.

Both desired properties 1 and 2 are directly satisfied by this. It's moreover convenient that the behavior of the entire system of parallel tasks is controlled by a single "seed" (the key for f).

prf
quelle
If I do not care about cryptographic strength, how does ChaCha(counter) compare with, e.g., Mersenne Twister? Is it faster or slower? Does it have have at least as good statistical properties? I tried to google, but failed to find any articles that compare these two in a non-cryptographic context.
Jukka Suomela
2

There is now a jump function for SFMT (a fast Mersenne Twister implementation).

This allows me to initialise 1000 MTs so that there is no cycle overlap. And SFMT should be faster than MTGP. Almost perfect for my purposes.

Jukka Suomela
quelle
1

You can just use 1000 instances of the Mersenne Twister initialized with different seeds.

You can sample the seeds from another Mersenne Twister, or, to be surer of their independence, from the OS cryptographic pseudorandom number generator (/dev/urandom in Linux).

The Mersenne Twister always operates on the same cyclic sequence, the seed controls where you start generating it. With indepenently sampled seeds, each generator will start at different, typically very far points, with a very small probability of intersection.

Antonio Valerio Miceli-Barone
quelle
So MT has some nice special properties that guarantee that seeding MT with another MT makes sense?
Jukka Suomela
does MT have any provable pseudorandomness properties?
Sasho Nikolov
@Jukka: not any I'm aware of. That's why I suggested to use another type of PRNG for seeding if you are particularly afraid of some strange unknown kind of correlations.
Antonio Valerio Miceli-Barone
@Sasho: the Wikipedia page mentions k-distribution and the large period.
Antonio Valerio Miceli-Barone
1
these indirect measures perplex me; is it ever the case that all you want from a PRNG is a large period and k-distribution? i doubt that; those are just heuristic sanity checks; contrast with k-wise independence which actually is a pseudorandom property that guarantees accuracy in many settings. also even if you combine two PRNG's, you at least should still show that at least the heuristic "randomness" properties hold
Sasho Nikolov