Parallel mapM na tablicach Repa

W mojej ostatniej pracy z Gibbs samplingwielkim wykorzystaniem RVar, moim zdaniem, zapewnia prawie idealny interfejs do generowania liczb losowych. Niestety, nie mogłem skorzystać z Repa ze względu na brak możliwości korzystania z monadycznych działań na mapach.

Chociaż wyraźnie mapy monadyczne nie mogą być generalnie zrównoleglane, wydaje mi się, że RVarmoże to być przynajmniej jeden przykład monady, w której efekty można bezpiecznie zrównoleglać (przynajmniej w zasadzie; nie jestem strasznie zaznajomiony z wewnętrznym działaniem RVar) . Mianowicie chcę napisać coś takiego jak poniżej,

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

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

gdzie A.mapMwyglądałoby coś takiego,

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

Chociaż wyraźnie to, jak to zadziała, zależy głównie od implementacji RVari podstaw RandomSource, w zasadzie można by pomyśleć, że wymagałoby to losowania nowego, losowego ziarna dla każdego zrodzonego wątku i kontynuowania normalnego postępowania.

Wydaje się, że intuicyjnie ten sam pomysł można uogólnić na inne monady.

A więc moje pytanie brzmi: czy można skonstruować klasę ParallelMonadmonad, dla których efekty mogą być bezpiecznie zrównoleglane (prawdopodobnie zamieszkane przynajmniej przez RVar)?

Jak to może wyglądać? Jakie inne monady mogą zamieszkiwać tę klasę? Czy inni rozważali możliwość, jak to może działać w Repie?

Wreszcie, jeśli nie można uogólnić tego pojęcia równoległych działań monadycznych, czy ktoś widzi jakiś fajny sposób, aby to zadziałało w konkretnym przypadku RVar(gdzie byłoby to bardzo przydatne)? Rezygnacja RVarz paralelizmu to bardzo trudny kompromis.

Minęło 7 lat, odkąd zadano to pytanie, a nadal wydaje się, że nikt nie znalazł dobrego rozwiązania tego problemu. Repa nie ma funkcji podobnej do mapM/ traverse, nawet takiej, która mogłaby działać bez równoległości. Co więcej, biorąc pod uwagę postęp, jaki dokonał się w ciągu ostatnich kilku lat, wydaje się mało prawdopodobne, aby tak się stało.

Ze względu na przestarzały stan wielu bibliotek tablicowych w Haskell i moje ogólne niezadowolenie z ich zestawów funkcji, włożyłem kilka lat pracy nad biblioteką tablicową massiv, która pożycza niektóre koncepcje od Repa, ale przenosi ją na zupełnie inny poziom. Dość z intro.

Przed dzisiaj, nie było trzy monadycznego mapa jak funkcje w massiv(nie licząc synonim jak funkcje: imapM, forMet al.):

• mapM- zwykłe mapowanie w sposób arbitralny Monad. Nie można zrównoleglać z oczywistych powodów, a także jest nieco powolny (podobnie jak zwykle mapMna liście wolno)
• traversePrim- tutaj jesteśmy ograniczeni PrimMonad, co jest znacznie szybsze niż mapM, ale przyczyna tego nie jest istotna dla tej dyskusji.
• mapIO- ten, jak nazwa sugeruje, ogranicza się do IO(a raczej MonadUnliftIO, ale to nie ma znaczenia). Ponieważ jesteśmy w IOśrodku, możemy automatycznie podzielić tablicę na tyle fragmentów, ile jest rdzeni, i użyć oddzielnych wątków roboczych, aby zmapować IOdziałanie każdego elementu w tych fragmentach. W przeciwieństwie do pure fmap, który jest również równoległy, musimy być IOtutaj z powodu niedeterminizmu planowania w połączeniu z efektami ubocznymi naszej akcji mapowania.

