Wie kann ich einen parallelen linearen kongruenten Pseudozufallszahlengenerator für die maximale Periode setzen?

8

Normalerweise verwende ich den Aufruf, wenn ich einen sequentiellen Zufallszahlengenerator in C setze

srand(time(NULL))

dann benutze

rand() mod N

um eine zufällige ganze Zahl zwischen 0 und N-1 zu erhalten. Wenn ich dies jedoch parallel mache, sind die Aufrufe zur Zeit (NULL) so nahe beieinander, dass sie genau dieselbe Nummer haben.

Ich habe versucht, einen linearen kongruenten Zufallszahlengenerator zu verwenden:

xn+1:=axn+c(modm) für einige ganze Zahlen a,c, und m .

Ich weiß, dass die Wahl von m=2k für eine große ganze Zahl k schnellen Ergebnissen führt, da der Moduloperator durch Abschneiden von Ziffern berechnet werden kann. Es fällt mir jedoch schwer, Samen zu etablieren, die zufällige Sequenzen mit einer großen parallelen Periode produzieren. Ich weiß, dass eine Periodenlänge maximal ist, wenn

  1. c und m sind Primzahlen zueinander
  2. a-1 ist durch alle Primfaktoren von m teilbar
  3. Wenn m ein Vielfaches von 4 ist, muss a-1 auch ein Vielfaches von 4 sein.

(Quelle: Wikipedia )

Aber wie stelle ich sicher, dass alle Zufallszahlenströme diese maximale Eigenschaft haben? Wie kann ich in Bezug auf den MPI die maximalen Perioden mit der linearen Kongruenzmethode einbeziehen rankund sizeerzeugen? Wäre es einfacher, einen Lagged Fibonacci oder Mersenne Twister zu verwenden, um längere parallele Zufallsströme zu erzeugen?

Paul
quelle
3
Nur als Randnotiz möchten Sie mit ziemlicher Sicherheit kein lineares kongruentes PRNG für wissenschaftliche Berechnungen verwenden. Sie können Räume mit einer Dimension über 1 nicht richtig abtasten. Das heißt: Sie können nicht einmal eine richtige Stichprobe von Punkten in einer Ebene zeichnen.
dmckee --- Ex-Moderator Kätzchen
1
@dmckee: Der Satz von Marsaglia ist sicherlich für einige wissenschaftliche Berechnungen relevant , aber es wäre unfair zu sagen, dass er LCGs für alle wissenschaftlichen Berechnungen disqualifiziert. Manchmal ist ein schnelles PRNG gleich wichtig, und die Anzahl der übergreifenden Vektoren (durch den Ursprung) ist oft wichtiger als die Anzahl der Hyperebenen, die den Probenraum abdecken.
Jack Poulson
2
@dmckee: Sie haben vielleicht Recht mit LCG, aber für viele Anwendungen reicht 1D aus.
Paul
1
@ JackPerhaps Ich bin voreingenommen von der Art meiner Arbeit, und ich bin mir dessen bewusst, weshalb ich die Art des Defekts angegeben habe. Paul: Es gibt eine Vielzahl gut untersuchter PRNGs und viele Kompromisse (Geschwindigkeit, Periode, kryptografische Sicherheit und Fähigkeit, hochdimensionale Tupel zu zeichnen). Ich benutze Mersenne Twister sowohl in Sachen, die ich von Hand codiere, als auch als Standard-PRNG in ROOT . Es ist nicht die schnellste, aber das Zeichnen von Zahlen ist im Allgemeinen ein bescheidener Beitrag zu meiner Laufzeit.
dmckee --- Ex-Moderator Kätzchen
1
Als eine andere Seite beachten, wenn Sie benötigen LC PRNGs verwenden (vielleicht aus Geschwindigkeitsgründen) : Sie verwenden möchten , nicht moddie niederwertigen Bits zu greifen - wie Jonathan Dursi vorgeschlagen, sie sind viel weniger zufällig. Teilen Sie stattdessen Ihre (int) Zufallszahl durch maxint / range, um den gewünschten Bereich zu erhalten. Es kostet Sie eine Kluft, aber es ist wahrscheinlich eine billigere Option, um die Qualität Ihres Zufallszahlenstroms zu verbessern, als zu einem anderen PRNG zu wechseln.
Mark Booth

