Geradores de números pseudoaleatórios paralelos

Essa questão está relacionada principalmente a um problema prático de engenharia de software, mas eu ficaria curioso para saber se os teóricos poderiam fornecer mais insights sobre isso.

Simplificando, eu tenho uma simulação de Monte Carlo que usa um gerador de números pseudo-aleatórios e gostaria de paralelá-la para que haja 1000 computadores executando a mesma simulação em paralelo. Portanto, preciso de 1000 fluxos independentes de números pseudo-aleatórios.

Podemos ter 1000 fluxos paralelos com as seguintes propriedades? Aqui $X$ deve ser um PRNG muito conhecido e amplamente estudado, com todos os tipos de boas propriedades teóricas e empíricas.

1. Os fluxos são comprovadamente tão bons quanto o que eu obteria se simplesmente usasse o $X$ e dividisse o fluxo gerado pelo $X$ em 1000 fluxos.

2. Gerando o próximo número em qualquer fluxo é (quase) tão rápido quanto gerar o próximo número com $X$ .

Em outras palavras: podemos obter múltiplos fluxos independentes "de graça"?

Obviamente, se simplesmente usamos , descartando sempre 999 números e escolhendo 1, certamente teríamos a propriedade 1, mas perderíamos no tempo de execução pelo fator 1000.$X$

Uma idéia simples seria usar 1000 cópias de , com sementes 1, 2, ..., 1000. Isso certamente seria rápido, mas não é óbvio se os fluxos tiverem boas propriedades estatísticas.$X$

Depois de pesquisar no Google, encontrei, por exemplo, o seguinte:

• A biblioteca SPRNG parece ter sido projetada exatamente para esse fim e suporta vários PRNGs .

• O twister de Mersenne parece ser um PRNG popular hoje em dia, e eu encontrei algumas referências a uma variante capaz de produzir múltiplos fluxos em paralelo.

Mas tudo isso está tão longe das minhas próprias áreas de pesquisa, que não consegui descobrir o que é realmente o estado da arte e quais construções funcionam bem não apenas na teoria, mas também na prática.

Alguns esclarecimentos: não preciso de nenhum tipo de propriedades criptográficas; isto é para computação científica. Vou precisar de bilhões de números aleatórios, para que possamos esquecer qualquer gerador com um período .$< 2^{32}$

Edit: Não consigo usar um RNG verdadeiro; Eu preciso de um PRNG determinístico. Em primeiro lugar, ajuda muito na depuração e torna tudo repetível. Em segundo lugar, ele permite que eu faça, por exemplo, encontrar medianas de maneira muito eficiente, explorando o fato de que posso usar o modelo de múltiplas passagens (consulte esta pergunta ).

Edit 2: Existe uma pergunta intimamente relacionada @ StackOverflow: Gerador de números pseudo-aleatórios para ambiente de cluster .

Você pode usar uma evolução do algoritmo Mersenne Twister desenvolvido por Saito e Matsumoto:

Fast Mersenne Twister (SFMT) orientado a SIMD

SFMT é um gerador LFSR (Linear Feedbacked Shift Register) que gera um número inteiro pseudo-aleatório de 128 bits em uma etapa. O SFMT foi projetado com recente paralelismo de CPUs modernas, como pipelining de vários estágios e instruções SIMD (por exemplo, número inteiro de 128 bits). Ele suporta números inteiros de 32 e 64 bits, bem como o ponto flutuante de precisão dupla como saída. O SFMT é muito mais rápido que o MT, na maioria das plataformas. Não apenas a velocidade, mas também as dimensões das equidistribuições com precisão de bits v são aprimoradas. Além disso, a recuperação do estado inicial com excesso de 0 é muito mais rápida. Veja a Tese de Mutsuo Saito para detalhes .

O período varia de a 2 216091 - 1 .$2^{607}-1$$2^{216091}-1$

O uso de um mesmo gerador de números aleatórios para gerar múltiplos fluxos independentes, alterando os valores iniciais, pode causar um problema (com probabilidade insignificante pequena). Para evitar o problema, é preferível usar parâmetros diferentes para cada geração. Essa técnica é chamada criação dinâmica dos parâmetros MT.

No código-fonte SFMT, você pode encontrar alguns exemplos de conjuntos de parâmetros (de períodos variáveis) e um script awk para converter um arquivo CSV em um conjunto de parâmetros compilável. Existe também uma ferramenta chamada " Criação dinâmica de geradores Mersenne Twister ".

Os autores desenvolveram recentemente outra versão modificada do Mersenne Twister - Mersenne Twister para processadores gráficos - projetada para rodar em GPUs e tirar proveito de seus threads de execução paralela nativa. A principal característica é a velocidade: inteiros aleatórios a cada 4,6ms em uma GeForce GTX 260.$5 \times 10^7$

Os períodos da sequência gerada são , 2 23209 - 1 e 2 44497 - 1 para a versão de 32 bits e 2 23209 - 1 , 2 44497 - 1 , 2 110503 - 1 para a versão de 64 bits. Ele suporta 128 conjuntos de parâmetros para cada período, ou seja, pode gerar 128 seqüências de números pseudoaleatórios independentes para cada período. Desenvolvemos o Dynamic Creator for MTGP, que gera mais conjuntos de parâmetros$2^{11213}-1$$2^{23209}-1$$2^{44497}-1$$2^{23209}-1$$2^{44497}-1$$2^{110503}-1$

