Параллельная генерация случайных чисел

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

SeedSequence порождение

NumPy позволяет создавать новые (с очень высокой вероятностью) независимые BitGenerator и Generator экземпляры через их spawn() метод. Это порождение реализовано SeedSequence используется для инициализации случайного потока генераторов битов.

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

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

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

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

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 не требуется. Вышеуказанное streams может быть порождён напрямую из родительского генератора через spawn:

parent_rng = default_rng(12345)
streams = parent_rng.spawn(10)

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

grandchildren = streams[0].spawn(4)

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

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

[1]

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

[2]

В этом вычислении мы можем в основном игнорировать количество чисел, взятых из каждого потока. См. Обновление PCG64 с PCG64DXSM для технических деталей о PCG64. Другие предоставляемые нами ГСЧ имеют встроенную дополнительную защиту, которая предотвращает перекрытия, если SeedSequence пулы отличаются хотя бы немного. PCG64DXSM имеет \(2^{127}\) отдельные циклы, определяемые сидом в дополнение к позиции в \(2^{128}\) длинный период для каждого цикла, поэтому нужно как попасть на тот же цикл или близко к нему и засеять близлежащую позицию в цикле. Philox имеет полностью независимые циклы, определяемые seed. SFC64 включает 64-битный счётчик, поэтому каждый уникальный сид как минимум \(2^{64}\) итераций от любого другого начального значения. И наконец, MT19937 имеет просто невообразимо огромный период. Получение коллизии внутри SeedSequence это способ, которым будет наблюдаться сбой.

Последовательность целочисленных начальных значений

Как обсуждалось в предыдущем разделе, SeedSequence может принимать не только целочисленное начальное значение, но и последовательность произвольной длины (неотрицательных) целых чисел. При небольшой осторожности можно использовать эту возможность для проектирования ad hoc схемы для получения безопасных параллельных потоков PRNG с аналогичными гарантиями безопасности, как при порождении.

Например, один распространённый случай использования — когда рабочий процесс получает одно корневое начальное число для всего вычисления, а также целочисленный идентификатор рабочего процесса (или что-то более детальное, например идентификатор задания, идентификатор пакета или что-то подобное). Если эти идентификаторы создаются детерминированно и уникально, то можно получить воспроизводимые параллельные потоки ГСЧ, комбинируя идентификатор и корневое начальное число в списке.

# default_rng() and each of the BitGenerators use SeedSequence underneath, so
# they all accept sequences of integers as seeds the same way.
from numpy.random import default_rng

def worker(root_seed, worker_id):
    rng = default_rng([worker_id, root_seed])
    # Do work ...

root_seed = 0x8c3c010cb4754c905776bdac5ee7501
results = [worker(root_seed, worker_id) for worker_id in range(10)]

Это можно использовать для замены ряда небезопасных стратегий, которые использовались в прошлом и пытались объединить корневое начальное значение и ID обратно в одно целочисленное начальное значение. Например, часто можно увидеть, как пользователи добавляют ID рабочего к корневому начальному значению, особенно с устаревшим RandomState код.

# UNSAFE! Do not do this!
worker_seed = root_seed + worker_id
rng = np.random.RandomState(worker_seed)

Это правда, что для любого запуска параллельной программы, построенной таким образом, каждый рабочий процесс будет иметь отдельные потоки. Однако весьма вероятно, что множественные вызовы программы с разными сидами получат перекрывающиеся наборы сидов рабочих процессов. Нередко (по собственному опыту автора) изменять корневой сид всего на одно или два приращения при выполнении этих повторных запусков. Если сиды рабочих процессов также выводятся небольшими приращениями идентификатора рабочего процесса, то подмножества рабочих процессов будут возвращать идентичные результаты, вызывая смещение в общем ансамбле результатов.

Объединение идентификатора рабочего процесса и корневого сида в виде списка целых чисел устраняет этот риск. Практики ленивого сидирования все еще будут достаточно безопасными.

Эта схема требует, чтобы дополнительные идентификаторы были уникальными и детерминированно созданными. Это может потребовать координации между рабочими процессами. Рекомендуется размещать изменяющиеся идентификаторы до неизменяемое начальное значение. spawn добавляет целые числа после предоставленного пользователем начального значения, поэтому если вы можете смешивать и это ad hoc механизм и порождение, или передача ваших объектов в библиотечный код, который может порождать процессы, то немного безопаснее добавлять идентификаторы рабочих процессов в начало, а не в конец, чтобы избежать коллизий.

# Good.
worker_seed = [worker_id, root_seed]

# Less good. It will *work*, but it's less flexible.
worker_seed = [root_seed, worker_id]

С учётом этих оговорок, гарантии безопасности от коллизий примерно такие же, как при порождении, обсуждаемые в предыдущем разделе. Алгоритмические механизмы те же.

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

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}\) to \(2^{128}\). Кроме того, как если бы выборки также зависят от размера случайного числа по умолчанию, генерируемого конкретным BitGenerator. BitGenerators, которые поддерживают jumped, наряду с периодом BitGenerator, размером скачка и битами в стандартном беззнаковом случайном числе, перечислены ниже.

BitGenerator	Period	Размер прыжка	Битов на выборку
MT19937	\(2^{19937}-1\)	\(2^{128}\)	32
PCG64	\(2^{128}\)	\(~2^{127}\) ([3])	64
PCG64DXSM	\(2^{128}\)	\(~2^{127}\) ([3])	64
Philox	\(2^{256}\)	\(2^{128}\)	64

[3] (1,2)

Размер скачка равен \((\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), иначе он воссоздал бы те же потоки. С другой стороны, если вы тщательно сконструируете потоки, то гарантированно получите потоки, которые не перекрываются.