使用 PCG64DXSM 升级 PCG64#

在海量并行环境中使用 PCG64 BitGenerator 已被证明存在最初在 numpy 1.17 中发布时未发现的统计弱点。大多数用户永远不会遇到此弱点，并且可以安全地继续使用 PCG64。我们引入了一个新的 PCG64DXSM BitGenerator，它最终将成为 default_rng 在未来版本中使用的新的默认 BitGenerator 实现。 PCG64DXSM 解决了统计弱点，同时保留了 PCG64 的性能和功能。

这会影响我吗？#

如果您

  1. 仅使用单个 Generator 实例，

  2. 仅使用 RandomState 或 numpy.random 中的函数，

  3. 仅使用 PCG64.jumped 方法生成并行流，

  4. 显式使用除 PCG64 之外的 BitGenerator，

那么此弱点根本不会影响您。继续即可。

如果您使用使用 default_rng 或 SeedSequence.spawn 创建的中等数量的并行流（以千计），那么观察到此弱点的可能性微乎其微。您可以继续舒适地使用 PCG64。

如果您使用非常大量的并行流（以百万计），并从每个流中提取大量数字，那么观察到此弱点的可能性可能会变得不可忽略，尽管仍然很小。此类用例的一个示例是具有数百万个长蒙特卡罗模拟的非常大的分布式强化学习问题，每个模拟都会生成数十亿个随机数绘制。此类用例应考虑显式使用 PCG64DXSM 或其他现代 BitGenerator，如 SFC64 或 Philox，但您可能计算的任何旧结果都不太可能无效。无论如何，此弱点是一种 生日悖论 碰撞。也就是说，数百万个并行流中的单个对，如果放在一起考虑，可能会在一套严格的随机性统计测试中失败。其余数百万个流都将完全正常，并且在大多数应用程序中，不良对对整个计算的影响很可能被其余流所淹没。

技术细节#

与许多 PRNG 算法一样，PCG64 由一个转换函数（推进 128 位状态）和一个输出函数（将 128 位状态混合到要输出的 64 位整数中）构成。PCG 系列 PRNG 的指导设计原则之一是在转换函数和输出函数之间平衡计算成本（和伪随机性强度）。转换函数是一个 128 位线性同余生成器 (LCG)，它包括将 128 位状态与固定的乘法常数相乘，然后在 128 位模运算中添加用户选择的增量。LCG 是经过充分分析的 PRNG，具有已知的弱点，尽管 128 位 LCG 足够大，可以独立通过严格的统计测试，并且仅具有简单的输出函数。 PCG64 的输出函数旨在通过进行“足够”的位混淆来修补其中一些已知的弱点，以帮助提高统计属性，而不会增加过多的计算成本。

这些已知弱点之一是，将 LCG 的状态推进以 2 的幂为步长的次数（bg.advance(2**N)）将使较低的 N 位与刚刚离开的状态相同。对于从顺序中提取的单个流，这影响不大。剩余的 \(128-N\) 位提供了大量的伪随机性，这些伪随机性将被混合到任何实际的 N 中，这些 N 可以在一个流中观察到，这就是为什么如果您在应用程序中仅使用一个流，则无需担心这一点的原因。类似地，PCG64.jumped 方法使用精心选择的步数来避免创建这些碰撞。但是，一旦您开始创建“随机初始化”的并行流，无论是通过重复调用 default_rng 来使用操作系统熵还是使用 SeedSequence.spawn，那么我们需要考虑需要多少个较低位需要“碰撞”才能创建一对不良流，然后评估创建此类碰撞的概率。根据经验，如果共享状态的较低 58 位并共享一个增量，那么一对流（交错时）将在合理的时间内在 PractRand 中失败，在绘制几 GB 的数据后。按照此类碰撞的 58 位的标准生日悖论计算，我们可以看到我们可以创建 \(2^{29}\) 或大约 5 亿个流，此时此类碰撞的概率变得很高。5 亿个流相当高，每个流在统计相关性变得明显（即使对于严格的 PractRand 测试）之前需要绘制的数据量也以 GB 为单位。但这对于非常大的应用程序（如分布式强化学习）来说是即将发生的事情。有理由预期，即使在这些应用程序中，碰撞可能也不会对总结果产生实际影响，因为统计问题仅限于碰撞对。

现在，让我们考虑增量不受约束为相同的情况。我们对 PCG64 的实现对状态和增量都进行播种；也就是说，对 default_rng 的两次调用（几乎可以肯定）具有不同的状态和增量。在我们的第一次发布中，我们认为使用播种的增量会提供一定程度的额外保护，即人们必须在状态空间和增量空间中都“接近”才能在流对中观察到相关性（PractRand 失败）。如果属实，那么碰撞的“瓶颈”将是 SeedSequence 内部的 128 位熵池大小（128 位碰撞属于“荒谬不可能”类别）。不幸的是，事实并非如此。

线性同余生成器 (LCG) 的一个已知特性是，不同的增量会创建不同的流，但它们之间存在已知的关系。每个 LCG 都有一个轨道，遍历所有\(2^{128}\)个不同的 128 位状态。两个增量不同的 LCG 之间的关系是，可以“旋转”第一个 LCG 的轨道（将其向前推进我们可以根据两个增量计算出的步数），这样两个 LCG 就会始终具有相同的状态，最多相差一个加法常数，或者可能存在比特反转。如果然后以锁步方式迭代这两个流，则状态将始终保持由该相同加法常数（以及存在的情况下反转）相关联。回想一下，PCG64是由转换函数（LCG）和输出函数构成的。预计输出函数的扰动效果足以使不同的流在实践中独立（即“通过PractRand测试”），除非两个增量之间存在病态关系（例如 1 和 3）。我们在PCG64中实现的当时标准 PCG 算法的输出函数 XSL-RR 证明太弱，无法掩盖我们上面描述的底层 LCG 的 58 位冲突。对于任何给定的增量对，状态的“冲突”空间大小都是相同的，因此对于此弱点，增量提供的额外独特性不会转化为针对PractRand可以检测到的统计相关性的额外保护。

幸运的是，增强输出函数能够纠正此弱点，并且确实将不同增量提供的额外独特性转化为针对这些低位冲突的额外保护。感谢PCG 作者，她在新的BitGenerator系统漫长的诞生过程中，针对相关讨论开发了一个更强大的输出函数。我们 NumPy 开发人员选择“保守”地使用当时经过更长时间测试的 XSL-RR 变体。DXSM 输出函数采用强整数哈希中使用的“异或移位-乘法”结构，该结构比 XSL-RR 输出函数具有更好的雪崩特性。虽然存在导致两个流相关的“不良”加法常数的“病态”增量对，但绝大多数对会导致“良好”的加法常数，从而使 LCG 状态的仅仅不同的流成为实际上独立的输出流。实际上，我们曾经对PCG64做出的断言现在实际上适用于PCG64DXSM：冲突是可能的，但两个流必须同时在 128 位状态空间中“接近”，并且在 127 位增量空间中“接近”，因此这将不太可能，比在 128 位内部SeedSequence池中发生冲突的微不足道的可能性还要小。DXSM 输出函数在计算上比 XSL-RR 更密集，但 LCG 中的一些优化弥补了大多数机器上的性能损失，因此PCG64DXSM是一个良好、安全的升级。当然，可以考虑无限数量的更强大的输出函数，但大多数将具有更大的计算成本，而 DXSM 输出函数目前已通过PractRand进行了许多 CPU 周期的测试。

本页内容