Параллельное отображениеM на массивах Repa

Ответ 1

Вероятно, это не очень хорошая идея сделать это из-за последовательного характера PRNG. Вместо этого вы можете перевести свой код следующим образом:

• Объявить функцию ввода-вывода (main или что у вас есть).
• Прочитайте как можно больше случайных чисел.
• Передайте (теперь чистые) числа на ваши функции repa.

Ответ 2

Прошло 7 лет с тех пор, как этот вопрос был задан, и все еще кажется, что никто не придумал хорошего решения этой проблемы. mapM не имеет функции, аналогичной mapM/traverse, даже такой, которая могла бы выполняться без распараллеливания. Более того, учитывая прогресс, достигнутый за последние несколько лет, маловероятно, что это также произойдет.

Из - за несвежее состоянием многих библиотек массивов в Haskell и моей общей неудовлетворенность их наборы функций я загадал пару лет работы в библиотеке массива massiv, который заимствует некоторые понятия Репы, но беру его на совершенно иной уровень, Достаточно интро.

До сегодняшнего дня, было три монадическая карта как функции в massiv (не считая синонимом как функции: imapM, forM. И др):

• mapM - обычное отображение в произвольной Monad. Не распараллеливается по очевидным причинам, а также немного медленен (по обычному mapM над списком медленный)
• traversePrim - здесь мы ограничены PrimMonad, который значительно быстрее, чем mapM, но причина этого не важна для этого обсуждения.
• mapIO - этот, как следует из названия, ограничен IO (или, скорее, MonadUnliftIO, но это не имеет значения). Поскольку мы находимся в IO мы можем автоматически разбивать массив на столько частей, сколько имеется ядер, и использовать отдельные рабочие потоки для сопоставления действия IO каждого элемента в этих чанках. В отличие от чистого fmap, который также можно распараллелить, мы должны быть здесь в IO из-за недетерминированности планирования в сочетании с побочными эффектами нашего действия отображения.

Итак, прочитав этот вопрос, я подумал про себя, что проблема практически решается massiv, но не так быстро. Генераторы случайных чисел, такие как mwc-random и другие в random-fu не могут использовать один и тот же генератор во многих потоках. Это означает, что единственной частью головоломки, которую я пропустил, было: "нарисовать новое случайное семя для каждой порожденной нити и продолжить как обычно". Другими словами, мне нужно было две вещи:

• Функция, которая инициализирует столько генераторов, сколько будет рабочих потоков
• и абстракция, которая без проблем предоставит правильный генератор для функции отображения в зависимости от того, в каком потоке выполняется действие.

Именно это я и сделал.

Сначала я приведу примеры с использованием специально созданных randomArrayWS и initWorkerStates, так как они более актуальны для вопроса, а позже initWorkerStates к более общей монадической карте. Вот их тип подписи:

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)

Для тех, кто не знаком с massiv, аргумент Comp - это вычислительная стратегия, которую можно использовать, например, следующие конструкторы:

• Seq - запускать вычисления последовательно, без разветвлений
• Par столько потоков, сколько есть возможностей, и используйте их для выполнения работы.

mwc-random я буду использовать mwc-random в качестве примера, а позже RVarT к RVarT:

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

Выше мы инициализировали отдельный генератор для каждого потока, используя системную случайность, но мы могли бы также использовать уникальный начальный поток для каждого потока, извлекая его из аргумента WorkerId, который является простым индексом Int рабочего. И теперь мы можем использовать эти генераторы для создания массива со случайными значениями:

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

Используя стратегию Par, библиотека scheduler будет равномерно распределять работу генерации между доступными работниками, и каждый работник будет использовать свой собственный генератор, тем самым делая его потокобезопасным. Ничто не мешает нам повторно использовать одни и WorkerStates же WorkerStates произвольное количество раз, если это не делается одновременно, что в противном случае привело бы к исключению:

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

Теперь, поместив mwc-random в сторону, мы можем повторно использовать ту же концепцию для других возможных случаев использования с помощью таких функций, как 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)

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

Вот обещанный пример использования этой функциональности с rvar, random-fu и mersenne-random-pure64. Мы могли бы и здесь использовать randomArrayWS, но в качестве примера, допустим, у нас уже есть массив с различными RVarT, и в этом случае нам нужен 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 ]
  ]

Важно отметить, что, несмотря на то, что в приведенном выше примере используется чистая реализация Mersenne Twister, мы не можем избежать ввода-вывода. Это из-за недетерминированного планирования, что означает, что мы никогда не знаем, кто из рабочих будет обрабатывать какой кусок массива и, следовательно, какой генератор будет использоваться для какой части массива. С другой стороны, если генератор является чистым и разделяемым, например, splitmix, то мы можем использовать чистую, детерминистическую и распараллеливаемую функцию генерации: randomArray, но это уже отдельная история.