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

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

Создание 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

В этом расчёте мы в основном можем проигнорировать количество чисел, извлечённых из каждого потока. См. Модернизация PCG64 с PCG64DXSM для технических подробностей о PCG64. Другие предлагаемые нами генераторы псевдослучайных чисел имеют дополнительную защиту, которая предотвращает наложение, если пулы SeedSequence отличаются хотя бы немного. PCG64DXSM имеет \(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, размером перескока и битами в стандартном неподписанном случайном числе перечислены ниже.

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