Я намереваюсь написать приложение на C ++ 11 для Linux, которое выполняет некоторое численное моделирование (не криптографию) на основе приблизительно одного миллиона псевдослучайных 32-битных чисел. Чтобы ускорить процесс, я хотел бы выполнить симуляцию в параллельных потоках, используя все ядра центрального процессора настольного компьютера. Я хотел бы использовать Mersenne Twister mt19937
обеспечивается в качестве PRNG, и я думаю, что по соображениям производительности у меня должен быть один такой PRNG на поток. Теперь я не уверен, как их заполнить, чтобы избежать генерации одной и той же подпоследовательности случайных чисел в нескольких потоках.
Вот альтернативы, о которых я думал до сих пор:
Посеять PRNG для каждого потока независимо от /dev/urandom
,
Меня немного беспокоит случай, когда пул энтропии системы исчерпан, так как я не знаю, как работает внутренний PRNG системы. Может ли это случиться так, что я случайно получу последовательные семена, которые точно идентифицируют последовательные состояния Twister Мерсенна, из-за того, что /dev/urandom
использует сам Mersenne Twister? Вероятно, сильно связано с моей озабоченностью по следующему пункту.
Семя одно PRNG из /dev/urandom
и остальные из этого первого.
По сути, это то же самое: хорошо или плохо использовать один PRNG для посева другого, использующего тот же алгоритм? Или, другими словами, чтение 625 32-битных целых чисел из mt19937
соответствуют непосредственно внутреннему состоянию mt19937
генератор в любой момент во время этого поколения?
Посмотрите на других с самого начала с информацией, не относящейся к Мерсенну.
Поскольку использование одного и того же алгоритма для генерации случайных чисел и для создания начального начального числа кажется каким-то образом плохой идеей, я подумал о введении некоторого элемента, который не зависит от алгоритма Мерсенна Твистера. Например, я мог бы XOR идентифицировать поток в каждом элементе начального начального вектора. Делает ли это что-то лучше?
Поделиться одним PRNG среди потоков.
Это позволило бы убедиться, что существует только одна последовательность со всеми известными и желаемыми свойствами Mersenne Twister. Но издержки блокировки, необходимые для управления доступом к этому генератору, меня несколько волнуют. Поскольку я не нашел никаких доказательств обратного, я предполагаю, что я, как пользователь библиотеки, буду нести ответственность за предотвращение одновременного доступа к PRNG.
Предварительно сгенерируйте все случайные числа.
Это позволит одному потоку сгенерировать все необходимые 1М случайные числа заранее, чтобы впоследствии использовать их в разных потоках. Требуемый объем памяти 4M будет небольшим по сравнению с общим приложением. Что меня больше всего беспокоит в этом подходе, так это то, что генерация случайных чисел сама по себе не является параллельной. Весь этот подход также не слишком хорошо масштабируется.
Какой из этих подходов вы бы предложили и почему? Или у вас есть другое предложение?
Знаете ли вы, какие из моих опасений оправданы, а какие просто связаны с тем, что я не понимаю, как все работает на самом деле?
Я бы использовал один экземпляр, чтобы посеять другие. Я уверен, что вы можете сделать это безопасно довольно легко.
Я хотел бы пойти с # 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 вместо этого.
Вы могли бы использовать PRNG с другой алгебраической структурой для заполнения различных PRNG. Например. некоторая последовательность хэшей MD5.
Однако я бы выбрал # 5. Если это работает, тогда это хорошо. Если это не так, вы все равно можете оптимизировать его.
Дело в том, чтобы создать хорошо PRNG намного сложнее, чем можно было ожидать. Хороший PRNG для многопоточных приложений — это, скорее всего, предмет исследования.
Если количество процессоров достаточно низкое, вы можете избежать скачкообразной лягушки. Например. если у вас есть 4 ядра, инициализируйте все с одинаковыми значениями, но продвиньте основной 1 PRNG на 1, # 2 на и # 3 на 3. Затем продвигайтесь всегда на 4 шага, когда вам нужен новый номер.
Семенная нить 1 с 1, семенная нить 2 с 2 и т. Д.
Если вам нужен Монте-Карло, это даст вам воспроизводимые результаты, его легко отследить и реализовать.
Взгляните на следующую статью: Динамическое создание генераторов псевдослучайных чисел и сопутствующая реализация: Динамический Создатель. Это решает эту точную проблему.
Если вы действительно хотите быть математически правильными, используйте функции перехода, предоставленные авторами алгоритма SFMT. Функции перехода гарантируют минимальное количество последовательностей между двумя различными потоками PRNG.
На практике, однако, будет достаточно инициализации / dev / urandom.
Я бы сказал, что № 3 — победитель. Заполните каждый поток чем-то вроде processID или threadID; хотя технически возможно, что вы могли бы перекрываться, это крайне маловероятно. Даже последовательные числа не должны быть связаны с точки зрения начальных чисел, как только вы выберете однозначные цифры (я не знаю алгоритм Твистера, но худший ГРП, который я видел, был выше 7). Миллион PRNG не так много по сравнению с большинством уравнений PRNG.
Наконец, вы можете проверить довольно легко. Проверить прошлой начальное число, сгенерированное каждым потоком против всех чисел в другом потоке. Если семя появляется в потоке, то проверьте предыдущий номер, сгенерированный в каждом потоке; если они также совпадают, то у вас есть коллизия, и вам нужно заново посеять потоки и повторить попытку.
Существует реализация (и опубликованная статья), конкретно касающаяся использования Twister Mersenne для параллельных вычислений. Это авторы оригинального МТ. Они называют его «Динамический Создатель», и это можно найти здесь:
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html
Это было бы очень хорошим местом для изучения вашего конкретного использования MT19937, особенно бумаги там.