MapM parallèle sur des tableaux Repa

Question

Dans mon récent travail con Gibbs sampling j'ai fait un usage intensif de l'application RVar qui, à mon avis, fournit une interface presque idéale pour la génération de nombres aléatoires. Malheureusement, je n'ai pas été en mesure d'utiliser Repa en raison de l'impossibilité d'utiliser des actions monadiques dans les cartes.

Bien qu'il soit clair que les cartes monadiques ne peuvent pas être parallélisées en général, il me semble que RVar peut être au moins un exemple de monade dont les effets peuvent être parallélisés en toute sécurité (du moins en principe ; je ne suis pas très familier avec le fonctionnement interne de RVar ). À savoir, je veux écrire quelque chose comme ce qui suit,

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

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

donde A.mapM ressemblerait à quelque chose comme,

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

Bien que la manière dont cela fonctionnerait dépende essentiellement de la mise en œuvre de la stratégie de l RVar et son sous-jacent RandomSource En principe, on pourrait penser qu'il s'agit de tirer une nouvelle graine aléatoire pour chaque thread créé et de procéder comme d'habitude.

Intuitivement, il semble que cette même idée puisse se généraliser à d'autres monades.

Donc, ma question est la suivante : peut-on construire une classe ParallelMonad de monades pour lesquelles les effets peuvent être parallélisés en toute sécurité (vraisemblablement habitées par, au moins, RVar ) ?

A quoi cela pourrait-il ressembler ? Quelles autres monades pourraient habiter cette classe ? D'autres personnes ont-elles envisagé la possibilité que cela fonctionne dans Repa ?

Enfin, si cette notion d'actions monadiques parallèles ne peut pas être généralisée, quelqu'un voit-il un moyen agréable de faire fonctionner cette notion dans le cas spécifique de RVar (où il serait très utile) ? Abandon RVar pour le parallélisme est un compromis très difficile.

Answer 1

Cela fait 7 ans que cette question a été posée, et il semble toujours que personne n'ait trouvé de bonne solution à ce problème. Repa n'a pas de mapM / traverse comme une fonction, même une qui pourrait fonctionner sans parallélisation. De plus, compte tenu des progrès réalisés au cours des dernières années, il semble peu probable que cela se produise.

En raison de la désuétude de nombreuses bibliothèques de tableaux en Haskell et de mon insatisfaction générale quant à leurs fonctionnalités, j'ai consacré quelques années de travail à la création d'une bibliothèque de tableaux. massiv qui emprunte certains concepts à Repa, mais l'amène à un niveau complètement différent. Assez avec l'introduction.

Jusqu'à aujourd'hui, il existait trois fonctions monadiques semblables à des cartes dans la bibliothèque de l'UE. massiv (sans compter les fonctions synonymes comme les fonctions : imapM , forM et al.) :

• mapM - la correspondance habituelle dans un Monad . Il n'est pas parallélisable pour des raisons évidentes et est également un peu lent (dans la lignée de ce qui se fait habituellement). mapM sur une liste lente)
• traversePrim - ici nous sommes limités à PrimMonad qui est nettement plus rapide que mapM mais la raison de ce choix n'est pas importante pour cette discussion.
• mapIO - celui-ci, comme son nom l'indique, est réservé aux personnes suivantes IO (ou plutôt MonadUnliftIO mais cela n'est pas pertinent). Parce que nous sommes dans IO nous pouvons automatiquement diviser le tableau en autant de morceaux qu'il y a de cœurs et utiliser des fils de travail distincts pour mettre en correspondance le tableau et les cœurs. IO sur chaque élément de ces morceaux. Contrairement aux fmap qui est également parallélisable, nous devons être dans IO ici en raison du non-déterminisme de l'ordonnancement combiné aux effets secondaires de notre action de mise en correspondance.

Ainsi, lorsque j'ai lu cette question, je me suis dit que le problème est pratiquement résolu en massiv mais pas si vite. Les générateurs de nombres aléatoires, comme dans mwc-random et d'autres dans random-fu ne peut pas utiliser le même générateur sur plusieurs fils. Ce qui veut dire que la seule pièce du puzzle qui me manquait était : "tirer une nouvelle graine aléatoire pour chaque thread créé et procéder comme d'habitude". En d'autres termes, j'avais besoin de deux choses :

• Une fonction qui initialiserait autant de générateurs qu'il y aura de fils de travail.
• et une abstraction qui donnerait de manière transparente le générateur correct à la fonction de mappage en fonction du thread dans lequel l'action est exécutée.

C'est donc exactement ce que j'ai fait.

Tout d'abord, je vais donner des exemples en utilisant l'outil spécialement conçu à cet effet randomArrayWS y initWorkerStates car elles sont plus pertinentes pour la question, avant de passer à la carte monadique plus générale. Voici leurs signatures de type :

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)

Pour ceux qui ne sont pas familiers avec massiv le Comp L'argument est une stratégie de calcul à utiliser, les constructeurs notables sont :

• Seq - exécuter le calcul de manière séquentielle, sans bifurquer de threads
• Par - créer autant de fils qu'il y a de possibilités et les utiliser pour faire le travail.

Je vais utiliser mwc-random à titre d'exemple dans un premier temps, puis de passer à RVarT :

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

Ci-dessus, nous avons initialisé un générateur distinct par thread en utilisant le caractère aléatoire du système, mais nous aurions pu tout aussi bien utiliser une graine unique par thread en la dérivant de l'attribut WorkerId argument, qui est un simple Int l'indice du travailleur. Et maintenant nous pouvons utiliser ces générateurs pour créer un tableau avec des valeurs aléatoires :

λ> 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 ]
  ]

En utilisant Par stratégie le scheduler répartira équitablement le travail de génération entre les travailleurs disponibles et chaque travailleur utilisera son propre générateur, ce qui le rendra thread safe. Rien ne nous empêche de réutiliser le même WorkerStates un nombre arbitraire de fois, tant qu'elle n'est pas effectuée simultanément, ce qui, sinon, entraînerait une exception :

λ> 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 ]

Maintenant, en mettant mwc-random nous pouvons réutiliser le même concept pour d'autres cas d'utilisation possibles en utilisant des fonctions telles que 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)

y 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)

Voici l'exemple promis sur la façon d'utiliser cette fonctionnalité avec rvar , random-fu y mersenne-random-pure64 bibliothèques. Nous aurions pu utiliser randomArrayWS ici aussi, mais pour les besoins de l'exemple, disons que nous avons déjà un tableau avec différents RVarT dans ce cas, nous avons besoin d'un 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 ]
  ]

Il est important de noter qu'en dépit du fait qu'une implémentation pure de Mersenne Twister est utilisée dans l'exemple ci-dessus, nous ne pouvons pas échapper à l'IO. Cela est dû à l'ordonnancement non déterministe, ce qui signifie que nous ne savons jamais lequel des travailleurs traitera quel morceau du tableau et, par conséquent, quel générateur sera utilisé pour quelle partie du tableau. D'un autre côté, si le générateur est pur et divisible, tel que splitmix nous pouvons alors utiliser la fonction de génération pure, déterministe et parallélisable : randomArray mais c'est déjà une autre histoire.

Answer 2

Ce n'est probablement pas une bonne idée de faire cela en raison de la nature intrinsèquement séquentielle des PRNGs. Au lieu de cela, vous pouvez faire évoluer votre code comme suit :

1. Déclarer une fonction IO ( main ou quoi que ce soit d'autre).
2. Lisez autant de nombres aléatoires que vous le souhaitez.
3. Passez les nombres (maintenant purs) à vos fonctions repa.