Generazione contemporanea di numeri casuali

Question

Sto scrivendo un programma parallelo usando open mp in cui io generi una matrice di numeri in virgola mobile casuali e poi eseguo un numero di calcoli su di esso. Attualmente voglio fare il passo in cui creo la matrice in parallelo, ma ho il problema che la funzione rand() non è stata pensata per funzionare contemporaneamente. Non voglio usare i lock per fornire mutex su rand perché questa è l'unica cosa che viene fatta nel ciclo e probabilmente sarebbe più efficiente eseguirla in sequenza. C'è un modo per fare questo passo in modo efficiente in parallelo?

Qui se il codice corrente per questa parte (senza mutex su rand);

#pragma omp parallel default(private) 
{ 
    int i= omp_get_thread_num(); 
    for(int j=0; j<cols; j++) 
     matrix[i][j]= rand()%1000 + (float)(rand()%100)/(float)(rand()%1000); 
} 

Answer 1

Se si utilizza C++, è consigliabile utilizzare Boost library random number classes. È possibile creare un'istanza PRNG univoca per ogni thread. Se si richiede la ripetibilità, è possibile inizializzare ciascuna istanza nel thread principale con valori seme ripetibili generati.

Answer 2

Se pseudo è abbastanza buono (cfr commento di Ben), allora si potrebbe creare il proprio PRNG (ad es. A Mersenne Twister piuttosto che il metodo modulo deboli utilizzato dalla maggior parte dei sistemi), e implementare un generatore indipendente per ogni filo. se lo fai, DEVI assicurarti che ogni generatore abbia un seme diverso.

Answer 3

Un vero problema è se si desidera la riproducibilità, che è spesso necessaria nel test. Con un seme dato genera una sequenza di semi di filo. Quindi ogni thread utilizzerà il proprio seme per generare numeri.

Il fatto che rand() non sia thread-safe non rappresenta un problema. Sono disponibili numerosi algoritmi ed è banale eseguire il rollback di una istanza (stato) per thread, basta iniziare da http://en.wikipedia.org/wiki/Random_number_generation#Computational_methods per esempio. Il blocco per ogni chiamata rand() sarebbe un disastro di concorrenza.

Answer 4

Penso che stiate cercando rand_r(), che prende esplicitamente lo stato RNG corrente come parametro. Quindi ogni thread dovrebbe avere la propria copia dei dati seme (se vuoi che ogni thread inizi con lo stesso seme o diversi dipende da cosa stai facendo, qui vuoi che siano diversi o otterrai la stessa riga ancora e ancora). C'è qualche discussione su rand_r() e sicurezza del thread qui: whether rand_r is real thread safe?.

Quindi si supponga di volere che ogni thread abbia il proprio inizio iniziale con il suo numero di thread (che probabilmente non è quello che si desidera, poiché darebbe la stessa matrice ogni volta che si eseguiva lo stesso numero di thread, ma proprio come un esempio):

#pragma omp parallel default(none) shared(matrix, cols) 
{ 
    int i= omp_get_thread_num(); 
    unsigned int myseed = i; 
    for(int j=0; j<cols; j++) 
     matrix[i][j]= rand_r(&myseed)%1000 + (float)(rand_r(&myseed)%100)/(float)(rand_r(&myseed)%1000 + 1); 
} 

Ora ogni thread sta modificando il proprio stato esclusivamente (rand_r() è una funzione pura) e si dovrebbe essere a casa gratuitamente.