Paralleles mapM auf Repa-Arrays

90

In meiner jüngsten Arbeit mit Gibbs samplinghabe ich das sehr gut genutzt, RVarwas meiner Ansicht nach eine nahezu ideale Schnittstelle zur Erzeugung von Zufallszahlen bietet. Leider konnte ich Repa nicht verwenden, da ich keine monadischen Aktionen in Karten verwenden konnte.

Während eindeutig monadische Karten im Allgemeinen nicht parallelisiert werden können, scheint es mir RVarmindestens ein Beispiel für eine Monade zu sein, bei der Effekte sicher parallelisiert werden können (zumindest im Prinzip; ich bin mit dem Innenleben von nicht besonders vertraut RVar). . Ich möchte nämlich so etwas wie das Folgende schreiben:

drawClass :: Sample -> RVar Class
drawClass = ...

drawClasses :: Array U DIM1 Sample -> RVar (Array U DIM1 Class)
drawClasses samples = A.mapM drawClass samples

wo A.mapMwürde so etwas aussehen,

mapM :: ParallelMonad m => (a -> m b) -> Array r sh a -> m (Array r sh b)

Während dies eindeutig entscheidend von der Implementierung RVarund dem zugrunde liegenden Thema abhängt RandomSource, würde man im Prinzip denken, dass dies das Zeichnen eines neuen zufälligen Startwerts für jeden erzeugten Thread und das übliche Vorgehen beinhalten würde.

Intuitiv scheint es, dass dieselbe Idee auf einige andere Monaden verallgemeinert werden könnte.

Meine Frage lautet also: Könnte man eine Klasse ParallelMonadvon Monaden konstruieren, für die Effekte sicher parallelisiert werden können (vermutlich zumindest von bewohnt RVar)?

Wie könnte es aussehen? Welche anderen Monaden könnten diese Klasse bewohnen? Haben andere über die Möglichkeit nachgedacht, wie dies in Repa funktionieren könnte?

Wenn diese Vorstellung von parallelen monadischen Aktionen nicht verallgemeinert werden kann, sieht jemand eine gute Möglichkeit, diese Arbeit im speziellen Fall von RVar(wo es sehr nützlich wäre) zu machen? RVarParallelität aufzugeben ist ein sehr schwieriger Kompromiss.

