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

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

Создание 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}$ отдельных циклов, определяемых начальным значением, помимо длительного периода для каждого цикла, поэтому необходимо попасть в или близко к одному и тому же циклу *и* задать близкую позицию в цикле. 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	Период	Размер перехода	Биты
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.19/reference/random/parallel.html