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

Question

проблема

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

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

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

1. Посеять PRNG для каждого потока независимо от /dev/urandom,

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

2. Семя одно PRNG из /dev/urandom и остальные из этого первого.

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

3. Посмотрите на других с самого начала с информацией, не относящейся к Мерсенну.

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

4. Поделиться одним PRNG среди потоков.

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

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

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

Вопросы

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

Знаете ли вы, какие из моих опасений оправданы, а какие просто связаны с тем, что я не понимаю, как все работает на самом деле?

Answer 1

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

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

Answer 2

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

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

#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 3

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

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

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

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

Answer 4

Семенная нить 1 с 1, семенная нить 2 с 2 и т. Д.

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

Answer 5

Взгляните на следующую статью: Динамическое создание генераторов псевдослучайных чисел и сопутствующая реализация: Dynamic Creator. Это решает эту точную проблему.

Answer 6

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

На практике, однако, будет достаточно инициализации /dev/urandom.

Answer 7

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

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

Answer 8

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

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

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