Параллельные генераторы псевдослучайных чисел

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

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

Можем ли мы иметь 1000 параллельных потоков со следующими свойствами? Здесь должен быть очень известным и широко изученным PRNG со всеми видами хороших теоретических и эмпирических свойств.$X$

1. Потоки, вероятно, так же хороши, как если бы я просто использовал и разделил поток, сгенерированный X, на 1000 потоков.$X$$X$

2. Генерация следующего числа в любом потоке (почти) так быстро , как генерации следующего номера с .$X$

Иначе говоря: можем ли мы получить несколько независимых потоков «бесплатно»?

Конечно, если бы мы просто использовали , всегда отбрасывая 999 чисел и выбирая 1, то у нас наверняка было бы свойство 1, но мы потеряли бы во время выполнения в 1000 раз.$X$

Простая идея состоит в том, чтобы использовать 1000 копий с начальными числами 1, 2, ..., 1000. Это, безусловно, будет быстрым, но не очевидно, если потоки имеют хорошие статистические свойства.$X$

После некоторого поиска в Google я обнаружил, например, следующее:

• Библиотека SPRNG, похоже, предназначена именно для этой цели и поддерживает несколько PRNG .

• В наше время Mersenne Twister, кажется, является популярным PRNG, и я нашел несколько ссылок на вариант, который может генерировать несколько потоков параллельно.

Но все это так далеко от моих собственных областей исследований, что я не мог понять, что на самом деле является современным, и какие конструкции хорошо работают не только в теории, но и на практике.

Некоторые уточнения: мне не нужны никакие криптографические свойства; это для научных расчетов. Мне понадобятся миллиарды случайных чисел, поэтому мы можем забыть любой генератор с периодом .$< 2^{32}$

Редактировать: я не могу использовать настоящий ГСЧ; Мне нужен детерминистический PRNG. Во-первых, это очень помогает при отладке и делает все воспроизводимым. Во-вторых, это позволяет мне, например, очень эффективно находить медиану, используя тот факт, что я могу использовать многоходовую модель (см. Этот вопрос ).

Редактировать 2: Есть тесно связанный вопрос @ StackOverflow: генератор псевдослучайных чисел для кластерной среды .

Вы можете использовать эволюцию алгоритма Мерсенна Твистера, разработанного Сайто и Мацумото:

SIMD-ориентированный Fast Mersenne Twister (SFMT)

SFMT - это генератор регистров сдвига с линейной обратной связью (LFSR), который генерирует 128-битное псевдослучайное целое число за один шаг. SFMT разработан с учетом недавнего параллелизма современных процессоров, таких как многоступенчатый конвейер и инструкции SIMD (например, 128-битное целое число). Он поддерживает 32-разрядные и 64-разрядные целые числа, а также с плавающей запятой двойной точности в качестве выходных данных. SFMT намного быстрее, чем MT, на большинстве платформ. Улучшена не только скорость, но и размеры равнораспределений с точностью v-бита. Кроме того, восстановление из 0-избыточного исходного состояния происходит намного быстрее. См. Магистерскую диссертацию Муцуо Сайто для подробностей .

Период колеблется от до 2 216091 - 1 .$2^{607}-1$$2^{216091}-1$

Использование одного и того же генератора псевдослучайных чисел для генерации нескольких независимых потоков путем изменения начальных значений может вызвать проблемы (с пренебрежимо малой вероятностью). Чтобы избежать проблемы, использование разных параметров для каждого поколения является предпочтительным. Этот метод называется динамическим созданием параметров МП.

В исходном коде SFMT вы можете найти несколько примеров наборов параметров (переменных периодов) и сценария awk для преобразования файла CSV в скомпилированный набор параметров. Существует также инструмент под названием « Динамическое создание генераторов Мерсенна Твистера ».

Недавно авторы разработали еще одну модифицированную версию Mersenne Twister - Mersenne Twister для графических процессоров - предназначенную для работы в графических процессорах и использования преимуществ собственных потоков параллельного выполнения. Ключевой особенностью является скорость: случайных целых чисел каждые 4,6 мс на GeForce GTX 260.$5 \times 10^7$

