Zufallszahlengenerator für Fortran und OpenMP

[Reaping_Ant]

Ich arbeite schon seit längerem mit einem selbstgeschriebenen Fortran Programm zur Simulation von stochastischen Prozessen (Langevin Dynamik bzw. Continuous Time Random Walk). Kurz gesagt, berechne ich eine große Anzahl von Realisierungen (Trajektorien) eines Zufallsprozesses um anschließend deren Statistik auszuwerten.
Den Teil des Programms, der die Trajektorien berechnet und deren Statistik auswertet, habe ich mittlerweile erfolgreich parallelisiert und dieser skaliert auch sehr gut. Allerdings ist der Fortran-eigene Zufallszahlengenerator nicht für parallele Berechung von Zufallszahlen geeignet, was mich zu meiner Frage bringt:
Kennt jemand einen guten und einfach zu implementierenden parallelen Zufallszahlengenerator für Fortran? Klar kann man sowas auch selbst schreiben, allerdings ist das Programm für mich mehr Mittel zum Zweck, deshalb wollte ich nicht übermäßig viel Arbeit in den Zufallszahlengenerator investieren.

[Trap]

Von der Wikipedia-Seite zu Mersenne Twister:
http://theo.phys.sci.hiroshima-u.ac.jp/~ishikawa/PRNG/mt_stream_en.html

Hab von Fortran keine Ahnung, aber das sieht ganz brauchbar aus...

[Reaping_Ant]

Danke für den Link, werde ich mir ansehen.

[RLZ]

Falls du an die Intel Math Kernel Library ran kommst, hast du genügend Zufallsgeneratoren. ;)

[Gnafoo]

Entweder du packst einen Mutex um die RNG-Aufrufe. Dadurch wirds aber wieder zu einem gewissen Grad sequentiell. Ob das etwas ausmacht hängt von deiner Benutzung ab. Oder du sorgst irgendwie dafür, dass der RNG in jedem Thread einen anderen Zustand benutzt, so dass die sich nicht in die Quere kommen (wobei man die dann so seeden sollte, dass sie nicht dieselbe Folge generieren).

Das mit dem Zustand ist natürlich effizienter, aber ich weiß nicht ob der RNG in Fortran so etwas kann. Manchmal gibt es in der API auch RNG-Funktionen mit einem expliziten State-Parameter. Wenn man keine zu hohen Ansprüche an die Zufallszahlen hat, ist das aber auch trivial selbst zu implementieren. Die rand()-Funktionen der meisten Programmiersprachen machen einfach einen linearen Kongruenzgenerator. Wikipedia hat sogar eine Tabelle mit den Parametern:

http://en.wikipedia.org/wiki/Linear_congruential_generator

Wenn es gute Zufallszahlen sein sollen, dann kannst du den von Trap genannten Mersenne Twister nehmen.

[Gast]

Es erscheint mir als Nichtprogrammierer zu trivial für einen neuen Thread, zum RNG und Co. hätte ich aber eine allgemeinere Frage. Die habe ich schon irgendwo mal im Netz gesehen, aber keine verwendbaren Antworten vernommen. Ich bin mir nicht sicher ob das sogar hier war.

Ich hoffe Reaping_Ant stört das nicht gewaltig. Bzw. geht es dabei eigentlich um die Qualität des RNG. Folgendes:

Zwar meist, aber auch nicht ausschliesslich, ist der GCC für seine Funktionen herausoptimierenden Flags bekannt. Dafür gibt es in regelmässigen Abständen shitstorm auf den mailinglists.

Wenn man jetzt ein Gebilde schreibt um zb. eben das R im RNG weniger pseudo zu machen :) besteht die Möglichkeit, daß der Optimizer/Compiler einiges davon weghaut? Was eine Verschlechterung des RNG bedeutet? Grade beim RNG ist eine Analyse ohnehin sehr schwierig.

Ist hier jemand in security tätig oder muß sich damit teilweise beschäftigen?
Oder gibt es eine Arbeit eines Sicherheitsforschers darüber?
Eine ganz praktische Liste mit Flags die man bei Crypto/RNG eher vermeiden sollte?

[Gnafoo]

Compiler-Optimierungen dürfen das beobachtbare Verhalten eines Programms (mit ganz wenigen Ausnahmen, z.B. beim Copy-Konstruktor) nicht verändern. Insofern sollte es auch kein Problem sein, entsprechende Optimierungen anzuschalten. Das „Problem“, wegen dem GCC mitunter kritisiert wurde tritt erst dann auf, wenn der Code undefiniertes Verhalten auslöst. An der Stelle hat der Compiler gewisse Freiheiten, die GCC z.B. mitunter zum Optimieren verwendet.