Antworten:

9

Der Trick besteht darin, den LCG-Stream jedes Prozesses zu verschachteln: Für Prozesse modifizieren wir die LCGp

xn+1:=axn+c(modm),

sein

xn+p:=Apxn+Cp(modm),

wobei und effektiv Schritte vorwärts gehen . Wir können sie schnell ableiten, indem wir den ursprünglichen LCG-Schritt erweitern:ApCpp

xn+2=a(axn+c)+c(modm)=a2xn+(a+1)c(modm),

und das Muster ist , dass und ist das Ergebnis, beginnend mit der Nummer , sukzessiv durch Multiplikation und Zugabe Mal, dann durch Multiplikation , die alle .Apapmodm,Cp0a1 pcmodm

Der letzte Schritt besteht darin, sicherzustellen, dass sich das Schritt-LCG jedes Prozesses nicht überlappt: Initialisieren Sie einfach den Prozess mit Rang mit und ein paralleles LCG mit einzelnen Perioden von ist bereit, wobei die ursprüngliche Periode und ist Anzahl der Prozesse. Wenn das modifizierte LCG jedes Prozesses gleichermaßen verwendet wird, wird die gesamte Periode parallel wiederhergestellt.prxrN/pNp

Ich habe dies vor ungefähr sechs Monaten implementiert (vielleicht naiv), und Sie können den Code hier finden .

Jack Poulson
quelle
Das ist ein interessanter Ansatz. Es nimmt effektiv N Tupel aus einem einzelnen LC PRNG-Stream auf verteilte Weise. Es leidet immer noch unter den in Wikipedia erwähnten Korrelationsproblemen , erfordert jedoch keinen Synchronisationsaufwand für eine zentralisierte PRNG-Quelle. Es würde mich interessieren, wie die Qualität dieser Streams mit der Korrelation zwischen Streams verglichen wird, die von mehreren LC-PRNGs mit unterschiedlichen Konstanten erstellt wurden.
Mark Booth
Gute Idee; Dies scheint für die GPU geschrieben zu sein.
Chinasaur
Ist Ihre Implementierung auf Speicherkohärenz abgestimmt? Ich kann mir vorstellen, dass der Versuch, jedem Thread einen größeren zusammenhängenden Block zu geben und sie in größeren Schritten übereinander springen zu lassen, reibungsloser funktioniert. Auf der GPU hingegen ist die vollwertige Version perfekt.
Chinasaur
6

Es gibt ein sehr schönes Tutorial-Übersichtspapier von Katzgrabber, Zufallszahlen im wissenschaftlichen Rechnen: Eine Einführung , auf das ich Leute hinweise, die PRNGs für wissenschaftliche Berechnungen verwenden möchten. Lineare kongruente Generatoren sind schnell, aber das ist ungefähr alles, was sie für sie tun müssen. Sie haben kurze Zeiträume und können sehr leicht schief gehen. Perfekt vernünftig aussehende Kombinationen von a, c und m können zu schrecklich korrelierten Ausgaben führen, selbst wenn Sie die üblichen Anforderungen zwischen a, c und m erfüllen.

Schlimmer noch, in einem häufigen Fall, in dem m eine Zweierpotenz ist (die Mod-Operation ist also schnell), haben die Bits niedrigerer Ordnung eine viel kürzere Periode als die gesamte Sequenz. Wenn Sie also rand ()% N ausführen, Sie haben eine noch kürzere Zeit als erwartet.

Als Faustregel gilt, dass Generatoren mit verzögertem Fibbonacci, MT und WELL viel bessere Eigenschaften haben und immer noch ziemlich schnell sind.

