Parallele Berechnungen mit schneller Zufälligkeit und Reinheit?

Question

Mein Ziel ist es, eine Berechnung mit parMap aus der parallel package zu parallelisieren, aber ich möchte auch ein bisschen Zufälligkeit meiner Sampling-Funktion hinzufügen.

Ohne die Zufälligkeit meine Berechnung ist einfach einige Zahlen knirschen und so ist es rein und ich könnte parMap verwenden. Um gute Ergebnisse zu erzielen, muss ich bei jedem Schritt mehrere Proben nehmen und die Ergebnisse mitteln. Die Stichprobe muss randomisiert werden.

Eine Lösung könnte sein, die random package zu verwenden, randoms anrufen und dann diese Liste während der Berechnung zu konsumieren (indem Sie die reine faule Liste an die Berechnung übergeben, würde ich sie rein halten). Leider ist das ein sehr langsamer Zufallszahlengenerator und ich brauche viele Zufallszahlen, also würde ich lieber mwc-random oder mersenne-random verwenden (obwohl ich denke, mersenne-random wird immer noch beibehalten).

Ist es sicher, etwas wie unsafePerformIO mit mwc-random zu verwenden, um eine Funktion wie randoms zu schreiben? Etwas wie folgt aus:

randomsMWC :: Variate a => GenST s -> [a] 
randomsMWC g = unsafePerformIO $ unsafeSTToIO $ randomsMWC' g 
    where 
    randomsMWC' g = do 
    a <- uniform g 
    as <- unsafeInterleaveST $ randomsMWC' g 
    return (a : as) 

Muss ich stattdessen für eine parallel number generator erreichen? Oder muss ich in den sauren Apfel beißen und zugeben, dass mein Algorithmus einfach nicht rein ist, ohne das langsame Zufallspaket zu verwenden?

Vorschläge? Vielen Dank!

Answer 1

Wenn ein Single-Threaded-Zufallsquelle aufweist, ist kein Problem für die Leistung, können Sie eine reine Wrapper um mwc Zufalls erhalten

import Control.Monad.ST.Lazy 
import Control.Monad 
import System.Random.MWC 

rList :: Variate a => Seed -> [a] 
rList s = runST $ do 
    g <- strictToLazyST $ restore s 
    advance g 

advance :: Variate a => Gen s -> ST s [a] 
advance g = do 
    x <- strictToLazyST $ uniform g 
    xs <- x `seq` advance g 
    return (x:xs) 

hier rList einen Samen nimmt, und erzeugt dann gemächlich ein unendlicher Strom von faulen Zahlen deterministisch. Ich bin mir nicht sicher, ob wirklich sicher ist, aber niemand scheint dagegen zu sein. Ich habe kein Benchmarking durchgeführt, aber ich vermute, dass dies ziemlich schnell ist. Ich nehme an, dass mwc-random threadsicher ist, da der explit-Datenfluss mit dem Generator codiert ist und dass er in der ST Monade verwendet werden kann. Jemanden einladen, den obigen Hack zu benutzen. Ich glaube nicht, das seq notwendig ist, aber es macht mich weniger suspicous von strictToLazyST, dass ich weiß, dass ich determinis Auswerteauftrag haben (und es ist immer noch faul genug zu arbeiten).

Sie benötigen immer noch Zufall (das ist IO) irgendwo, um eine echte zufällige Saat zu erzeugen, aber dies sollte Sie lassen den größten Teil des Codes rein, und lassen Sie den Seed in Datei speichern oder bei Bedarf wiederverwenden.

GHCi:

λ: gen <- create 
λ: x <- save gen 
λ: drop 1 $ take 10 $ rList x :: [Int] 
[4443157817804305558,-6283633474236987377,3602072957429409483, 
-5035101780705339502,-925260411398682800,423158235494603307, 
-6981326876987356147,490540715145304360,-8184987036354194323] 

Answer 2

Meine Vermutung ist, dass mersenne Zufalls nicht sicher ist, fädeln, so jede unsafe... und parallelisiert wird bereitet Sie zu Problemen führen, damit von mehreren Threads aufgerufen wird. (. Siehe auch GHC manual Abschnitt 8.2.4.1)