Ein kleines Beispiel: beim vorzeichenlosen Integer ist durch den Standard klar definiert, was beim Überlauf passiert. Wenn man auf den größten Integer 1 addiert, dann kommt man wieder bei 0 an. Sprich (UINT_MAX + 1) == 0. Viele gehen davon aus, dass beim vorzeichenbehafteten Integer etwas ähnliches passiert, sprich (INT_MAX + 1) == INT_MIN. Das ist allerdings nicht der Fall. Tatsächlich ist das Ergebnis laut Standard undefiniert.

Der Compiler darf so etwas zum Optimieren verwenden, z.B. indem er folgende if-Verzweigung komplett entfernt:


int a = INT_MAX;
if ((a + 1) < 0)
{
// ...
}


Und zwar deshalb, weil er davon ausgehen darf, dass das Ergebnis von (INT_MAX + 1) irgendetwas beliebiges ist. Beispielsweise 5 oder 17 oder 832794. Der Standard macht keine Aussage über das Ergebnis, also darf sich der Compiler auch ein Ergebnis aussuchen, bei dem er möglichst viel optimieren kann. Das hat beim GCC für ein paar Beschwerden gesorgt, liegt aber vollständig im Rahmen dessen, was der Compiler machen darf. Wer Code schreibt, dessen Verhalten laut Standard nicht definiert ist, darf sich auch nicht beschweren, wenn das Ergebnis von seiner Erwartung abweicht.

Kurz und bündig: wer Standardkonformen Code schreibt, der kann auch die Optimierungen hochdrehen, wie er möchte. Solange der Compiler keinen Fehler hat, darf sich das zu beobachtende Verhalten dadurch nicht ändern (abgesehen natürlich von der Geschwindigkeit). Auch ein RNG ist immer noch ein deterministisches Programm und wenn derselbe Seed plötzlich zu einem anderen Ergebnis führt, weil man an den Optimierungen gedreht hat, dann ist mit ziemlicher Sicherheit irgendwo ein Fehler im Programm und nicht im Compiler.

[Gast]

Das ist wie im richtigen Leben. Es gibt Gesetze und es gibt Benimmregeln. Die Benimmregeln entstehen in der Mehrheit des sozialen Umfelds.

Das vermeintliche Problem mit GCC ist, daß einige seiner Entwickler sehr um die Gesetze bedacht sind, sich aber selten etwas aus Benimmregeln machen, die Programmierer außerhalb des GGC-Projektes pflegen und an die sich vielerorts auch Intel und Microsoft halten.

fefe ist mein Lieblingsautor ;) wenn es um den GCC geht :) Er halt die Maintainer zum einen gehörigen Teil für Kleinkinder bei sowas. Meine Erfarhung ist eher, daß sie wie Judge Dredd sind, den aber alles andere garnicht interessiert.

Hier nur ein paar Perlen
http://blog.fefe.de/?ts=bb5517a4
http://blog.fefe.de/?ts=b1ca91a1
http://blog.fefe.de/?ts=afaeba76


Was jetzt das etwaige Problem mit RNGs oder allgemien security soft nicht klärt. Die Frage fand ich nicht so schlecht.

Bei dem O-Ton von Gnafoo, wenn Programmierer alles perfekt machen, passiert nichts, fehlt mir komplett ein Realitätsabgleich. Wenn dann nicht nur auf die eigene Soft sondern noch auf die teils sehr eigenwilligen Benimmregel des Optimizer-teils aufpassen muß, welche auch nicht klar beschrieben werden und oft nur mit dem Gemüt des jeweiligen maintainers einhergehen, dann ist das ein Zustand und darf als mangelhaft bezeichnet werden.

Ich sehe auf dem security sector keine Programmierer die mit nach der 1.0 mit weiteren Versionen nur noch Features und keine Fixes einreichen. Dasmit gibt es auch auf diesem Gebiet KEINE Kapazität die fehlerfrei arbeitet.

Man sollte sich daher ähnlich Intel bemühen Benimmregeln zu folgen welche grad diesen Leuten ihre Arbeit einfacher und nicht schwerer machen. Statt sich alleine auf seine Judge Dredd Unqualitäten zu konzentrieren.

[Timbaloo]

Ich stimme zu, dass die gcc-ler sich hier kindisch verhalten. Aber gerade beim Beispiel von gnafoo sieht man auch, dass die Mit-"Schuld" auch am C-Standard liegt, der einfach aus historischen Gründen zuviele Dinge "undefined" oder "implementation defined" lässt. Da hat man bei C99 und C11 total verpasst mal aufzuräumen. Naja, gets() hat man ja in C11 rausgeschmissen...... :rolleyes:

[Gnafoo]

Naja laut Standard ist es klipp und klar ein Fehler. Sagen wir mal GCC würde schön drumrum arbeiten, indem er -fwrapv standardmäßig aktiviert. Mal abgesehen davon, dass man weniger optimieren kann, freut sich der Entwickler, dass die Bibliothek so wunderbar funktioniert. Nur eines schönen Tages möchte man auf Embedded-System XY portieren und dort ist es tatsächlich so, dass der signed Overflow keinen wrap-around macht. Dann fliegt einem plötzlich alles um die Ohren.

Gut das mag jetzt etwas konstruiert klingen, aber prinzipiell bin ich kein Fan von Lösungen, die versuchen die Intention des Entwicklers zu erraten und dabei um den eigentlichen Fehler herum arbeiten. Natürlich ist niemand perfekt, aber das ist meiner Meinung nach der falsche Ansatz, um damit umzugehen. Wenn wirklich so eindeutig und klar ist, was passieren sollte, dann ist das tatsächliche Problem, das es nicht im Standard steht. Den Fehler beim Compiler zu suchen ist imho auch nicht richtig.

Eines muss man sich dabei aber auch immer klar machen: C/C++ ist extrem portabel und läuft auf jeder Menge Plattformen. Nicht alles, was bei einem „normalen“ Rechner selbstverständlich ist, trifft auch auf den Mikrochip irgendwo im Auto zu. Wenn man aber eine Bibliothek schreiben möchte, die auf beiden Plattformen läuft, dann kann man sich einfach nicht auf „Benimmregeln“ verlassen, sondern nur auf den Standard. Und der ist wenigstens eindeutig definiert. Falls man auf Portabilität verzichten möchte, dann darf man das natürlich gerne machen, aber das heißt dann unter Umständen auch, dass man dies dem Compiler explizit mitteilen muss, beispielsweise mit -fwrapv.

Ansonsten noch einmal kurz zu den Optimierungen: es gibt da ja durchaus auch sinnvolle Szenarien bei denen aus dem undefinierten Überlauf ein wirklicher Nutzen gezogen werden kann und nicht nur konstruierte Beispiele, in denen auf den ersten Blick klar ist, dass da ein Fehler vorliegt. Beispielsweise:


int a = ...;
for (int i = a; i < (a + 10); i++)
{
// ...
}


Wenn der Compiler sich nicht um den Überlauf scheren muss, dann kann er die Schleife „unrollen“, weil sie immer 10x ausgeführt wird. Falls der Überlauf aber eine Rolle spielt, dann kann „a < (a+10)“ auch vorher schon falsch sein und der Compiler muss wirklich eine Schleife generieren, die unter Umständen (sprich: im Hotpath) deutlich teurer sein kann. Ich halte so eine Optimierung durchaus für legitim. Die Alternative brächte sowieso nur ein trügerisches Gefühl der Sicherheit für den Programmierer (das er beim nächsten Compiler gleich wieder verlieren kann).

[Timbaloo]

Eines muss man sich dabei aber auch immer klar machen: C/C++ ist extrem portabel und läuft auf jeder Menge Plattformen. Nicht alles, was bei einem „normalen“ Rechner selbstverständlich ist, trifft auch auf den Mikrochip irgendwo im Auto zu. Wenn man aber eine Bibliothek schreiben möchte, die auf beiden Plattformen läuft, dann kann man sich einfach nicht auf „Benimmregeln“ verlassen, sondern nur auf den Standard. Und der ist wenigstens eindeutig definiert.
Wie ich schon sagte, die Altlasten im Standard sind ein Problem. Ich kenne durchaus ein paar µC/Plattformen die vom "Standard" x86 abweichen. Z.B. welche wo ein Byte != 8Bit (z.B. 16). Aber ich kenne halt einfach keine (einigermassen aktuelle) Plattform die nicht auf Zweierkomplement für signed setzt, und das ist hier ja genau das Problem. Sowas hätte man vor längerer Zeit rausschmeissen sollen. Aber wenn man halt versucht in einem Standard halt jeden Exoten zu erlauben, dann kommt halt auch Müll bei raus.

[Gast]

Gnafoo Standards sind nicht des Pudels Kern.

Davon ab ist das was du meinst nicht das was die ggc-maintainer selbst machen. Wenn ich O1 fahre backt der Compiler exakt so wie ich es will, mit Os und O2 pöllt er mir die Konstrukte weg? Was sind das für Lösungen?

Wenn ich Compiler baue gibt es Sachen die ich erfüllen muß und welche die ich erfüllen könnte. Meint man bei dem "könnte" einen Versuch festzustellen was nicht schädlich aber sinnvoll sein könnte, stellt man bei der GCC Truppe ein Totalversagen fest.

