Параллельные вычисления с быстрой случайностью и чистотой?

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

Без случайности мой расчет - это просто некоторое количество хрустов, и поэтому оно чистое, и я мог бы использовать parMap. Чтобы получить хорошие результаты, мне нужно взять несколько образцов на каждом шаге и усреднить результаты. Выборка должна быть рандомизирована.

Одним из решений может быть использование случайного пакета, вызов randoms, а затем использование этого списка во время вычисления (путем передачи чистого ленивого список к вычислению, я бы сохранил его чисто). К сожалению, это очень медленный генератор случайных чисел, и мне нужно много случайных чисел, поэтому я предпочел бы использовать mwc-random или mersenne-random (хотя, я не думаю, что mersenne-random все еще поддерживается).

Можно ли использовать нечто вроде unsafePerformIO с mwc-random для записи функции типа randoms? Что-то вроде этого:

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)

Нужно ли вместо этого использовать генератор параллельных чисел? Или мне нужно укусить пулю и признать, что мой алгоритм просто не чист, не используя медленный случайный пакет?

Предложения? Спасибо!

Ответы

Ответ 1

Если наличие однопоточного источника случайности не является проблемой для производительности, вы можете получить чистую оболочку вокруг mwc-random

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)

здесь rList берет семя, а затем лениво производит бесконечный поток ленивых чисел детерминистически. Я не уверен, что strictToLazyST действительно безопасен, но никто, кажется, не возражает против него. Я не проводил бенчмаркинга, но я подозреваю, что это довольно быстро. Я полагаю, что mwc-random является потокобезопасным из-за потока данных разбора, закодированного с помощью генератора, и что он может использоваться в монаде ST. Приглашение кого-либо использовать взломать выше. Я не думаю, что seq необходимо, но это делает меня менее подозрительным strictToLazyST, что я знаю, что у меня есть детерминированный порядок оценки (и он все еще ленив, чтобы работать).

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

GHCi:

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

Ответ 2

У меня есть не совсем готовый пакет hsrandom123 на Github, который может быть полезен здесь. Я начал реализовывать этот пакет, чтобы иметь подходящий RNG для параллельных вычислений. Он повторно объединяет RNG Philox и Threefry из библиотеки random123 C (там также описывается описание идей).

Есть причина, по которой моя библиотека еще не выпущена: хотя фактическая реализация RNG выполнена и, похоже, дает те же результаты, что и версия C, я не определил, какой интерфейс Haskell использовать, а библиотека вряд ли документирована. Не стесняйтесь обращаться ко мне, если вам нужна дополнительная информация или помощь в ее использовании.

Ответ 3

Я предполагаю, что mersenne-random не является потокобезопасным, поэтому использование любого unsafe... и распараллеливания приведет к проблемам с вызовом его из нескольких потоков. (См. Также руководство GHC. Раздел 8.2.4.1.)

Функции, которые требуют случайности, не являются чистыми, им нужен некоторый источник случайности, который является либо внешним (hardware - как устройство шум выборки) и, следовательно, привязан к IO или псевдослучайному, который должен поддерживать некоторое состояние во время вычисления. В любом случае они не могут быть чистыми функциями Haskell.

Я бы начал с разделения ваших требований на определенный тип типа монады, например, что-то вроде

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

который позволит вам написать свой основной код без привязки к конкретной реализации. Или, если вы чувствуете смелость, вы можете использовать monad-parallel и определить что-то вроде

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

Теперь сложной частью является определение как random, так и parSequence (или MonadParallel bindM2) и сделать это быстро. Поскольку вы контролируете bindM2, вы можете управлять тем, как создаются потоки и какое состояние они сохраняют. Таким образом, вы можете привязать буфер к каждому потоку, из которого он извлекает рандомизированные числа. Если буфер пуст, он выполняет синхронизированные вызовы для mersenne-random (или другого генератора числа IO), заполняет буфер и продолжается.

(Если вы реализуете что-то подобное, было бы неплохо сделать из него отдельную библиотеку.)

Обратите внимание, что randoms из mersenne-random уже использует unsafeInterleaveIO для создания ленивого списка, но я бы сказал, что список предназначен для потребления только из одного потока. И у этого есть также место для улучшений. Он использует unsafeInterleaveIO и имеет некоторые накладные расходы, как указано в свой комментарий:

Здесь есть реальные накладные расходы. С нетерпением ждем, чтобы куски были аккуратно заполнены и извлекли элементы.

Ответ 4

Для полноты ответов позвольте мне объяснить, что я делаю в данный момент, чтобы решить эту проблему.

Вместо того, чтобы сделать вычисление чистым, я решил использовать async вместо parallel.

Если я решил пересмотреть мое текущее решение, чтобы быть чистым, я сначала попробую решение, предложенное Филиппом JF, поэтому я отметил его ответ как принятый.

Моя следующая задача - выяснить, как аппроксимировать оптимальное разбиение работы, чтобы потоковая передача уменьшала количество времени, а не заставляла его занимать больше времени.)