Funktionen, die Zufälligkeit brauchen, sind nicht rein, sie brauchen eine gewisse Zufallsquelle, die entweder extern ist (hardware - wie ein Gerät Sampling-Rauschen) und damit gebunden IO, oder Pseudozufall, der während der Berechnung einen gewissen Zustand beibehalten muss. So oder so können sie nicht reine Haskell-Funktionen sein.

würde ich mit Trennung Ihre Anforderungen an einen bestimmten Monade Typklasse starten, zum Beispiel so etwas wie

class Monad m => MonadParRand m where 
    random  :: MTRandom a => m a 
    parSequence :: [m a] -> m [a] 

, die Sie Ihren Hauptcode ermöglicht es zu schreiben, ohne an eine bestimmte Implementierung gebunden zu sein. Oder wenn Sie fett fühlen könnten Sie monad-parallel verwenden und definieren so etwas wie

class MonadParallel m => MonadParRand m where 
    random  :: MTRandom a => m a 

Jetzt kommt der schwierige Teil ist, wie beide zu definieren random und parSequence (oder MonadParallel ‚s bindM2) und es schnell zu machen. Da Sie die Kontrolle über bindM2 haben, können Sie verwalten, wie Threads erzeugt werden und welchen Status sie behalten. So können Sie einen Puffer an jeden Thread binden, aus dem er zufällige Zahlen zieht. Wenn der Puffer leer ist, macht er synchronisierte Aufrufe an Mersenne-Random (oder einen anderen IO -basierten Nummerngenerator), füllt den Puffer und fährt fort.

(Wenn Sie so etwas implementieren, wäre es sehr nett, daraus eine eigenständige Bibliothek zu machen.

)

---

Beachten Sie, dass randoms von mersenne Zufall verwendet bereits unsafeInterleaveIO einen faulen Liste zu produzieren, aber ich würde sagen, die Liste gemeint ist, nur aus einem einzigen Faden verbraucht werden. Und es gibt auch Raum für Verbesserungen. Es verwendet unsafeInterleaveIO und es einigen Aufwand hat, wie erwähnt in its comment:

Es gibt hier echt Gemeinkosten. Betrachten Sie eifrig füllen Stücke und extrahieren Elemente stückweise.

Answer 3

Ich habe ein nicht ganz releasefähig Paket hsrandom123 auf Github, die hier hilfreich sein könnte. Ich habe mit der Implementierung dieses Pakets begonnen, um einen geeigneten RNG für parallele Berechnungen zur Verfügung zu haben. Es stellt die Philox- und Threefry-Zufallszahlengeneratoren von the random123 C library wieder her (es gibt auch ein Papier, in dem die Ideen beschrieben werden).

Es gibt einen Grund, warum meine Bibliothek nicht freigegeben ist: Während die tatsächliche RNG-Implementierung durchgeführt wird und die gleichen Ergebnisse wie die C-Version zu produzieren scheint, war ich noch unentschlossen, welche Haskell-Schnittstelle zu verwenden ist und die Bibliothek kaum dokumentiert ist . Fühlen Sie sich frei, mich zu kontaktieren, wenn Sie mehr Informationen benötigen oder helfen, es zu benutzen.

Answer 4

Für Vollständigkeit der Antworten, lassen Sie mich erklären, was ich im Moment mache dieses Problem zu lösen.

Anstatt zu versuchen, die Berechnung rein zu machen, habe ich mich dafür entschieden, das async-Paket statt parallel zu verwenden.

Wenn ich entscheiden, meine aktuelle Lösung zu revidieren, rein zu sein, werde ich versuchen, zuerst die Lösung von Philip JF vorgeschlagen, so habe ich seine Antwort als Sicherheiten akzeptiert, gekennzeichnet.

Meine nächste Herausforderung ist, herauszufinden, wie eine optimale Chunking der Arbeit anzunähern, so dass threading es dauern, machen die Zeit, reduziert stattdessen mehr :)