Skip to content

Latest commit

 

History

History
243 lines (163 loc) · 16.8 KB

np126_0961.md

File metadata and controls

243 lines (163 loc) · 16.8 KB

并行随机数生成

原文:numpy.org/doc/1.26/reference/random/parallel.html

有四种主要策略可以用来在多个进程(本地或分布式)中产生可重复的伪随机数。

SeedSequence 的生成

NumPy 允许您通过它们的 spawn() 方法生成新的(非常高的概率)独立的BitGeneratorGenerator实例。这种生成是通过用于初始化比特生成器随机流的SeedSequence实现的。

SeedSequence 实现了一个算法,用于处理用户提供的种子,通常作为某种大小的整数,并将其转换为BitGenerator的初始状态。它使用哈希技术确保低质量的种子被转换为高质量的初始状态(至少,有很高的概率)。

例如,MT19937 的状态由 624 个 uint32 整数组成。一个简单的方法是将一个 32 位整数种子设置为状态的最后一个元素,其余为 0。这对于MT19937来说是一个有效的状态,但不是一个好的状态。梅森旋转算法如果有太多的 0会出现问题。同样,相邻的两个 32 位整数种子(例如 1234512346)会产生非常相似的流。

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 是不必要的。上述的 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^{-128}),其中n*是生成的流的数量。如果一个程序使用了激进的百万流,约为(2^{20}),那么至少有一对它们相同的概率约为(2^{-88}),这已经是可以忽略不计的领域([2])。 ## 整数种子序列

如前一节所讨论的,SeedSequence不仅可以接受整数种子,还可以接受任意长度的(非负)整数序列。如果稍加小心,可以利用这个特性设计特设方案,以获得类似生成的安全并行 PRNG 流的安全保证。

例如,一个常见的用例是,一个工作进程为整个计算传递一个根种子整数,还有一个整数工作人员 ID(或者更精细的像作业 ID、批次 ID 或类似的东西)。如果这些 ID 是确定性且唯一地创建的,那么可以通过将 ID 和根种子整数组合成一个列表来派生可重现的并行 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) 

对于以这种方式构建的并行程序的任何一次运行,每个工作人员将具有不同的流。然而,很可能在不同种子的多次调用程序中获得重叠的工作人员种子集。在进行这些重复运行时,仅仅通过增加一两个根种子是很常见的(作者的亲身经历)。如果工作人员种子也是通过工作人员 ID 的小增量派生的,那么工作者的子集将返回相同的结果,导致整体结果集中的偏差。

将工作人员 ID 和根种子作为整数列表组合可以消除这种风险。懒惰的播种实践仍然是相当安全的。

此方案要求额外的 ID 必须是唯一的并且是确定性创建的。这可能需要在工作进程之间进行协调。建议将变化的 ID 放在 不变的根种子之前。spawn 在用户提供的种子后 追加 整数,因此如果您可能同时使用这种 临时 机制和生成,或者将您的对象传递给可能正在生成的库代码,那么最好在前面而不是在后面添加您的工作 ID,以避免碰撞。

# Good.
worker_seed = [worker_id, root_seed]

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

在考虑这些注意事项的情况下,针对碰撞的安全保证与前一节讨论的生成相同。算法机制也是相同的。 ## 独立流

Philox 是基于计数器的 RNG,通过使用弱加密原语对递增计数器进行加密来生成值。种子确定了用于加密的密钥。唯一的密钥创建了唯一的、独立的流。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)] 

此方案要求避免重复使用流 ID。这可能需要并行进程之间的协调。 ## 推进位生成器状态

jumped 推进位生成器的状态,好像已经抽取了大量的随机数,并返回具有此状态的新实例。具体的抽取次数因位生成器而异,范围从 (2^{64}) 到 (2^{128})。此外,好像抽取还取决于特定位生成器产生的默认无符号随机数的大小。支持 jumped 的位生成器,以及位生成器的周期、跳跃大小和默认无符号随机数的位数如下所示。

位生成器 周期 跳跃大小 每次抽取的位数
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

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)开始,否则将重新创建相同的流。另一方面,如果您仔细构建这些流,则可以确保流不会重叠。##SeedSequence生成

NumPy 允许您通过其spawn()方法生成新的(高概率下的)相互独立的BitGeneratorGenerator实例。这种生成由用于初始化比特生成器随机流的SeedSequence实现。

SeedSequence实现了一种算法,用于处理用户提供的种子,通常是某种大小的整数,并将其转换为BitGenerator的初始状态。它使用散列技术确保低质量的种子以非常高的概率被转换为高质量的初始状态。

例如,MT19937 的状态由 624 个 uint32 整数组成。一种朴素的方法是将一个 32 位整数种子设置为状态的最后一个元素,并将其余元素设置为 0。这是 MT19937 的一个有效状态,但不是一个好的状态。梅森旋转算法suffers if there are too many 0s。同理,相邻的两个 32 位整数种子(即 1234512346)会产生非常相似的序列。

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。上述的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^{-128}),其中n*是生成的流的数量。如果一个程序使用了激进的百万流,约为(2^{20}),那么至少有一对它们相同的概率约为(2^{-88}),这在可忽略的范围内([2])。

整数种子序列

如前一节所讨论的,SeedSequence不仅可以接受整数种子,还可以接受任意长度的(非负)整数序列。如果稍加注意,可以利用这个特性设计类似生成的安全并行 PRNG 流的临时方案,具有类似生成的安全保证。

例如,一个常见的用例是,一个工作进程被传递一个整数根种子用于整个计算,还有一个整数工作人员 ID(或者更精细的像作业 ID、批次 ID 或类似的东西)。如果这些 ID 是确定性地且唯一地创建的,那么可以通过将 ID 和根种子整数组合成列表来派生可重现的并行 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) 

对于以这种方式构建的并行程序的任何一次运行,每个工作人员将具有不同的流。然而,很可能在使用不同种子多次调用程序时,会得到重叠的工作人员种子集。改变根种子仅仅增加一两个时并不罕见(作者的自身经验)。如果工作人员种子也是通过工作人员 ID 的小增量派生的,那么工作人员的子集将返回相同的结果,导致整体结果集中的偏差。

将工作人员 ID 和根种子组合为整数列表可以消除这种风险。懒惰的播种实践仍然是相当安全的。

此方案要求额外的 ID 必须是唯一的,并且是确定性创建的。这可能需要协调工作进程之间的关系。建议将变化的 ID放在不变的根种子之前生成 追加用户提供的种子之后的整数,所以如果可能同时使用这临时机制和生成,或者将对象传递给可能在生成中生成的库代码,那么更安全的做法是在你的工作进程 ID 之前添加而不是追加,以避免冲突。

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

此方案确实要求避免重用流 ID。这可能需要在并行进程之间协调。

跳转 BitGenerator 状态

jumped会推进 BitGenerator 的状态,好像已经抽取了大量的随机数,并返回一个具有此状态的新实例。具体的抽取次数因 BitGenerator 而异,范围从(2^{64})到(2^{128})不等。此外,好像抽取还取决于特定 BitGenerator 产生的默认无符号随机数的大小。支持jumped的 BitGenerators 以及 BitGenerator 的周期、跳跃的大小和默认无符号随机数的比特数如下所示。

BitGenerator 周期 跳跃大小 每次抽取的比特数
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

可以使用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)开始,否则会重新创建相同的流。另一方面,如果仔细构造流,那么就确保了不会重叠的流。