Обновление PCG64 с PCG64DXSM#

Использование PCG64 BitGenerator В контексте массового параллелизма были показаны статистические слабости, которые не были очевидны при первом выпуске в numpy 1.17. Большинство пользователей никогда не заметят эту слабость и могут безопасно продолжать использовать PCG64Мы представили новый PCG64DXSM BitGenerator который в конечном итоге станет новым значением по умолчанию BitGenerator реализация, используемая default_rng в будущих выпусках. PCG64DXSM решает статистическую слабость, сохраняя производительность и особенности PCG64.

Это затрагивает меня?#

Если вы

  1. использовать только один Generator экземпляр,

  2. использовать только RandomState или функций в numpy.random,

  3. использовать только PCG64.jumped метод для генерации параллельных потоков,

  4. явно использовать BitGenerator кроме PCG64,

тогда эта слабость вас вообще не затрагивает. Продолжайте.

Если вы используете умеренное количество параллельных потоков, созданных с помощью default_rng или SeedSequence.spawn, в тысячах, то вероятность наблюдения этой слабости ничтожно мала. Вы можете продолжать использовать PCG64 удобно.

Если вы используете очень большое количество параллельных потоков, в миллионах, и генерируете большие объёмы чисел из каждого, то вероятность наблюдения этой слабости может стать не пренебрежимо малой, хотя и остаётся небольшой. Примером такого случая использования может быть очень большая распределённая задача обучения с подкреплением с миллионами длинных развёрток Монте-Карло, каждая из которых генерирует миллиарды случайных чисел. Такие случаи использования должны рассмотреть использование PCG64DXSM явно или другой современный BitGenerator как SFC64 или Philox, но маловероятно, что какие-либо старые результаты, которые вы могли вычислить, недействительны. В любом случае, слабость — это своего рода Парадокс дней рождения коллизия. То есть одна пара параллельных потоков из миллионов, рассматриваемая вместе, может не пройти строгий набор статистических тестов случайности. Остальные миллионы потоков будут совершенно нормальными, и влияние плохой пары на весь расчет, скорее всего, будет подавлено остальными потоками в большинстве приложений.

Технические детали#

Как и многие алгоритмы ГПСЧ, PCG64 строится из функции перехода, которая обновляет 128-битное состояние, и выходной функции, которая смешивает 128-битное состояние в 64-битное целое число для вывода. Один из руководящих принципов дизайна семейства PRNG PCG — балансировать вычислительную стоимость (и силу псевдослучайности) между функцией перехода и выходной функцией. Функция перехода — это 128-битный линейный конгруэнтный генератор (LCG), который состоит из умножения 128-битного состояния на фиксированную константу умножения и затем добавления выбранного пользователем приращения в 128-битной модульной арифметике. LCG — это хорошо изученные PRNG с известными слабостями, хотя 128-битные LCG достаточно велики, чтобы пройти строгие статистические тесты самостоятельно, только с тривиальной выходной функцией. Выходная функция PCG64 предназначен для исправления некоторых известных недостатков, выполняя «достаточно» перемешивания битов, чтобы помочь в статистических свойствах, не добавляя слишком много вычислительных затрат.

Одним из известных недостатков является то, что продвижение состояния LCG на количество шагов, равное степени двойки (bg.advance(2**N)) оставит нижнюю N биты идентичны состоянию, которое только что было оставлено. Для одного потока, извлекаемого последовательно, это не имеет большого значения. Оставшиеся \(128-N\) битов предоставляют достаточно псевдослучайности, которая будет смешана для любых практических N которые можно наблюдать в одном потоке, поэтому не нужно беспокоиться об этом, если вы используете только один поток в своём приложении. Аналогично, PCG64.jumped метод использует тщательно подобранное количество шагов, чтобы избежать создания этих коллизий. Однако, как только вы начинаете создавать «случайно инициализированные» параллельные потоки, либо используя энтропию ОС вызовом default_rng повторно или с использованием SeedSequence.spawn, тогда нам нужно рассмотреть, сколько младших битов должны «столкнуться», чтобы создать плохую пару потоков, а затем оценить вероятность создания такого столкновения. Эмпирически, было определено, что если разделить нижние 58 бит состояния и разделить инкремент, то пара потоков при чередовании будет давать сбой PractRand за разумное время после извлечения нескольких гигабайт данных. Следуя стандартным расчетам парадокса дней рождения для коллизии в 58 бит, мы видим, что можем создать \(2^{29}\), или около полумиллиарда потоков, когда вероятность такого столкновения становится высокой. Полмиллиарда потоков — это довольно много, и количество данных, которое каждый поток должен извлечь, прежде чем статистические корреляции станут заметными даже для самых строгих PractRand тестов составляет гигабайты. Но это на горизонте для очень больших приложений, таких как распределённое обучение с подкреплением. Есть основания ожидать, что даже в этих приложениях столкновение, вероятно, не окажет практического влияния на общий результат, поскольку статистическая проблема ограничена только столкнувшейся парой.