Bgamari
quelle
1
Ich denke, der Knackpunkt ist "Zeichnen eines neuen zufälligen Seeds für jeden erzeugten Thread" - wie sollte dieser Schritt funktionieren und wie sollten die Seeds wieder zusammengeführt werden, sobald alle Threads zurückkehren?
Daniel Wagner
1
Die RVar-Schnittstelle würde mit ziemlicher Sicherheit einige Ergänzungen benötigen, um das Laichen eines neuen Generators mit einem bestimmten Startwert zu ermöglichen. Zugegeben, es ist unklar, wie die Mechanik dieser Arbeit funktioniert, und es scheint ziemlich RandomSourcespezifisch zu sein. Mein naiver Versuch, einen Samen zu zeichnen, wäre, etwas Einfaches und wahrscheinlich sehr Falsches zu tun, wie einen Vektor von Elementen (im Fall von mwc-random) zu zeichnen und 1 zu jedem Element zu addieren, um einen Samen für den ersten Arbeiter zu erzeugen, 2 für den zweiten Arbeiter usw. absolut unzureichend, wenn Sie eine Entropie von kryptografischer Qualität benötigen; hoffentlich gut, wenn Sie nur einen zufälligen Spaziergang brauchen.
Bgamari
3
Ich bin auf diese Frage gestoßen, als ich versucht habe, ein ähnliches Problem zu lösen. Ich verwende MonadRandom und System.Random für monadische Zufallsberechnungen parallel. Dies ist nur mit der splitFunktion von System.Random möglich . Es hat den Nachteil, dass es unterschiedliche Ergebnisse splitliefert (aufgrund der Art von, aber es funktioniert. Ich versuche jedoch, dies auf Repa-Arrays auszudehnen und habe nicht viel Glück. Haben Sie damit Fortschritte gemacht oder ist es tot? Ende?
Tom Savage
1
Monade ohne Sequenzierung und Abhängigkeiten zwischen Berechnungen klingt für mich eher zutreffend.
John Tyree
1
Ich zögere. Wie Tom Savage bemerkt, splitbietet dies eine notwendige Grundlage, aber beachten Sie den Kommentar zur Quelle für die splitImplementierung: "- keine statistische Grundlage dafür!". Ich neige dazu zu glauben, dass jede Methode zur Aufteilung eines PRNG eine ausnutzbare Korrelation zwischen seinen Zweigen hinterlässt, aber nicht über den statistischen Hintergrund verfügt, um dies zu beweisen. Im Hinblick auf die allgemeine Frage, ich bin nicht sicher , dass
isturdy

Antworten:

7

Es ist 7 Jahre her, seit diese Frage gestellt wurde, und es scheint immer noch, als hätte niemand eine gute Lösung für dieses Problem gefunden. Repa hat keine mapM/ traverselike-Funktion, auch keine , die ohne Parallelisierung ausgeführt werden könnte. Angesichts der Fortschritte, die in den letzten Jahren erzielt wurden, ist es außerdem unwahrscheinlich, dass dies auch passieren wird.

Aufgrund des veralteten Zustands vieler Array-Bibliotheken in Haskell und meiner allgemeinen Unzufriedenheit mit ihren Funktionssätzen habe ich einige Jahre Arbeit in eine Array-Bibliothek gesteckt massiv, die einige Konzepte von Repa entlehnt, sie jedoch auf eine völlig andere Ebene bringt. Genug mit dem Intro.

Vor dem heutigen Tag gab es drei monadische kartenähnliche Funktionen in massiv(ohne das synonym ähnliche Funktionen : imapM, forMet al.):

  • mapM- die übliche Zuordnung in einer beliebigen Monad. Aus offensichtlichen Gründen nicht parallelisierbar und auch etwas langsam (wie üblich mapMüber eine Liste langsam)
  • traversePrim- hier beschränken wir uns auf PrimMonad, was deutlich schneller ist als mapM, aber der Grund dafür ist für diese Diskussion nicht wichtig.
  • mapIO- Dieser ist, wie der Name schon sagt, beschränkt auf IO(oder besser gesagt MonadUnliftIO, aber das ist irrelevant). Da wir uns in befinden IO, können wir das Array automatisch in so viele Blöcke aufteilen, wie Kerne vorhanden sind, und separate Arbeitsthreads verwenden, um die IOAktion über jedes Element in diesen Blöcken abzubilden . Im Gegensatz zu pure fmap, das auch parallelisierbar ist, müssen wir IOwegen des Nichtdeterminismus der Zeitplanung in Kombination mit den Nebenwirkungen unserer Mapping-Aktion hier sein.

Nachdem ich diese Frage gelesen hatte, dachte ich mir, dass das Problem praktisch gelöst ist massiv, aber nicht so schnell. Zufallszahlengeneratoren wie in mwc-randomund andere in random-fukönnen nicht denselben Generator für viele Threads verwenden. Das heißt, das einzige Teil des Puzzles, das mir fehlte, war: "Zeichnen eines neuen zufälligen Samens für jeden erzeugten Faden und Fortfahren wie gewohnt". Mit anderen Worten, ich brauchte zwei Dinge:

  • Eine Funktion, die so viele Generatoren initialisiert, wie es Arbeitsthreads geben wird
  • und eine Abstraktion, die der Zuordnungsfunktion nahtlos den richtigen Generator gibt, abhängig davon, in welchem ​​Thread die Aktion ausgeführt wird.

Genau das habe ich getan.

Zuerst werde ich Beispiele geben, die die speziell gestalteten randomArrayWSund initWorkerStatesFunktionen verwenden, da sie für die Frage relevanter sind, und später zur allgemeineren monadischen Karte übergehen. Hier sind ihre Typensignaturen:

randomArrayWS ::
     (Mutable r ix e, MonadUnliftIO m, PrimMonad m)
  => WorkerStates g -- ^ Use `initWorkerStates` to initialize you per thread generators
  -> Sz ix -- ^ Resulting size of the array
  -> (g -> m e) -- ^ Generate the value using the per thread generator.
  -> m (Array r ix e)
initWorkerStates :: MonadIO m => Comp -> (WorkerId -> m s) -> m (WorkerStates s)

Für diejenigen, die nicht vertraut sind massiv, ist das CompArgument eine zu verwendende Berechnungsstrategie. Bemerkenswerte Konstruktoren sind:

  • Seq - Führen Sie die Berechnung nacheinander aus, ohne Threads zu verzweigen
  • Par - Drehen Sie so viele Threads wie möglich und verwenden Sie diese, um die Arbeit zu erledigen.

Ich werde zunächst das mwc-randomPaket als Beispiel verwenden und später zu RVarT:

λ> import Data.Massiv.Array
λ> import System.Random.MWC (createSystemRandom, uniformR)
λ> import System.Random.MWC.Distributions (standard)
λ> gens <- initWorkerStates Par (\_ -> createSystemRandom)

Oben haben wir einen separaten Generator pro Thread mithilfe der Systemzufälligkeit initialisiert, aber wir hätten genauso gut einen eindeutigen Startwert pro Thread verwenden können, indem wir ihn aus dem WorkerIdArgument abgeleitet haben, das lediglich ein IntIndex des Workers ist. Und jetzt können wir diese Generatoren verwenden, um ein Array mit zufälligen Werten zu erstellen:

λ> randomArrayWS gens (Sz2 2 3) standard :: IO (Array P Ix2 Double)
Array P Par (Sz (2 :. 3))
  [ [ -0.9066144845415213, 0.5264323240310042, -1.320943607597422 ]
  , [ -0.6837929005619592, -0.3041255565826211, 6.53353089112833e-2 ]
  ]

Durch die Verwendung der ParStrategie schedulerteilt die Bibliothek die Generierungsarbeit gleichmäßig auf die verfügbaren Mitarbeiter auf, und jeder Mitarbeiter verwendet seinen eigenen Generator, wodurch der Thread sicher wird. Nichts hindert uns daran, dieselbe WorkerStateswillkürliche Anzahl von Malen wiederzuverwenden, solange dies nicht gleichzeitig erfolgt, was sonst zu einer Ausnahme führen würde:

λ> randomArrayWS gens (Sz1 10) (uniformR (0, 9)) :: IO (Array P Ix1 Int)
Array P Par (Sz1 10)
  [ 3, 6, 1, 2, 1, 7, 6, 0, 8, 8 ]

Wenn mwc-randomwir nun zur Seite stellen, können wir dasselbe Konzept für andere mögliche Anwendungsfälle wiederverwenden, indem wir Funktionen wie generateArrayWS:

generateArrayWS ::
     (Mutable r ix e, MonadUnliftIO m, PrimMonad m)
  => WorkerStates s
  -> Sz ix --  ^ size of new array
  -> (ix -> s -> m e) -- ^ element generating action
  -> m (Array r ix e)

und mapWS:

mapWS ::
     (Source r' ix a, Mutable r ix b, MonadUnliftIO m, PrimMonad m)
  => WorkerStates s
  -> (a -> s -> m b) -- ^ Mapping action
  -> Array r' ix a -- ^ Source array
  -> m (Array r ix b)

Hier ist das versprochene Beispiel dafür, wie diese Funktion nutzen mit rvar, random-fuund mersenne-random-pure64Bibliotheken. Wir hätten es auch randomArrayWShier verwenden können , aber zum Beispiel nehmen wir an, wir haben bereits ein Array mit verschiedenen RVarTs. In diesem Fall benötigen wir ein mapWS:

λ> import Data.Massiv.Array
λ> import Control.Scheduler (WorkerId(..), initWorkerStates)
λ> import Data.IORef
λ> import System.Random.Mersenne.Pure64 as MT
λ> import Data.RVar as RVar
λ> import Data.Random as Fu
λ> rvarArray = makeArrayR D Par (Sz2 3 9) (\ (i :. j) -> Fu.uniformT i j)
λ> mtState <- initWorkerStates Par (newIORef . MT.pureMT . fromIntegral . getWorkerId)
λ> mapWS mtState RVar.runRVarT rvarArray :: IO (Array P Ix2 Int)
Array P Par (Sz (3 :. 9))
  [ [ 0, 1, 2, 2, 2, 4, 5, 0, 3 ]
  , [ 1, 1, 1, 2, 3, 2, 6, 6, 2 ]
  , [ 0, 1, 2, 3, 4, 4, 6, 7, 7 ]
  ]

Es ist wichtig zu beachten, dass wir uns trotz der Tatsache, dass im obigen Beispiel die reine Implementierung von Mersenne Twister verwendet wird, dem IO nicht entziehen können. Dies liegt an der nicht deterministischen Planung, was bedeutet, dass wir nie wissen, welcher der Arbeiter welchen Teil des Arrays handhaben wird und folglich welcher Generator für welchen Teil des Arrays verwendet wird. Auf der anderen Seite, wenn der Generator rein und teilbar ist, wie zum Beispiel splitmix, dann können wir die reine, deterministische und parallelisierbare Generierungsfunktion verwenden:, randomArrayaber das ist bereits eine separate Geschichte.

Lehins
quelle
Für den Fall, dass Sie einige Benchmarks sehen möchten
Lehins
4

Es ist wahrscheinlich keine gute Idee, dies zu tun, da PRNGs von Natur aus sequentiell sind. Stattdessen möchten Sie Ihren Code möglicherweise wie folgt umstellen:

  1. Deklarieren Sie eine E / A-Funktion ( mainoder was haben Sie).
  2. Lesen Sie so viele Zufallszahlen, wie Sie benötigen.
  3. Übergeben Sie die (jetzt reinen) Zahlen an Ihre Repa-Funktionen.
mcandre
quelle
Wäre es möglich, jedes PRNG in jeden parallelen Thread einzubrennen, um statistische Unabhängigkeit zu schaffen?
J. Abrahamson
@ J.Abrahamson ja, das wäre möglich. Siehe meine Antwort.
Lehins