Thread-safe generazione di numeri casuali per l'integrazione di Monte-Carlo

Question

Nel tentativo di scrivere qualcosa che calcola molto rapidamente numeri casuali e può essere applicata su più thread. Il mio codice attuale è:

/* Approximating PI using a Monte-Carlo method. */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <omp.h>
#define N 1000000000  /* As lareg as possible for increased accuracy */

double random_function(void);

int main(void)
{
   int i = 0;
    double X, Y;
   double count_inside_temp = 0.0, count_inside = 0.0;
   unsigned int th_id = omp_get_thread_num();
   #pragma omp parallel private(i, X, Y) firstprivate(count_inside_temp)
   {
      srand(th_id);
      #pragma omp for schedule(static)
      for (i = 0; i <= N; i++) {
         X = 2.0 * random_function() - 1.0;
         Y = 2.0 * random_function() - 1.0;
         if ((X * X) + (Y * Y) < 1.0) {
        count_inside_temp += 1.0;
     }
  }
  #pragma omp atomic
      count_inside += count_inside_temp;
   }
   printf("Approximation to PI is = %.10lf\n", (count_inside * 4.0)/ N);
   return 0;
}

double random_function(void)
{
   return ((double) rand() / (double) RAND_MAX);
}

Questo funziona, ma osservando un gestore di risorse So che la sua non usare tutti i fili. Fa rand) lavoro (per il codice multithread? E se non c'è una buona alternativa? Grazie molto. Jack

Answer 1

È rand() thread-safe? Forse, forse no:

  

Il rand () non deve essere rientrante. Una funzione che non è necessario per essere rientranti non è richiesto di essere thread-safe ".

Un test e un buon esercizio di apprendimento potrebbe essere quella di sostituire la chiamata a rand() con, diciamo, un intero fisso e vedere cosa succede.

Il modo di pensare di generatori di numeri pseudo-casuali è come una scatola nera che prendono un intero come input e restituisce un intero come uscita. Per un dato ingresso l'uscita è sempre lo stesso, ma non c'è uno schema nella sequenza di numeri e la sequenza viene distribuito uniformemente sulla gamma di possibili uscite. (Questo modello non è del tutto esatto, ma si farà.) Il modo in cui si utilizza questa scatola nera è quello di scegliere un numero a fissare (il seme) utilizzare il valore di uscita nella propria applicazione e come ingresso per la successiva chiamata al generatore di numeri casuali. Ci sono due comuni approcci per la progettazione di un API:

1. due funzioni, una per definire il seme iniziale (ad esempio srand(seed)) e uno per recuperare il valore successivo dalla sequenza (ad esempio rand()). Lo stato del PRNG è memorizzato internamente in una sorta di variabile globale. Generazione di un nuovo numero casuale o non sarà thread-safe (difficile da dire, ma il flusso di output non sarà riproducibile) o sarà lento nel codice multithreded (si finisce con un po 'di serializzazione intorno al valore di stato).
2. Un'interfaccia in cui lo Stato PRNG è esposto al programmatore di applicazioni. Qui è in genere sono tre funzioni: init_prng(seed), che restituisce qualche rappresentazione opaca del PRNG stato, get_prng(state), che restituisce un numero casuale e cambia la variabile di stato, e destroy_peng(state), che pulisce solo la memoria allocata e così via. PRNGs con questo tipo di API dovrebbero essere sicuri filo ed eseguire in parallelo senza bloccaggio (perché si è responsabile della gestione della variabile di stato (ora infilare locale).

Io in genere scrivere in Fortran e utilizzare implementazione di Ladd della Mersenne Twister PRNG (che puntano vale la pena di lettura). Ci sono un sacco di adatti PRNG di in C che espongono lo Stato al controllo. PRNG sembra buono e l'utilizzo di questo (con l'inizializzazione e distruggere le chiamate all'interno della regione in parallelo e lo stato privato variabili) dovrebbe darvi un aumento di velocità decente.

Infine, è spesso il caso che PRNGs possono essere fatte per eseguire meglio se si chiede per tutta una sequenza di numeri casuali in una sola volta (ad esempio, il compilatore può vectorize i meccanismi interni PRNG). A causa di questo le librerie hanno spesso qualcosa di simile a funzioni get_prng_array(state) che darà indietro una serie completa di numeri casuali, come se si mette get_prng in un ciclo di riempimento degli elementi dell'array - hanno appena farlo più velocemente. Questo sarebbe un secondo di ottimizzazione (e avrebbe bisogno di un valore aggiunto per il ciclo all'interno del parallelo per ciclo. Ovviamente, non si vuole correre fuori di ogni thread spazio dello stack fare questo!