Теперь рассмотрим случай, когда приращение не ограничено одинаковым значением. Наша реализация PCG64 инициализирует как состояние, так и инкремент; то есть два вызова default_rng (почти наверняка) имеют разные состояния и приращения. При нашем первом выпуске мы считали, что наличие засеянного приращения обеспечит определённую дополнительную защиту, что нужно будет быть «близким» как в пространстве состояний, так и в пространстве приращений, чтобы наблюдать корреляции (PractRand сбоев) в паре потоков. Если бы это было правдой, то "узким местом" для коллизий был бы размер пула энтропии 128 бит внутри SeedSequence (и 128-битные коллизии находятся в категории "невероятно маловероятных"). К сожалению, это не так.

Одно из известных свойств LCG заключается в том, что разные приращения создают различные . Это формализованная версия консенсуса, в которой голоса +1 указывают на согласие, -1 — вето (и должны сопровождаться обоснованием, как указано выше), а также можно голосовать дробно (например, -0.5, +0.5), если хочется выразить мнение без полного вето. Эти числовые голоса также часто используются неформально как способ получить общее представление о чувствах людей по какому-либо вопросу и обычно не должны рассматриваться как формальные голоса. Формальное голосование происходит только если оно явно объявлено, и если это происходит, то голосование должно быть открыто достаточно долго, чтобы все заинтересованные члены Совета имели возможность ответить — как минимум одну неделю. \(2^{128}\) различные 128-битные состояния. Два LCG с разными инкрементами связаны тем, что можно «повернуть» орбиту первого LCG (продвинуть её на число шагов, которое мы можем вычислить из двух инкрементов), так что тогда оба LCG всегда будут иметь одинаковое состояние, с точностью до аддитивной константы и, возможно, инверсии битов. Если затем итерировать оба потока синхронно, то состояния будут всегда остаются связанными той же самой аддитивной константой (и инверсией, если присутствует). Напомним, что PCG64 конструируется как из функции перехода (LCG), так и из выходной функции. Ожидалось, что скремблирующий эффект выходной функции будет достаточно сильным, чтобы сделать различные потоки практически независимыми (т.е. "проходящими PractRand тесты) если два приращения не были патологически связаны друг с другом (например, 1 и 3). Выходная функция XSL-RR стандартного на тот момент алгоритма PCG, который мы реализовали в PCG64 оказывается слишком слабым, чтобы компенсировать 58-битное столкновение базового LCG, которое мы описали выше. Для любой заданной пары приращений размер «сталкивающегося» пространства состояний одинаков, поэтому для этой слабости дополнительная различимость, обеспечиваемая приращениями, не превращается в дополнительную защиту от статистических корреляций, которые PractRand может обнаружить.

вместо) делает превратить дополнительную различимость, предоставляемую разными приращениями, в дополнительную защиту от этих низкобитных коллизий. Для Автор PCG кредит, она разработала более сильную выходную функцию в ответ на связанные обсуждения во время долгого создания нового BitGenerator система. Мы, разработчики NumPy, решили быть «консервативными» и использовать вариант XSL-RR, который на тот момент прошёл более длительный период тестирования. Функция вывода DXSM использует конструкцию «xorshift-умножение», применяемую в сильных целочисленных хэшах, которая имеет гораздо лучшие свойства лавинного эффекта, чем функция вывода XSL-RR. Хотя существуют «патологические» пары приращений, которые вызывают «плохие» аддитивные константы, связывающие два потока, подавляющее большинство пар вызывают «хорошие» аддитивные константы, которые превращают просто различные потоки состояний LCG в практически независимые выходные потоки. Действительно, теперь утверждение, которое мы когда-то делали о PCG64 фактически верно для PCG64DXSM: возможны коллизии, но оба потока должны одновременно быть «близкими» в 128-битном пространстве состояний и «близко» в 127-битном пространстве приращений, так что это было бы менее вероятно, чем ничтожный шанс столкновения во внутреннем 128-битном SeedSequence пул. Функция вывода DXSM более вычислительно интенсивна, чем XSL-RR, но некоторые оптимизации в LCG более чем компенсируют потерю производительности на большинстве машин, поэтому PCG64DXSM является хорошим, безопасным обновлением. Конечно, существует бесконечное количество более сильных выходных функций, которые можно рассмотреть, но большинство из них будут иметь большую вычислительную стоимость, а выходная функция DXSM теперь получила много циклов CPU тестирования через PractRand в настоящее время.