Kiedy więc przeczytałem to pytanie, pomyślałem, że problem został praktycznie rozwiązany massiv, ale nie tak szybko. Generatory liczb losowych, takie jak in mwc-randomi inne w, random-funie mogą używać tego samego generatora w wielu wątkach. Co oznacza, że ​​jedynym elementem układanki, którego mi brakowało, było: „losowanie nowego, losowego nasienia dla każdej zrodzonej nitki i kontynuowanie normalnego postępowania”. Innymi słowy, potrzebowałem dwóch rzeczy:

• Funkcja, która zainicjuje tyle generatorów, ile będzie wątków roboczych
• oraz abstrakcja, która bezproblemowo zapewni prawidłowy generator funkcji mapującej w zależności od wątku, w którym działa akcja.

Więc to jest dokładnie to, co zrobiłem.

Najpierw podam przykłady przy użyciu specjalnie spreparowanych funkcji randomArrayWSi initWorkerStatesfunkcji, ponieważ są one bardziej odpowiednie dla pytania, a później przejdę do bardziej ogólnej mapy monadycznej. Oto ich podpisy typu:

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)

Dla tych, którzy nie są zaznajomieni massiv, Compargumentem jest strategia obliczeniowa, godnymi uwagi konstruktorami są:

• Seq - uruchamiaj obliczenia sekwencyjnie, bez rozwidlania żadnych wątków
• Par - rozkręć tyle wątków, ile jest możliwości i wykorzystaj je do wykonania pracy.

Na początku użyję mwc-randompakietu jako przykładu, a później przejdę do RVarT:

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

Powyżej zainicjowaliśmy oddzielny generator na wątek przy użyciu losowości systemowej, ale równie dobrze moglibyśmy użyć unikalnego ziarna dla każdego wątku, wyprowadzając je z WorkerIdargumentu, który jest zwykłym Intindeksem procesu roboczego. A teraz możemy użyć tych generatorów do stworzenia tablicy z losowymi wartościami:

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

Korzystając ze Parstrategii, schedulerbiblioteka podzieli równomiernie pracę pokolenia na dostępnych pracowników, a każdy pracownik będzie korzystał z własnego generatora, dzięki czemu będzie bezpieczny dla wątków. Nic nie stoi na przeszkodzie, abyśmy ponownie wykorzystali tę samą WorkerStatesdowolną liczbę razy, o ile nie jest to wykonywane jednocześnie, co w przeciwnym razie skutkowałoby wyjątkiem:

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

Teraz odkładając mwc-randomna bok, możemy ponownie wykorzystać tę samą koncepcję do innych możliwych zastosowań, używając funkcji takich jak 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)

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

Oto obiecany przykład, w jaki sposób korzystać z tej funkcjonalności z rvar, random-fui mersenne-random-pure64bibliotek. Mogliśmy również użyć randomArrayWStutaj, ale dla przykładu powiedzmy, że mamy już tablicę z różnymi RVarTs, w takim przypadku potrzebujemy 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 ]
  ]

Należy zauważyć, że pomimo faktu, że w powyższym przykładzie używana jest czysta implementacja Mersenne Twister, nie możemy uciec od IO. Dzieje się tak z powodu niedeterministycznego planowania, co oznacza, że ​​nigdy nie wiemy, który z procesów roboczych będzie obsługiwał który fragment tablicy, a co za tym idzie, który generator będzie używany dla której części tablicy. Z drugiej strony, jeśli generator jest czysty i podzielny, na przykład splitmix, możemy użyć czystej, deterministycznej i równoległej funkcji generującej: randomArrayale to już jest osobna historia.

Robienie tego prawdopodobnie nie jest dobrym pomysłem ze względu na z natury sekwencyjny charakter PRNG. Zamiast tego możesz przenieść kod w następujący sposób:

1. Zadeklaruj funkcję we / wy ( mainlub co masz).
2. Przeczytaj tyle liczb losowych, ile potrzebujesz.
3. Przekaż (teraz czyste) liczby do funkcji repa.