[Gast]

Man soll diesem Mist aber auch nur die nötige Beachtung schenken. Laut meinen eigenen Tests mit Win7, gcc 4.7.2 und GnuPG 1.4.14 auf der corei7 Architektur ist man mit
-O2 -march=core2 -mtune=core2
ist genauso schnell oder bis zu 3% schneller als
-O3 -ftracer -march=corei7 -mtune=corei7 -fivopts -ftree-loop-distribution -minline-all-stringops -funroll-loops -maccumulate-outgoing-args

Was soll dieser Mist also wenn man keine maschinenspezifische Raytracer baut oder überhaupt kein Vektoring benötigt?

Man sieht sich hier wohl einem verzweifelten Geschwindigkeitswettbewerb gegen den ICC ausgesetzt. Und der ist meist eine halbe bis eine ganze Klasse schneller. Hat aber trotzdem eine größere Kodesicherheit als GCC. Der haut auch nicht alle aserts weg die er findet.

Das GCC-Team meint wohl, wenn sie aus einem nicht 100% rechtwinkligen Kode alles raushauen oder umkrempeln könne was dem Standard nicht entspricht, holen sie etwas auf.
Programmiere gut oder schlecht, wir machen alles gleich schnell Bullshit.

Ich gebe zu die Optimizer sind gelegentlich sehr aufregend, irgendwie aber auch die Pest. Die asm-ahnugnslose Generation blickt überhaupt nicht durch was mit ihrem Kode überhaupt passiert.

Optimierungen. Besagter fefe brachte auch mal einen Blog in dem er fand, Linux braucht viele Virenscaner :D Er hat einen Windowsclient auditiert und erstmal alle Schlangenöle für diese Sitzung gekillt. Er war erstaunt wie schnell und auch wieviel agiler das System im Vergleich zu einer vergleichbaren Linuxmaschine agierte.
Und befand mit Schlangenölen muß sich das ganze Biotop mehr bei den Optimierungen anstrengen, damit das System im Ganzen rennt. Wenn man die dann weglässt: Rakete. Interessante Idee ;)

Mir scheint die GCC-Leute sehen sich vielen durchschnittlichen Anwendern gegenüber und meinen aus jedem hello world eine Perle machen zu müßen und leider auch zu können. Das können sie aber nicht und das sollte auch nicht der Anspruch sein.

Bei der Kodesicherheit, also der Verlgeich zwischen dem Kompilat und den Funktionen die man im Editor eingetippt hat, ist GCC gefühlt doppelt so agressiv wie ICC. Und langsamer.

Vielleicht sollte der Schwerpunkt endlich wieder der sein, zu gucken, wie man sich das zurechtlegt was man durchlässt und nicht was man alles weghauen und umkrempeln kann.

Es kann nicht Sinn der Sache sein, daß die größte Aufgabe des Optimizers ist den Kode quasi umzuschreiben. Wenn ich schlecht programmiere will ich schlechten Kode sehen. Oder einen Haufen Warnungen spätestens beim Make. Sonst kann ich nichts lernen und wenn ich lerne kann ich meinen Kode mit Sicherheit besser optimieren als ein gedankenloses Stück Software.

Die Kodesicherheit, also wieviel davon was ich eingetippt habe landet so im Kompilat, ist beim GCC langsam nicht mehr akzeptabel. Wenn ich mal außerhalb des Standards bin, soll eine scheiß Software dabei rauskommen und nicht irgendetwas, weil GCC meint es ist nicht standardisiert und damit kann man damit das machen was dem Maintainer grad so in den Sinn kam.

Sie sind wie Teenies. Das beschreibt es schon ziemlich genau.

[Reaping_Ant]

Auch wenn der Thread zuletzt etwas OT ging, möchte ich mich doch noch einmal melden und bei allen für die Antworten bedanken. Besonderer Dank geht an Trap.
Nachdem ich in letzter Zeit nicht dazu kam, habe ich es heute nach einigem Herumprobieren geschafft, die multi-stream Version des Mersenne Twisters in mein Programm einzubinden. Das Ganze kompiliert mittlerweile sogar unter Windows und funktioniert tadellos.

Das Ergebnis der Mühen kann sich sehen lassen: Ein einfacher Test-Datensatz dauerte mit meiner bisherigen Methode (zuerst singlethreaded Zufallszahlen generieren und dann multithreaded Trajektorien berechnen) 13 Minuten, mit dem Mersenne Twister jetzt nur noch 3 (beides unter Nutzung von 10 Threads auf einem Gulftown).