Comments 2
Спасибо за статью! Однако хочу заметить, что генерация псевдослучайных чисел — это по своей природе последовательный процесс, который обычно не распараллеливается (кроме некоторых специальных случаев, например, в криптографии: AES-CTR или Yarrow). Последовательный он потому, что по определению предусматривает возможность полностью воссоздать всю последовательность псевдослучайных чисел, задав исходное зерно (seed).
Генератор обычно устроен таким образом: он хранит в себе некоторое состояние, при каждом обращении он генерирует новое число, исходя из этого состояния, затем меняет состояние. Таким образом, даже MKL-евский генератор имеет ограничение по эффективности.
Благодаря вашей статье, я пошел разбираться в технологии бутстреппинга. Оказалось это — отличная, простая и очень удобная техника. Однако, поскольку идентичность результата при одном и том же зерне в вашем случае не важна, я бы предложил другой подход. Создал бы собственный класс генератора случайных чисел, чтобы каждый поток мог создать себе экземпляр такого класса с разным зерном. Для статистического моделирования я бы взял самый простой генератор Multiply with carry. Сам я обычно использую в качестве генератора ПСЧ алгоритм поточного шифрования RC4. Он имеет лучшие статистические характеристики, чем встроенный генератор, и чем MWC. И к тому же RC4 имеет очень простую реализацию, порядка десяти строчек кода (собственно для самой криптографии он уже устарел, хотя и используется по умолчанию многими серверами на SSL).
После того, как генератор есть, я бы дал каждому потоку по своему экземпляру класса генератора, инициализированного разными зернами (лучше всего использовать умножение значения таймера системы на уникальное для потока простое число, так больше энтропии). После этого каждый параллельный поток работал бы со своим генератором и, конечно, загрузил бы все ядра на полную катушку.
Генератор обычно устроен таким образом: он хранит в себе некоторое состояние, при каждом обращении он генерирует новое число, исходя из этого состояния, затем меняет состояние. Таким образом, даже MKL-евский генератор имеет ограничение по эффективности.
Благодаря вашей статье, я пошел разбираться в технологии бутстреппинга. Оказалось это — отличная, простая и очень удобная техника. Однако, поскольку идентичность результата при одном и том же зерне в вашем случае не важна, я бы предложил другой подход. Создал бы собственный класс генератора случайных чисел, чтобы каждый поток мог создать себе экземпляр такого класса с разным зерном. Для статистического моделирования я бы взял самый простой генератор Multiply with carry. Сам я обычно использую в качестве генератора ПСЧ алгоритм поточного шифрования RC4. Он имеет лучшие статистические характеристики, чем встроенный генератор, и чем MWC. И к тому же RC4 имеет очень простую реализацию, порядка десяти строчек кода (собственно для самой криптографии он уже устарел, хотя и используется по умолчанию многими серверами на SSL).
После того, как генератор есть, я бы дал каждому потоку по своему экземпляру класса генератора, инициализированного разными зернами (лучше всего использовать умножение значения таймера системы на уникальное для потока простое число, так больше энтропии). После этого каждый параллельный поток работал бы со своим генератором и, конечно, загрузил бы все ядра на полную катушку.
Руслан, спасибо за интерес и совет!
«Генератор обычно устроен таким образом: он хранит в себе некоторое состояние, при каждом обращении он генерирует новое число, исходя из этого состояния, затем меняет состояние. Таким образом, даже MKL-евский генератор имеет ограничение по эффективности.» — я в курсе )) Речь была о том, поддерживает ле библиотека беспрепятственное одновременное получение «следующего состояния» от нескольких экземпляров с разными стартовыми значениями («сидами»). Runtime-библиотека VB6, например, не поддерживала, MKL — поддерживала. Также речь была о возможности, сгенерировав массив последовательных чисел, разбить его на N подмассивов так, чтобы они были взаимно некореллированы. В приведённой статье авторами MKL расписано, почему всё не так просто, как кажется, и предоставлены 2 подхода к решению этого вопроса.
«После того, как генератор есть, я бы дал каждому потоку по своему экземпляру класса генератора, инициализированного разными зернами (лучше всего использовать умножение значения таймера системы на уникальное для потока простое число, так больше энтропии). После этого каждый параллельный поток работал бы со своим генератором и, конечно, загрузил бы все ядра на полную катушку.» — именно так я и сделал ))
«Генератор обычно устроен таким образом: он хранит в себе некоторое состояние, при каждом обращении он генерирует новое число, исходя из этого состояния, затем меняет состояние. Таким образом, даже MKL-евский генератор имеет ограничение по эффективности.» — я в курсе )) Речь была о том, поддерживает ле библиотека беспрепятственное одновременное получение «следующего состояния» от нескольких экземпляров с разными стартовыми значениями («сидами»). Runtime-библиотека VB6, например, не поддерживала, MKL — поддерживала. Также речь была о возможности, сгенерировав массив последовательных чисел, разбить его на N подмассивов так, чтобы они были взаимно некореллированы. В приведённой статье авторами MKL расписано, почему всё не так просто, как кажется, и предоставлены 2 подхода к решению этого вопроса.
«После того, как генератор есть, я бы дал каждому потоку по своему экземпляру класса генератора, инициализированного разными зернами (лучше всего использовать умножение значения таймера системы на уникальное для потока простое число, так больше энтропии). После этого каждый параллельный поток работал бы со своим генератором и, конечно, загрузил бы все ядра на полную катушку.» — именно так я и сделал ))
Sign up to leave a comment.
Быстрая генерация массивов случайных чисел для задач имитационного моделирования, статистического оценивания и создания повторной выборки