Obliczenia równoległe z dużą losowością i czystością?

Question

Moim celem jest zrównoleglenie obliczeń przy użyciu parMap z parallel package, ale chciałbym również dodać trochę losowości do mojej funkcji próbkowania.

Bez losowości moje obliczenia są po prostu chrupaniem numerów, więc jest czysto i mogę użyć parMap. Aby uzyskać dobre wyniki, muszę pobrać wiele próbek na każdym etapie i uzyskać średnie wyniki. Pobieranie próbek musi być losowe.

Jednym z rozwiązań może być użycie random package, wywołanie randoms, a następnie skonsumowanie tej listy podczas obliczeń (przekazując czystą leniwą listę do obliczeń, które utrzymam w czystości). Niestety, jest to bardzo wolny generator liczb losowych i potrzebuję dużej liczby liczb losowych, więc wolałbym użyć albo mwc-random lub mersenne-random (chociaż, nie sądzę, że losy mersenne są nadal utrzymywane).

Czy można bezpiecznie używać czegoś takiego jak unsafePerformIO z mwc-random, aby napisać funkcję podobną do randoms? Coś takiego:

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) 

Czy muszę zamiast tego sięgnąć po numer parallel number generator? Czy muszę ugryźć kulę i przyznać, że mój algorytm nie jest po prostu czysty bez użycia powolnego losowego pakietu?

Sugestie? Dzięki!

Answer 1

przypadku posiadania jednego gwintowany źródło losowości nie jest problemem dla wydajności, można uzyskać czystą otoki wokół MWC-losowej

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) 

tutaj rList pobiera nasienie, a potem leniwie produkuje nieskończony strumień leniwych liczb deterministycznie. Nie jestem pewien, czy strictToLazyST jest naprawdę bezpieczny, ale nikt nie wydaje się temu sprzeciwiać. Nie zrobiłem żadnego testu porównawczego, ale podejrzewam, że jest to dość szybkie. Zakładam, że mwc-random jest bezpieczny dla wątków z powodu przepływu danych explitingu zakodowanego z generatorem i że może być użyty w monadzie ST. Zaproszenie kogoś do użycia powyższego hackowania. Nie sądzę, że seq jest konieczne, ale sprawia, że ​​mniej podejrzane o strictToLazyST, wiem, że mam deterministyczny porządek oceny (i nadal jest wystarczająco leniwy, aby pracować).

Nadal potrzebna jest losowość (czyli IO), aby wygenerować prawdziwe losowe ziarno, ale powinno to pozwolić zachować większość kodu czystego i pozwolić przechowywać ziarno do pliku lub użyć go ponownie, gdy jest to konieczne.

GHCi:

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

Answer 2

Domyślam się, że mersenne-random nie jest bezpieczny dla wątków, więc użycie dowolnego unsafe... i równoległości doprowadzi Cię do problemów z wywołaniem go z wielu wątków. (. Patrz także rozdział 8.2.4.1 GHC manual)

funkcji, które wymagają przypadkowość nie są czyste, muszą jakieś źródło losowości, który jest albo zewnętrznego (hardware - jak hałas próbkowania urządzenie), a więc związany IO, lub pseudorandom, który musi zachować pewien stan podczas obliczeń. Tak czy inaczej nie mogą być czystymi funkcjami Haskell.

zacząłbym z oddzielając swoje wymagania do konkretnej klasy typu monada, na przykład coś jak

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

który pozwoli Ci napisać swój główny kod nie będąc związana z konkretną realizację. Lub jeśli czujesz się śmiały można użyć monad-parallel i zdefiniować coś podobnego

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

Teraz najtrudniejsza część jest jak zdefiniować zarówno random i parSequence (lub MonadParallel „s bindM2) i czyni go szybko. Ponieważ masz kontrolę nad bindM2, możesz zarządzać sposobem tworzenia wątków i ich stanem. Dzięki temu można powiązać bufor z każdym wątkiem, z którego losowane są liczby. Jeśli bufor jest pusty, wykonuje zsynchronizowane wywołania do mersenne-random (lub innego generatora liczbowego na podstawie numeru IO), wypełnia bufor i kontynuuje.

(Jeśli zaimplementujesz coś takiego, byłoby miło zrobić z tego niezależną bibliotekę.)

---

Zauważ, że randoms z Mersenne losowych korzysta już unsafeInterleaveIO produkować listę leniwy, ale powiedziałbym, że lista ma być spożywane tylko z jednego wątku. Ma też pole do ulepszeń. Używa ona wartości unsafeInterleaveIO i ma trochę narzutów, jak odnotowano w its comment:

Tutaj są prawdziwe koszty ogólne. Zastanów się nad tym, aby nieoczekiwanie wypełniać kawałki i wyodrębniać elementy.

Answer 3

mam nie całkiem gotowy zwolnić pakiet hsrandom123 na Github, które mogą być pomocne tutaj. Zacząłem wdrażać ten pakiet, aby mieć odpowiedni RNG do równoległych obliczeń. Reimplementuje RNG Philoxa i Threefry z the random123 C library (jest tam także papier opisujący te pomysły).

Jest powód, dla którego moja biblioteka jest niewydana: chociaż rzeczywiste wdrożenie RNG zostało wykonane i wydaje się, że daje takie same wyniki, jak wersja C, nie byłem zdecydowany, z jakiego interfejsu Haskell korzystać, a biblioteka jest prawie nie udokumentowana . Jeśli potrzebujesz więcej informacji lub pomocy, skontaktuj się ze mną.

Answer 4

Aby uzyskać kompletność odpowiedzi, pozwól mi wyjaśnić, co robię w tej chwili, aby rozwiązać ten problem.

Zamiast próbować uczynić obliczenia czystym, zdecydowałem się użyć pakietu async zamiast parallel.

Jeśli zdecyduję się zmienić moje obecne rozwiązanie na czyste, najpierw spróbuję rozwiązania zaproponowanego przez Philipa JF, więc zaznaczyłem jego odpowiedź jako zaakceptowaną.

Moim następnym wyzwaniem jest dowiedzieć się, jak w przybliżeniu optymalnego wyrwy prac tak, gwintowania zmniejsza ilość czasu zamiast dokonywania potrwać dłużej :)