Existe uma alternativa ao uso do tempo para propagar uma geração de números randoms?

Eu estou tentando executar várias instâncias de um pedaço de código (2000 instâncias ou mais) simultaneamente em um cluster de computação. A maneira como isso funciona é que eu envio as tarefas e o cluster as executará à medida que os nós se abrem de vez em quando, com vários trabalhos por nó. Isso parece produzir os mesmos valores para um bom número de instâncias em sua geração de números randoms, que usa um time-seed.

Existe uma alternativa simples que posso usar em vez disso? Reprodutibilidade e segurança não são importantes, a geração rápida de sementes únicas é. Qual seria a abordagem mais simples e, se possível, uma abordagem de plataforma cruzada seria boa?

A instrução rdtsc é uma semente bastante confiável (e aleatória).

No Windows, é acessível através do __rdtsc() intrínseco.

No GNU C, é acessível via:

 unsigned long long rdtsc(){ unsigned int lo,hi; __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi)); return ((unsigned long long)hi << 32) | lo; } 

A instrução mede o total de pseudo-ciclos desde que o processador foi ligado. Dada a alta freqüência das máquinas atuais, é extremamente improvável que dois processadores retornem o mesmo valor, mesmo que inicializem ao mesmo tempo e tenham a mesma velocidade.

Eu suponho que você tenha algum processo iniciando os outros processos. Passe na semente para usar. Então você pode ter esse processo mestre apenas passar um número random para cada processo para usar como semente. Dessa forma, há apenas uma semente arbitrária escolhida … você pode usar o tempo para isso.

Se você não tiver um processo mestre iniciando os outros, se cada processo tiver pelo menos um índice exclusivo, o que você pode fazer é fazer com que um processo gere uma série de números randoms na memory (se houver memory compartilhada) ou em um arquivo. (se compartilhado disco) e, em seguida, cada processo extrair o número random do índice para fora para usar como sua semente.

Nada lhe dará uma distribuição mais uniforme de sementes do que uma série de números randoms de uma única semente.

Uma combinação do PID e do tempo deve ser suficiente para obter uma semente única. Não é 100% multi-plataforma, mas getpid(3) em plataformas * nix e GetProcessId no Windows você obterá 99,9% do caminho até lá. Algo como isso deve funcionar:

 srand((time(NULL) & 0xFFFF) | (getpid() << 16)); 

Você também pode ler dados de /dev/urandom em sistemas * nix, mas não há equivalente a isso no Windows.

 unsigned seed; read(open("/dev/urandom", O_RDONLY), &seed, sizeof seed); srand(seed); // IRL, check for errors, close the fd, etc... 

Eu também recomendaria um melhor gerador de números randoms.

Se o C ++ 11 puder ser usado, considere std::random_device . Eu sugiro que você assista link para um guia completo.

Extraindo a mensagem essencial do link do vídeo : Você nunca deve usar srand & rand , mas em vez disso use std::random_device e std::mt19937 – para a maioria dos casos, o seguinte seria o que você deseja:

 #include  #include  int main() { std::random_device rd; std::mt19937 mt(rd()); std::uniform_int_distribution dist(0,99); for (int i = 0; i < 16; i++) { std::cout << dist(mt) << " "; } std::cout << std::endl; } 

Em vez do tempo direto medido em segundos a partir da function C std lib time (), você poderia usar o contador do processador? A maioria dos processadores tem uma contagem de ticks de execução livre, por exemplo, em x86 / x64, há o contador de registro de data e hora :

O Time Stamp Counter é um registrador de 64 bits presente em todos os processadores x86 desde o Pentium. Conta o número de pulsos desde a redefinição.

(Essa página também tem muitas maneiras de acessar este contador em diferentes plataformas – gcc / ms visual c / etc)

Lembre-se de que o contador de registro de data e hora não está isento de falhas, ele pode não estar sincronizado nos processadores (provavelmente você não se importa com o aplicativo). E os resources de economia de energia podem aumentar ou diminuir o processador (novamente, você provavelmente não se importa).

Apenas uma ideia … gerar um GUID (que é 16 bytes) e sumr seus fragments de 4 bytes ou 8 bytes (dependendo da largura esperada da semente), permitindo o contorno inteiro do inteiro. Use o resultado como uma semente.

Os GUIDs normalmente encapsulam as características do computador que os gerou (como o endereço MAC), o que torna improvável que duas máquinas diferentes acabem gerando a mesma seqüência aleatória.

Isso obviamente não é portátil, mas encontrar APIs / bibliotecas apropriadas para o seu sistema não deve ser muito difícil (por exemplo, UuidCreate no Win32, uuid_generate no Linux).

janelas

Fornece CryptGenRandom() e RtlGenRandom() . Eles lhe darão uma matriz de bytes randoms, que você pode usar como sementes.

Você pode encontrar os documentos nas páginas do msdn .

Linux / Unixes

Você pode usar RAND_bytes RAND_bytes() do RAND_bytes() para obter um número random de bytes no linux. Ele usará /dev/random por padrão.

Juntar as peças:

 #ifdef _WIN32 #include  #else #include  #endif uint32_t get_seed(void) { uint32_t seed = 0; #ifdef _WIN32 RtlGenRandom(&seed, sizeof(uint32_t) ); #else RAND_bytes(&seed, sizeof(uint32_t) ); #endif return seed; } 

Observe que o openssl fornece um PRNG criptograficamente seguro por padrão, para que você possa usá-lo diretamente. Mais informações aqui .

Supondo que você esteja em um sistema razoavelmente POSIX-ish, você deve ter clock_gettime . Isso dará o tempo atual em nanossegundos , o que significa que, para todos os fins práticos, é impossível obter o mesmo valor duas vezes. (Em teoria, implementações ruins podem ter uma resolução muito menor, por exemplo, apenas multiplicando milissegundos em 1 milhão, mas até mesmo sistemas decentes como o Linux geram resultados reais de nanossegundos.)

Se a exclusividade for importante, você precisará organizar cada nó para saber quais IDs foram reivindicados por outros. Você poderia fazer isso com um protocolo perguntando “alguém reivindicou o ID x?” ou organizar antecipadamente para cada nó ter uma seleção de IDs que não foram alocados a outros.

(Os GUIDs usam o MAC da máquina, portanto, cairiam na categoria “organizar antecipadamente”.)

Sem alguma forma de acordo, você arriscará dois nós usando o mesmo ID.