Параллельное генерирование случайных чисел

Реализованы три стратегии, которые можно использовать для получения воспроизводимых псевдослучайных чисел в нескольких процессах (локальных или распределённых).

Создание SeedSequence

SeedSequence реализует алгоритм для обработки предоставленного пользователем начального значения, обычно в виде целого числа определённого размера, и преобразования его в начальное состояние для BitGenerator. Используются хеширующие методы для того, чтобы убедиться, что плохое начальное значение преобразуется в качественное начальное состояние (по крайней мере, с очень высокой вероятностью).

Например, MT19937 имеет состояние, состоящее из 624 uint32 целых чисел. Примитивный способ использования 32-битного начального значения — просто установить последний элемент состояния в 32-битное начальное значение и оставить остальные 0. Это допустимое состояние для MT19937, но не хорошее. Алгоритм Mersenne Twister страдает, если слишком много нулей. Аналогично, два смежных 32-битных начальных значения (т.е. 12345 и 12346) приведут к очень похожим потокам.

SeedSequence избегает этих проблем, используя последовательности целочисленных хешей с хорошими свойствами разброса, чтобы гарантировать, что изменение любого бита на входе имеет примерно 50% шанс изменить любой бит на выходе. Два близких начальных значения приведут к очень разным начальным состояниям (с очень высокой вероятностью). Также она построена так, что вы можете предоставить целые числа произвольной длины или списки целых чисел. SeedSequence возьмёт все предоставленные биты и перемешает их, чтобы создать столько битов, сколько необходимо потребляющему BitGenerator для инициализации.

Эти свойства позволяют безопасно смешивать обычное начальное значение пользователя с простыми инкрементирующими счётчиками, чтобы получить BitGenerator состояния, которые (с очень высокой вероятностью) независимы друг от друга. Мы можем упаковать это всё в удобный в использовании и трудно используемый API.

from numpy.random import SeedSequence, default_rng

ss = SeedSequence(12345)

# Spawn off 10 child SeedSequences to pass to child processes.
child_seeds = ss.spawn(10)
streams = [default_rng(s) for s in child_seeds]

Объекты-потомки SeedSequence также могут генерировать потомков и так далее. У каждого SeedSequence его позиция в дереве сгенерированных SeedSequence объектов смешивается с предоставленным пользователем начальным значением для генерации независимых (с очень высокой вероятностью) потоков.

grandchildren = child_seeds[0].spawn(4)
grand_streams = [default_rng(s) for s in grandchildren]

Эта функция позволяет принимать локальные решения о том, как и когда разделять потоки, не требуя координации между процессами. Вам не нужно предварительно выделять память, чтобы избежать перекрытий, или запрашивать потоки из общей глобальной службы. Этот общий схему «хеширования дерева» не уникальна для numpy, но пока не широко распространена. Python имеет всё более гибкие механизмы для паралелизации, и эта схема прекрасно вписывается в подобные применения.

Используя эту схему, можно оценить верхнюю границу вероятности коллизии, если известно количество сгенерированных потоков. SeedSequence хеширует свои входы, как начальное значение, так и путь по дереву порождения, до 128-битного пула по умолчанию. Вероятность коллизии в этом пуле, пессимистически оцененная ([1]), будет примерно $n^2*2^{-128}$ , где n — количество сгенерированных потоков. Если программа использует агрессивное количество, скажем, миллион потоков, приблизительно $2^{20}$ , то вероятность, что хотя бы пара из них идентична, составляет примерно $2^{-88}$ , что находится в области, которую можно спокойно игнорировать ([2]).

[1]

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

[2] В этом расчёте мы можем проигнорировать количество чисел, взятых из каждого потока. Каждый из предоставляемых нами генераторов псевдослучайных чисел имеет дополнительную защиту, предотвращающую перекрытия, если пулы SeedSequence отличаются хотя бы немного. PCG64 имеет $2^{127}$ отдельных циклов, определяемых семеном, помимо длительного периода $2^{128}$ для каждого цикла, поэтому необходимо попасть в один и тот же цикл и иметь близкую позицию в этом цикле. Philox имеет полностью независимые циклы, определяемые семеном. SFC64 включает 64-битный счётчик, поэтому каждый уникальный семян отделён как минимум $2^{64}$ итерациями от любого другого семени. И наконец, MT19937 имеет просто невероятно большой период. Наблюдение за ошибкой произойдёт, если произойдёт столкновение внутри SeedSequence.

Независимые потоки

Philox — это генератор псевдослучайных чисел на основе счётчика, который генерирует значения путём шифрования нарастающего счётчика с помощью слабых криптографических примитивов. Семя определяет ключ, используемый для шифрования. Уникальные ключи создают уникальные, независимые потоки. Philox позволяет обойти алгоритм инициализации, чтобы напрямую задать 128-битный ключ. Аналогичные, но разные, ключи всё равно создадут независимые потоки.

import secrets
from numpy.random import Philox

# 128-bit number as a seed
root_seed = secrets.getrandbits(128)
streams = [Philox(key=root_seed + stream_id) for stream_id in range(10)]

Эта схема требует избегать повторного использования идентификаторов потоков. Это может потребовать координации между параллельными процессами.

Переход к состоянию BitGenerator

jumped перемещает состояние BitGenerator так, будто было сгенерировано большое количество случайных чисел, и возвращает новый экземпляр с этим состоянием. Конкретное количество извлечений варьируется в зависимости от BitGenerator и находится в диапазоне от $2^{64}$ до $2^{128}$ . Кроме того, мнимые извлечения также зависят от размера стандартного случайного числа, производимого конкретным BitGenerator. BitGenerator, которые поддерживают jumped, а также период BitGenerator, размер перехода и биты в стандартном беззнаковом случайном числе перечислены ниже.

BitGenerator	Период	Размер перехода	Биты
MT19937	$2^{19937}$	$2^{128}$	32
PCG64	$2^{128}$	$~2^{127}$ ([3])	64
Philox	$2^{256}$	$2^{128}$	64

[3]

Размер перехода — $(\phi-1)*2^{128}$ , где $\phi$ — золотое сечение. Поскольку переходы охватывают период, фактические расстояния между соседними потоками будут медленно уменьшаться по сравнению с размером перехода, но использование золотого сечения таким образом — это классический метод построения последовательности с низким расбросом, который оптимально распределяет состояния по периоду. Вы не сможете перепрыгнуть достаточно далеко, чтобы эти расстояния уменьшились настолько, чтобы они перекрывались за всю вашу жизнь.

jumped может использоваться для создания длинных блоков, которые должны быть достаточно длинными, чтобы не перекрываться.

import secrets
from numpy.random import PCG64

seed = secrets.getrandbits(128)
blocked_rng = []
rng = PCG64(seed)
for i in range(10):
    blocked_rng.append(rng.jumped(i))

При использовании jumped, необходимо следить за тем, чтобы не перейти к потоку, который уже использовался. В приведенном выше примере нельзя было бы позже использовать blocked_rng[0].jumped(), так как это перекрывалось бы с blocked_rng[1]. Как и с независимыми потоками, если основной процесс хочет разделить ещё 10 потоков путём перехода, то он должен начать с range(10, 20), иначе он создаст те же самые потоки. С другой стороны, если вы тщательно строите потоки, то гарантированно получите потоки, которые не перекрываются.

© 2005–2019 NumPy Developers
Licensed under the 3-clause BSD License.
https://docs.scipy.org/doc/numpy-1.17.0/reference/random/parallel.html