[JAVA] Problema nella generazione dei numeri casuali

[Lim]

Salve a tutti, ho un problema con la generazione dei numeri casuali in Java.
Ho sviluppato una piattaforma di simulazione per il moto di migliaia di particelle in uno spazio 3D.
Ho la necessità di aggiornare le loro coordinate spaziali (x, y, z) ad ogni istante temporale della simulazione in modo del tutto casuale (data da un moto di tipo Browniano) secondo una distribuzione Gaussiana con media nulla e deviazione standard predefinita.

Ipotizzando una dislocazione iniziale delle particelle in un punto ben preciso dello spazio, ci si aspetterebbe che dopo un certo tempo, le particelle si siano sparpagliate nello spazio in modo uniforme, mantenendo il baricentro di tutti i punti grosso modo intorno al punto iniziale.

Ho eseguito diversi run su macchine diverse ed ho ottenuto risultati diversi. La maggior parte delle macchine utilizzate resituisce i risultati attesi, mentre alcune configurazioni specifiche restituiscono risultati polarizzati.
Infatti dai risultati emerge che la "nuvola" di punti si sposti lungo una direzione preferenziale (lungo l'asse x).

Mi chiedo se la generazione dei numeri casuali possa dipendere in qualche modo dall'architettura del processore utilizzato.

Le architetture utilizzate per i test sono le seguenti:

Tipo 1:
Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz
RAM: 32GB

Tipo 2:
Intel(R) Core(TM) i5-2300 CPU @ 2.80GHz
RAM: da 8GB a 24GB

Tipo 3:
Intel(R) Xeon(R) CPU E5410 @ 2.33GHz
RAM: 24GB

Tipo 4:
Six-Core AMD Opteron(tm) Processor 8425 HE @ 2.1GHz
RAM: 64GB

Tipo 5:
AMD Opteron(tm) Processor 6128 @ 2GHz
RAM: 128GB

Tipo 6:
Intel(R) Xeon(R) CPU E5-2650 v3 @ 2.30GHz
RAM: 64GB


Le tipologie 1 e 2 forniscono i risultati attesi, tutte le altre danno risultati polarizzati.

Il sistema operativo utilizzato è Ubuntu 12.04 LTS e Ubuntu 14.04 LTS.
La versione della JVM è: OpenJDK 1.7 (64-Bit)


Riporto anche il codice dell'algoritmo per l'aggiornamento delle coordinate dei punti:

Il metodo move() è invocato ad ogni passo temporale della simulazione per ogni singolo punto da aggiornare mediante un approccio multithread (non mostrato qui):

public void move(MyObj p) {
        float[] center=p.getCenter();                   
        float sigma2=getDiffusionCoefficient(p);        

        float dx=getGauss(sigma2);
        float dy=getGauss(sigma2);
        float dz=getGauss(sigma2);

        center[0]=center[0]+dx;
        center[1]=center[1]+dy;
        center[2]=center[2]+dz;
        p.setCenter(center[0],center[1],center[2]); 
    }


// A better implementation of Gaussian Random Number
    public float getGauss(float sigma){
        float rai=(float) Math.sqrt(-2*sigma*sigma*Math.log(1-(random.next(val)/div)));
        float teta=(float) (2*Math.PI*(random.next(val)/div));
        return (float) (rai*Math.cos(teta));
    }

Dove random è un'istanza di XORShiftRandom:

// XORShiftRandom
    int val=31;
    double div=Math.pow(2, val);
    XORShiftRandom random=new XORShiftRandom(); 
    // End XORShiftRandom


public class XORShiftRandom {

    private long seed = System.nanoTime();        

    public XORShiftRandom() {

    }    

    protected int next(int nbits) {         
        long x = this.seed;
        x ^= (x << 21);
        x ^= (x >>> 35);
        x ^= (x << 4);
        this.seed = x;
        x &= ((1L << nbits) -1);
        return  (int)(x);
    }
}

Avendo rilevato una polarizzazione lungo l'asse x, ho voluto provare ad invertire l'ordine di generazione delle nuove coordinate, da x,y,z a y,z,x. La polarizzazione si è spostata dalla componente lungo x a quella lungo y! Quindi a quanto pare è la prima coordinata generata a subire principalmente gli effetti della polarizzazione.
Non ho idea del perché...
Inoltre, sembrerebbe che al crescere del numero di punti, cresca anche l'effetto della polarizzazione (in effetti, al crescere del numero di punti cresce il numero di chiamate al metodo di generazione delle coordinate).


Qualcuno ha qualche idea al riguardo?

[GianMi]

L'unica cosa che è connessa con l'hardware sottostante è la funzione System.nanoTime() e quindi potrebbe essere qualcosa legato alla risoluzione del timer. Tuttavia in un sistema multithread sono moltissime le cose che potrebbero non funzionare a dovere e presentare strani effetti collaterali.

[Lim]

Originariamente inviato da GianMi

L'unica cosa che è connessa con l'hardware sottostante è la funzione System.nanoTime() e quindi potrebbe essere qualcosa legato alla risoluzione del timer. Tuttavia in un sistema multithread sono moltissime le cose che potrebbero non funzionare a dovere e presentare strani effetti collaterali.

Avevo pensato anche io al System.nanoTime(), ma in realtà quella funzione viene invocata una sola volta, in fase di creazione dell'oggetto XORShiftRandom, quindi non dovrebbe influire più di tanto perché alla fine un seed vale l'altro per la generazione della sequenza casuale.
Piuttosto credo che il problema potrebbe essere legato alla concorrenza tra i thread, poiché ognuno effettua 3 chiamate al metodo next() di XORShiftRandom ed all'interno del metodo viene aggiornato il seed, dopo aver effettuato vari shift ed operazioni binarie sul seed precedente.
Sono sempre più convinto che i thread vadano a leggere e scrivere il seed in contemporanea e quindi la sequenza non è più casuale. Quello che continuo a non capire è perché l'effetto di polarizzazione sia evidente soltanto sulla coordinata X...

[GianMi]

Ok, allora potresti rendere la tua classe Random locale ai vari thread e quindi ognuno di essi avrà la sua istanza, cosa che se non sbaglio fa anche la la libreria java nella sua classe Random specializzata per il multithread. Dovresti però fare in modo che il seed di partenza non sia lo stesso quindi l'inizializzazione del seed andrebbe fatta con un Singleton.

[Daniels118]

Originariamente inviato da GianMi

Ok, allora potresti rendere la tua classe Random locale ai vari thread e quindi ognuno di essi avrà la sua istanza, cosa che se non sbaglio fa anche la la libreria java nella sua classe Random specializzata per il multithread. Dovresti però fare in modo che il seed di partenza non sia lo stesso quindi l'inizializzazione del seed andrebbe fatta con un Singleton.

Conviene passare il seed come parametro nel costruttore di XORShiftRandom, ed istanziarlo così:

long seed = System.nanoTime();
XORShiftRandom a = new XORShiftRandom(seed + 0);
XORShiftRandom b = new XORShiftRandom(seed + 1);
...

In questo modo hai la garanzia che i seed siano diversi (se il generatore è buono il fatto che si discostano sempre di 1 dovrebbe essere ininfluente).

[GianMi]

Originariamente inviato da Daniels118

Conviene passare il seed come parametro nel costruttore di XORShiftRandom, ed istanziarlo così:

long seed = System.nanoTime();
XORShiftRandom a = new XORShiftRandom(seed + 0);
XORShiftRandom b = new XORShiftRandom(seed + 1);
...

In questo modo hai la garanzia che i seed siano diversi (se il generatore è buono il fatto che si discostano sempre di 1 dovrebbe essere ininfluente).

La soluzione che suggerisci mi sembra che ignori del tutto il fatto che l'uso della classe è fatto in più thread paralleli... E' corretto generare il seed in quel modo, ma funzionerebbe solo se l'inizializzazione dei generatori random fosse statica, prima della partenza dei thread a cui si passa poi l'istanza di ogni generatore come parametro. La soluzione corretta potrebbe essere quella di usare un AtomicLong inizializzato con System.nanoTime() e poi usare il metodo incrementAndGet() che è sicuramente atomico.

[Daniels118]

La soluzione che ho proposto va bene se la creazione dei generatori avviene in un unico thread, non ha importanza quando e quanti ne vengono creati; certamente l'utilizzo di AtomicLong rende la classe applicabile ad un maggior numero di scenari.

[Daniels118]

Originariamente inviato da Lim

[..] Sono sempre più convinto che i thread vadano a leggere e scrivere il seed in contemporanea e quindi la sequenza non è più casuale. Quello che continuo a non capire è perché l'effetto di polarizzazione sia evidente soltanto sulla coordinata X...

Per curiosità fai queste prove e vedi se il problema persiste:
- esegui il programma su un singolo thread;
- aggiungi synchronized al metodo next (girando in multithread).