Энтропия и параллельный запуск генератора случайных чисел

Question

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

Наборы данных достаточно велики, поэтому я бы хотел распараллелить их, используя openMP, чтобы ускорить процесс. Проблема возникает, когда я хочу иметь несколько PRNG. У меня есть свой собственный класс PRNG, основанный на методе NR по модулю (я думаю, rand4), но я не уверен, как правильно посеять PRNG, чтобы обеспечить соответствующую энтропию

Normalliy Я бы сделал что-то подобное

prng.initTimer();

Но если у меня есть массив prngs, по одному на рабочий поток, то я не могу просто вызывать initTimer для каждого экземпляра - таймер может не измениться, а закрывающиеся таймеры могут ввести корреляцию.

Мне нужно защищаться от естественных корреляций, а не от злоумышленников (это экспериментальные данные), поэтому мне нужен безопасный способ заполнения массива rng.

Я думал о простом использовании

prng[0].initTimer()
for(int i=1; i<numRNGs; i++)
     prng[i].init(prng[0].getRandNum());

Затем вызывается мой цикл, но я не уверен, что это приведет к корреляциям в методе по модулю.

Answer 1

Заполнение PRNG не обязательно создает независимые потоки. Вы должны заполнить только первый экземпляр (назовите его ссылкой) и инициализировать оставшиеся экземпляры путем быстрой пересылки ссылочного экземпляра. Это работает только в том случае, если вы знаете, сколько случайных чисел будет использовать каждый поток, и доступен алгоритм быстрой пересылки.

Я не знаю много о вашем rand4 (гуглил, но ничего конкретного не вышло), но вы не должны предполагать, что можно создавать независимые потоки только путем заполнения. Вы, вероятно, хотите использовать другой (лучший) PRNG. Взгляните на ХОРОШО . Он быстрый, обладает хорошими статистическими свойствами и разработан хорошо известными специалистами. WELL 512 и 1024 являются одними из самых быстрых доступных PRNG, и оба имеют огромные периоды. Вы можете инициализировать несколько экземпляров WELL с различными начальными значениями для создания независимых потоков. Благодаря огромному периоду, практически нет шансов, что ваши PRNG будут генерировать перекрывающиеся потоки случайных чисел.

Если ваши PRNG часто вызываются, остерегайтесь ложного обмена. В этой статье Херба Саттера объясняется, как ложный обмен может снизить производительность многоядерных процессоров. Упаковка нескольких PRNG в непрерывный массив - почти идеальный рецепт для ложного обмена. Чтобы избежать ложного совместного использования, либо добавьте заполнение между PRNG, либо выделите PRNG в куче / свободном хранилище. В последнем случае каждый ГСЧ должен распределяться индивидуально с использованием какого-либо согласованного распределителя. Ваш компилятор должен предоставить версию выровненного malloc. Проверьте документы (ну, поиск в Google на самом деле быстрее, чем чтение руководств). Visual C ++ имеет _aligned_malloc, GCC имеет memalign и posix_memalign. Значение aliment должно быть кратным размеру строки кэша ЦП. Обычной практикой является выравнивание по 128-байтовым границам. Для переносимого решения вы можете использовать распределитель, выровненный по кэш-памяти TBB.

Answer 2

Я думаю, это зависит от свойств вашего PRNG.Обычно слабые стороны PRNG - это меньшая энтропия в младших битах и ​​меньшая энтропия для первых n значений.Поэтому я думаю, что вы должны проверить свой PRNG на наличие таких недостатков и соответствующим образом изменить свой код.

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

Например, запустите PRNG и суммируйте первые 100 значений по модулю 11 вашего PRNG, повторите это R раз.Если общая сумма сильно отличается от ожидаемой (5 * 100 * R), ваш PRNG страдает одним или обоими недостатками, упомянутыми выше.

Не зная ничего о PRNG, я бы чувствовал себя безопаснее, используя что-то подобное:

prng[0].initTimer();
// Throw the first 100 values away
for(int i=1; i < 100; i++)
   prng[0].getRandNum();
// Use only higher bits for seed values (assuming 32 bit size)
for(int i=1; i<numRNGs; i++)
   prng[i].init(((prng[0].getRandNum() >> 16) << 16)
               + (prng[0].getRandNum() >> 16));

Но, конечно, это предположения о PRNG.С идеальным PRNG ваш подход должен работать без ошибок.

Answer 3

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

В качестве альтернативы, если вы работаете в Unix-подобной системе с /dev/random, вы можете просто прочитать с этого устройства, чтобы получить последовательность случайных чисел для использования в качестве ваших семян.