Периоды сгенерированной последовательности составляют , 2 23209 - 1 и 2 44497 - $2^{11213}-1$$2^{23209}-1$$2^{44497}-1$ для 32-разрядной версии и , 2 44497 - 1 , 2 110503 - 1 для 64-разрядной версии. Он поддерживает 128 наборов параметров для каждого периода, другими словами, он может генерировать 128 независимых последовательностей псевдослучайных чисел для каждого периода. Мы разработали Dynamic Creator для MTGP, который генерирует больше наборов параметров$2^{23209}-1$$2^{44497}-1$$2^{110503}-1$

Действительно, они предоставляют инструмент MTGPDC для создания до наборов параметров (т.е. независимых потоков).$2^{32}$

Алгоритм проходит основные тесты на случайность, такие как Diehard и NIST.

Предварительная статья также доступна по arXiv: вариант Mersenne Twister, подходящий для графических процессоров.

Кажется, есть много способов решить эту проблему, но одним простым способом было бы использовать PRNG Blum Blum Shub . Этот PRNG определяется рекуррентным соотношением , где N - полупростая. Чтобы получить случайный бит из этого, вы можете просто взять битовую четность x i . Что хорошо в этом, так это то, что, поскольку x i + k = x 2 k i  mod  N = x 2 mod  N, вы можете напрямую рассчитать любой шаг постоянной времени в$x_{i+1} = x_i^2 \mbox{ mod }N$$N$$x_i$$x_{i+k} = x_i^{2^k}\mbox{ mod }N = x_i^{2^k \mbox{ mod } \lambda(N)}\mbox{mod }N$ (т.е. O ( log ( N ) 3 ) или быстрее) в зависимости от того, какой алгоритм умножения вы используете для модульной экспоненты). Таким образом, если у вас есть M машин, то для машины, индексированной y, вы можете использовать генератор x i + 1 , y = x 2 M mod  λ ( N ) i  mod  N , где x 0 , y = $k$$O(\log(N)^3)$$M$$y$$x_{i+1,y} = x_i^{2^M \mbox{mod }\lambda(N)}\mbox{ mod }N$, гдеx0- ваше начальное число. Удобно, что это генерирует точно такой же поток чисел, как если бы вы использовали один поток и распределяли его выходные данные по каждой из машин по очереди.$x_{0,y} = x_0^{2^y \mbox{ mod }\lambda(N)}\mbox{ mod }N$$x_0$

Однако это не самый быстрый из PRNG, поэтому он будет полезен только в том случае, если накладные расходы на то, что вы делаете в симуляции, значительно превышают стоимость PRNG. Однако стоит отметить, что для некоторых комбинаций и N это будет намного быстрее, чем для других, особенно если двоичное представление 2 $M$$N$ содержит несколько единиц или мало.$2^M \mbox{ mod }\lambda(N)$

Как насчет фазы предварительной обработки? Учитывая случайное начальное число (размера n ), запустите X, чтобы получить псевдослучайный поток размером 1000 n . Обозначим этот поток через s 1 , s 2 , … , s 1000 , где для 1 ≤ i ≤ 1000 , s $s$$n$$X$$1000n$$s_1,s_2,\ldots,s_{1000}$$1\le i \le 1000$$s_i$$n$

Эта фаза предварительной обработки может быть выполнена с очень низкими издержками, учитывая тот факт, что $X$

Теперь, отдавание как семя в $s_i$$i$$X$

$X$$s$$1 \le i < j \le 1000$$s_i$$s_j$$s$ ); следовательно, этот подход не требует большой случайности или хранения.

$f$$M = 1000$$\{ 0, 1, \ldots, M - 1 \}$$j$$i$$f(i + jM)$$M$

Это даст вам криптографический ГСЧ для каждого процесса, но это не обязательно приведет к снижению производительности. AES работает быстро, если у вас есть оборудование, которое его поддерживает, и ChaCha работает быстро Конечно, вы хотите измерить это в ваших конкретных условиях, чтобы быть уверенным.

$f$

Теперь есть функция перехода для SFMT (быстрая реализация Mersenne Twister).

Это позволяет мне инициализировать 1000 МТ, чтобы не было перекрытия циклов. И SFMT должен быть быстрее, чем MTGP. Почти идеально подходит для моих целей.

Вы можете просто использовать 1000 экземпляров Mersenne Twister, инициализированных различными семенами.

Вы можете попробовать семена из другого Mersenne Twister или, чтобы быть уверенным в их независимости, из генератора криптографических псевдослучайных чисел ОС (/ dev / urandom в Linux).

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