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

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

grandchildren = streams[0].spawn(4)

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

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

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

Как обсуждалось в предыдущем разделе, SeedSequence может принимать не только целое семя, но и произвольную последовательность (неотрицательных) целых чисел. При соблюдении определенных мер предосторожности можно использовать эту функцию для разработки специальных схем получения безопасных потоков параллельных ПСЧ с аналогичными гарантиями безопасности, как при разветвлении.

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

# 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)]

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

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

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

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

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

# 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)]

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

Переход к состоянию генератора случайных бит

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

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