In Bezug auf das parallele Seeding ist die Methode von Jack Poulson gut, da sie eine genau definierte Folge von Zahlen ergibt, die gleichmäßig zwischen den Prozessoren aufgeteilt sind. Wenn das keine Rolle spielt, können Sie alles Vernünftige tun, um die verschiedenen PRNGs zu setzen. Das gleiche Papier schlägt vor, dass sich viele Leute unabhängig voneinander etwas ausgedacht haben und die PID- oder MPI-Aufgabennummer mit der Zeit hashen. Die dort vorgeschlagene Formel ist

long seedgen(void)  {
    long s, seed, pid;

    pid = getpid();
    s = time ( &seconds );

    seed = abs(((s*181)*((pid-83)*359))%104729); 
    return seed;
}

Ich habe keine besonderen Meinungen zu dieser spezifischen Implementierung, aber der allgemeine Ansatz ist sicherlich vernünftig.


quelle
Ich mag das Übersichtspapier, danke! Ich nehme an, ich sollte LCGs verteidigen, indem ich argumentiere, dass man jetzt einfach gute Werte für aus Wikipedia oder Knuths seminumerischen Algorithmen auswählen kann und dass das Beispiel in der Katzgrabber-Veröffentlichung etwas unfair ist, da es sich um eine LCG ohne a handelt Verschiebung ( ). (a,c,m)c=0
Jack Poulson
Es gibt diesen, aber selbst der mit a = 106, c = 1283, m = 6075 (Abb. 2) ist ein ganzer Haufen Fehler. Aber ja, es sind gute Dreiergruppen bekannt.
@JackPoulson: Ich fand es immer sehr frustrierend, a, c und m von meinem Kopf zu nehmen ... wenn ich es so mache, scheint es immer zu sehr kleinen Perioden zu führen. Danke für das Zitat! Ich werde Knuths seminumerische Algorithmen nachschlagen.
Paul
2

Eine einfache Idee zum Verteilen eines typischen sequentiellen RNG über eine anständige Anzahl von Threads besteht darin, dass ein einzelner Thread den Startwert so schnell wie möglich vorschiebt und nur etwa jeden tausendsten Startwert in den Speicher sendet. Lassen Sie dann jeden Ihrer anderen Threads einen dieser beabstandeten Referenz-Seeds aufnehmen und die 1000 Werte in diesem Block verarbeiten, dh die 1000 Seeds im Block erneut regenerieren, ihre pseudozufälligen Draws generieren und dann die andere Verarbeitung Ihrer Aufgabe ausführen.

Dies funktioniert, weil bei RNGs, die nicht allzu viel berechnen (LCG ist sicherlich eine, aber viele andere sollten in dieser Kategorie sein), der eigentliche Engpass darin besteht, die Seeds in den Speicher zu senden (und wahrscheinlich auch die anschließende Verarbeitung). Wenn Sie ein LCG ausführen, ohne etwas in den Speicher zu senden, sollte das Ganze in CPU-Registern bleiben und extrem schnell sein. Selbst für ein komplizierteres RNG sollten Sie im L1-Cache bleiben und sehr schnell sein.

Ich habe diesen sehr einfachen Ansatz mit einer LCG verwendet, die wir aus alten Gründen beibehalten müssen. Grundsätzlich erhalten wir eine lineare Beschleunigung bis zu 4-8 Threads in einer typischen Multicore-Workstation. Aber jetzt werde ich die Methode aus Jack Poulsons Antwort ausprobieren und hoffentlich noch schneller werden :).

OTOH, ich glaube, dieser einfache Trick sollte für andere inhärent sequentielle RNGs funktionieren.

Chinasaurier
quelle
2

Diese Antwort kommt zu spät, aber Sie sollten sich SPRNG ansehen . Es wurde speziell für die parallele Skalierbarkeit entwickelt und unterstützt eine Handvoll Arten von PRNGs.

Bill Barth
quelle