Случайные числа для нескольких потоков

Question

Проблема

Я намерен написать заявление на C++ 11 для Linux, который делает некоторые численное моделирование (не криптография) на основе примерно один миллион псевдослучайных чисел 32bit. Чтобы ускорить работу, я хотел бы выполнить симуляцию в параллельных потоках, используя все ядра настольного процессора. Я бы хотел использовать Mersenne Twister mt19937, предоставляемый boost как PRNG, и я предполагаю, что по соображениям производительности у меня должен быть такой PRNG на поток. Теперь я не уверен, как их семени, чтобы не генерировать одну и ту же последовательность случайных чисел в нескольких потоках.

Альтернативы

Вот альтернативы, которые я думал до сих пор:

1. семени ГСЧ для каждого потока независимо от /dev/urandom.

   Меня немного беспокоит случай, когда пул энтропийных систем исчерпывается, так как я не знаю, как работает внутренний PRNG системы. Может случиться так, что я случайно получаю последовательные семена, которые точно определяют последовательные состояния Mersenne Twister, из-за того, что /dev/urandom использует сам Мерсенн Твистер? Наверное, сильно связан с моими опасениями в отношении следующего пункта.

2. Семена один PRNG от /dev/urandom и другие от первого.

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

3. Семена сперва с информацией, не относящейся к Мерсенне.

   Как использовать тот же алгоритм для генерации случайных чисел и генерации начального семени, как-то вроде бы плохой идеи, я подумал о введении некоторого элемента, который не зависит от алгоритма Мерсенна Твистера. Например, я мог бы XOR идентификатор потока в каждый элемент исходного вектора семени. Это улучшает ситуацию?

4. Поделитесь одним PRNG среди тем.

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

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

   У этого будет один поток, который генерирует все необходимые 1M случайные числа спереди, которые будут использоваться различными потоками позже. Требование к памяти 4M было бы небольшим по сравнению с объемом всего приложения. Меня больше всего беспокоит такой подход: генерация самих случайных чисел не является параллельной. Весь этот подход также не слишком хорошо масштабируется.

Вопросы

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

Знаете ли вы, какие из моих проблем оправданы и которые просто из-за моего отсутствия понимания того, как все работает?

Answer 1

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

• Даже небольшие изменения в пространстве состояний вызывают довольно большие изменения вниз - если вы можете гарантировать, что они не имеют точно такое же начальное пространства (и не идентичный государственный префикса), я бы не беспокоиться о производстве идентичных номеров , Например, использование только значений 1,2,3 для семян трех потоков будет работать нормально - вам даже не нужно высевать все пространство. Еще одно преимущество: используя явно предсказуемые семена, вы можете легко дискредитировать идею о том, что вы выбрали вишню в любых прогонах (при условии, что вы пытаетесь что-то продемонстрировать).
• Это тривиально посеять таким образом, чтобы результирующие «дети» были сильно не скоррелированы. Просто перебирайте в первую очередь; т.е. если вы хотите высевать значения N x 623 int, не выставляйте значения 623 последовательно, а выбирайте первый N и распределяете, затем следующий N и т. д. Даже если есть некоторая корреляция между сеятелем и дочерними элементами, корреляция между различные дети должны быть практически несуществующими - и это все, о чем вы заботитесь.
• Я бы предпочел алгоритм, который допускает детерминированное выполнение, когда это возможно, поэтому в зависимости от на урбанде не является привлекательным. Это облегчает отладку.
• Наконец, и, очевидно, тест. Эти PRNG довольно надежны, но, во всяком случае, обеспечивают результаты и делают несколько корреляционных тестов, вдохновляющих то, что вы имитируете. Большинство проблем должно быть очевидным - либо вы посеялись плохо, и есть очевидные повторяющиеся подпоследовательности, вы хорошо посеялись, а затем качество диктуется ограничениями PRNG.
• Для окончательных исполнений после завершения тестирования вы можете перенести первое из значений состояния 623, используя уранд для спокойствия и/или идентификатора потока.

Answer 2

Я бы сказал, что №3 является победителем. Семя каждого потока с чем-то вроде processID или threadID; в то время как технически возможно, что вы могли бы перекрыться, это маловероятно. Даже последовательные числа не должны быть связаны с семенами, когда вы выходите из одиночных цифр (я не знаю алгоритм Twister, но худший PRNG, который я видел, был выше 7). Один миллион PRNG не так много по сравнению с объемом большинства уравнений PRNG.

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

Answer 3

Взгляните на следующий документ: Dynamic Creation of Pseudorandom Number Generators и прилагаемый вариант: Dynamic Creator. Он решает эту проблему.

Answer 4

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

Однако я бы выбрал №5. Если он работает, тогда это нормально. Если это не так, вы все равно можете его оптимизировать.

Точка создание хорошего ПГСЧА намного сложнее, чем можно было бы ожидать. Хороший PRNG для поточных приложений - это, скорее всего, то, что все еще подлежит исследованию.

Если количество процессоров достаточно низкое, вы можете ускользнуть от прыжков. Например. если у вас есть 4 ядра, инициализируйте все с одинаковыми значениями, но продвигайте ядро ​​1 PRNG на 1, # 2 и 3 на 3. Затем заранее выполняйте 4 шага, когда вам нужен новый номер.

Answer 5

Я бы пошел с № 1, семенами каждый prng из урбанда. Это гарантирует, что состояния полностью независимы (поскольку данные семян независимы). Как правило, будет доступно множество энтропии, если у вас много потоков. Кроме того, в зависимости от алгоритма, используемого для/dev/urandom, вам почти наверняка не нужно беспокоиться об этом.

Таким образом, вы могли бы использовать что-то вроде следующего для создания каждого ПГСЧ:

#include <random> 

std::mt19937 get_prng() { 
    std::random_device r; 
    std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()}; 
    return std::mt19937(seed); 
} 

Вы должны убедиться, что реализация std::random_device извлечений из /dev/urandom под вашей конфигурации. И если он по умолчанию использует/dev/urandom, то обычно вы можете сказать std::random_device("/dev/random"), если вы хотите использовать/dev/random вместо этого.

Answer 6

Seed нить 1 с 1, Семя нить 2 с 2, и т.д.

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

Answer 7

Существует конкретная реализация (и опубликованная статья), касающаяся использования Mersenne Twister для параллельных вычислений. Это оригинальные авторы МТ. Они относятся к нему как «Dynamic Создатель», и его можно найти здесь:

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html

Это было бы очень хорошее место, чтобы изучить ваше специальное использование MT19937, особенно там бумаги.

Answer 8

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

Практически, однако, достаточно инициализации/dev/urandom.