如何正确选择rng种子进行并行处理



我目前正在一个C/C++项目中使用随机数生成器(gsl或boost)。整个想法可以简化为一个非平凡的随机过程,它接收种子并返回结果。我在计算过程中不同实现的平均值。

因此,种子很重要:过程必须使用不同的种子,否则会使平均值产生偏差。

到目前为止,我正在使用time(NULL)来给出一个种子。但是,如果两个进程在同一秒开始,则种子是相同的。之所以会发生这种情况,是因为我正在使用并行化(使用openMP)。

所以,我的问题是:如何在C/C++上实现一个提供独立种子的"种子生成器"?

例如,我使用了线程号(thread_num)seed = time(NULL)*thread_num。然而,这意味着种子是相关的:它们是彼此的倍数。这会给"伪随机"带来任何问题吗?还是它和顺序种子一样好?

要求是它必须在Mac OS(我的电脑)和类似于OS Cent(集群)的Linux发行版上工作(并自然提供独立的实现)。

一个常用的方案是使用一个"主"RNG为每个进程特定的RNG生成种子。

这种方案的优点是,整个计算只由一个种子决定,您可以将其记录在某个地方,以便能够回放任何模拟(这可能有助于调试讨厌的bug)。

我们在Beowulf计算网格上遇到了类似的问题,我们使用的解决方案是将过程的pid合并到RNG种子中,如下所示:

time(NULL)*thread_num*getpid()

当然,您可以从/dev/urandom或/dev/random读取一个整数。

遇到这个问题时,我经常使用Boost.Uuid中的seed_rng。它使用timeclock/dev/urandom中的随机数据来计算种子。你可以像一样使用它

#include <boost/uuid/seed_rng.hpp>
#include <iostream>
int main() {
int seed = boost::uuids::detail::seed_rng()();
std::cout << seed << std::endl;
}

请注意,seed_rng来自一个detail名称空间,因此它可以在不另行通知的情况下离开。在这种情况下,基于seed_rng编写自己的实现应该不会太难。

Mac操作系统也是Unix,所以它可能有/dev/random。如果是,那就是获得种子的最佳解决方案。否则,如果生成器好,取time( NULL )一次,然后为种子递增对于每个生成器,应该给出相当好的结果。

如果您在x86上,并且不介意使代码不可移植,那么您可以读取时间戳计数器(TSC),这是一个64位计数器,以CPU(最大)时钟速率(约3 GHz)递增,并将其用作种子。

#include <stdint.h>
static inline uint64_t rdtsc()
{
uint64_t tsc;
asm volatile
( 
"rdtscnt"
"shlt$32,%%rdxnt"       // rdx = TSC[ 63 : 32 ] : 0x00000000
"addt%%rdx,%%raxnt"     // rax = TSC[ 63 :  0 ]
: "=a" (tsc) : : "%rdx"
);
return tsc;
}

当比较由同一伪随机数生成器产生的具有不同种子的两个无限时间序列时,我们可以看到它们相同地延迟了一些时间τ。通常,这个时间尺度比你的问题大得多,以确保两个随机行走是不相关的。

如果你的随机过程是在高维相空间中,我认为一个好的建议是:

seed = MAXIMUM_INTEGER/NUMBER_OF_PARALLEL_RW*thread_num + time(NULL)

请注意,使用该方案并不能保证时间τ很大!!

如果你对你的系统时间尺度有一些了解,你可以调用你的随机数生成器一些次数o,以便生成等距某个时间间隔的种子。

也许你可以试试C++11:的std::chrono高分辨率时钟

类std::chrono::high_resolution_clock表示具有系统上可用的最小刻度周期。它可能是的别名std::chrono::system_clock或std::chrono::steady_lock,或第三个,独立时钟。

http://en.cppreference.com/w/cpp/chrono/high_resolution_clock

但是我不确定srand(0)是否有什么问题;srand(1)、srand(2)。。。。但我对兰特的了解非常基本

为了疯狂的安全考虑:

注意,下面描述的所有伪随机数生成器可复制可构建和可转让。复制或分配生成器将复制其所有内部状态,因此原件和副本将生成相同的随机数序列。

http://www.boost.org/doc/libs/1_51_0/doc/html/boost_random/reference.html#boost_random.reference.generators

由于大多数生成器都有疯狂的长周期,所以您可以生成一个生成器,将其复制为第一个生成器,用原始生成器生成X数,复制为第二个生成器,使用原始生成器生成X数,复制作为第三个生成器。。。如果您的用户调用自己的生成器少于X次,则不会出现重叠。

我理解您的问题的方式是,您有多个进程使用相同的伪随机数生成算法,并且您希望(每个进程中的)每个随机数"流"彼此独立。我说得对吗?

在这种情况下,你正确地怀疑,除非rng算法这么说,否则给出不同的(相关的)种子并不能保证你的任何东西。你基本上有两个解决方案:

简单版本

使用单个随机数源和单个种子。然后以循环方式向每个进程提供随机数。

这个解决方案是缓慢的,但提供了一些保证,你给你的过程的数字是可以的

你可以做同样的事情,但一次生成你需要的所有随机数,然后将这个集合分割成你所处理的尽可能多的切片。

使用专门设计的RNG

你可以在论文和网络上找到几种专门设计用于从单个初始状态提供独立随机数流的算法。它们很复杂,但大多数都提供源代码。其想法通常是将RNG空间(您可以从初始状态中获得的值)"拆分"为如上所述的各种块。它们只是更快,因为使用的算法可以很容易地计算出如果跳过给定数量的值,RNG的状态会是什么。

这些生成器通常被称为"并行随机数生成器"。最受欢迎的可能是这两个:

  • RngStreams:http://statmath.wu.ac.at/software/RngStreams/
  • SPRNG:http://sprng.cs.fsu.edu/

查看他们的手册,充分了解他们做什么,如何做,以及这是否真的是你需要的。

最新更新