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

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

Генерация SeedSequence

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

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