De fato, eles fornecem uma ferramenta MTGPDC para criar até conjuntos de parâmetros (ou seja, fluxos independentes).$2^{32}$

O algoritmo passa nos principais testes de aleatoriedade, como Diehard e NIST.

Um artigo preliminar também está disponível no arXiv: uma variante do Mersenne Twister adequada para processadores gráficos

Parece haver muitas maneiras de solucionar esse problema, mas uma maneira simples seria usar o PRNG Blum Blum Shub . Este PRNG é definida pela relação recurrance , onde N é um semiprimo. Para obter um pouco aleatório disso, você pode simplesmente ter a paridade de bits de x i . O que é legal nisso é que, como x i + k = x 2 k i  mod  N = x 2 k  mod  λ ( N )$x_{i+1} = x_i^2 \mbox{ mod }N$$N$$x_i$ você pode calcular diretamente qualquer passo no tempo constante em k (ou seja, O ( log ( N ) 3 ) ou mais rápido, dependendo do algoritmo de multiplicação usado para o exponencial modular). Assim, você temmáquinas M ; então, para a máquina indexada por y, você pode usar o gerador x i + 1 , y = x 2 M mod  λ ( N ) i  mod  N , onde x 0 , y = $x_{i+k} = x_i^{2^k}\mbox{ mod }N = x_i^{2^k \mbox{ mod } \lambda(N)}\mbox{mod }N$$k$$O(\log(N)^3)$$M$$y$$x_{i+1,y} = x_i^{2^M \mbox{mod }\lambda(N)}\mbox{ mod }N$, ondex0é sua semente. Convenientemente, isso gera exatamente o mesmo fluxo de números, como se você usasse um único fluxo e distribuísse sua saída para cada uma das máquinas.$x_{0,y} = x_0^{2^y \mbox{ mod }\lambda(N)}\mbox{ mod }N$$x_0$

Porém, esse não é o PRNGs mais rápido, portanto, será útil apenas se a sobrecarga do que você estiver fazendo na simulação for significativamente maior do que o custo do PRNG. No entanto, vale ressaltar que será muito mais rápido para certas combinações de e N do que outras, particularmente se a representação binária de 2 M  mod  λ ( N ) contiver poucos 1s ou for pequena.$M$$N$$2^M \mbox{ mod }\lambda(N)$

Que tal uma fase de pré-processamento? Dado um valor aleatório (do tamanho n ), execute X para obter um fluxo pseudo-aleatório do tamanho 1000 n . Denote esse fluxo por s 1 , s 2 , … , s 1000 , onde para 1 ≤ i ≤ 1000 , s i é uma porção contígua do fluxo de tamanho n .$s$$n$$X$$1000n$$s_1,s_2,\ldots,s_{1000}$$1\le i \le 1000$$s_i$$n$

Essa fase de pré-processamento pode ser realizada com uma sobrecarga muito baixa, pois o é um PRNG eficiente (hoje, temos PRNGs muito rápidos).$X$

$s_i$$i$$X$

$X$$s$$1 \le i < j \le 1000$$s_i$$s_j$$s$

Você poderia usar uma função pseudo-aleatória $f$como AES ou ChaCha com uma única chave aleatória, criptografando um contador. Atribua cada um dos$M = 1000$ paralelo processa um valor inicial único em $\{ 0, 1, \ldots, M - 1 \}$e, em seguida, calcule o $j$th bloco aleatório de bits para processo $i$ Como $f(i + jM)$, ou seja, incremente o contador em cada processo $M$ para cada bloco subsequente de bits aleatórios.

Isso fornecerá um RNG criptográfico em todos os processos, mas não necessariamente vem com um custo de desempenho. O AES é rápido se você possui um hardware que o suporta, e o ChaCha é rápido, independentemente. Obviamente, você deve medir isso em sua configuração específica para ter certeza.

Ambas as propriedades 1 e 2 desejadas são diretamente satisfeitas por isso. Além disso, é conveniente que o comportamento de todo o sistema de tarefas paralelas seja controlado por uma única "semente" (a chave para$f$)

There is now a jump function for SFMT (a fast Mersenne Twister implementation).

This allows me to initialise 1000 MTs so that there is no cycle overlap. And SFMT should be faster than MTGP. Almost perfect for my purposes.

Você pode usar apenas 1000 instâncias do Mersenne Twister inicializadas com sementes diferentes.

Você pode amostrar as sementes de outro Mersenne Twister, ou, para ter certeza de sua independência, do gerador de números pseudo-aleatórios criptográficos do SO (/ dev / urandom no Linux).

O Mersenne Twister sempre opera na mesma sequência cíclica, a semente controla onde você começa a gerá-lo. Com sementes amostradas independentemente, cada gerador inicia em pontos diferentes, geralmente muito distantes, com uma probabilidade muito pequena de interseção.