Paralleles mapM auf Repa-Arrays

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.

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.

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.