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

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

Генерация SeedSequence

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

Например, MT19937 имеет состояние, состоящее из 624 uint32 целых чисел. Примитивный способ использования 32-битного целого числа в качестве семени — установить последний элемент состояния на 32-битное семя и оставить остальные нулями. Это является допустимым состоянием для 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–2020 NumPy Developers
Licensed under the 3-clause BSD License.
https://numpy.org/doc/1.18/reference/random/parallel.html