Riempimento di un vettore con più thread

Question

Ho bisogno di riempire un valore enorme (7734500 elementi) std::vector<unsigned int> con valori casuali e sto cercando di farlo in parallelo con più thread per ottenere una maggiore efficienza. Ecco il codice che ho finora:

std::random_device rd; // seed generator 

std::mt19937_64 generator{rd()}; // generator initialized with seed from rd 

static const unsigned int NUM_THREADS = 4; 


std::uniform_int_distribution<> initialize(unsigned long long int modulus) 
{ 
    std::uniform_int_distribution<> unifDist{0, (int)(modulus-1)}; 
    return unifDist; 
} 


void unifRandVectorThreadRoutine 
    (std::vector<unsigned int>& vector, unsigned int start, 
    unsigned int end, std::uniform_int_distribution<>& dist) 
{ 
    for(unsigned int i = start ; i < end ; ++i) 
    { 
     vector[i] = dist(generator); 
    } 
} 


std::vector<unsigned int> uniformRandomVector 
    (unsigned int rows, unsigned int columns, unsigned long long int modulus) 
{ 
    std::uniform_int_distribution<> dist = initialize(modulus); 

    std::thread threads[NUM_THREADS]; 

    std::vector<unsigned int> v; 
    v.resize(rows*columns); 

    // number of entries each thread will take care of 
    unsigned int positionsEachThread = rows*columns/NUM_THREADS; 

    // all but the last thread 
    for(unsigned int i = 0 ; i < NUM_THREADS - 1 ; ++i) 
    { 
     threads[i] = std::thread(unifRandVectorThreadRoutine, v, i*positionsEachThread, 
      (i+1)*positionsEachThread, dist); 
     // threads[i].join(); 
    } 

    // last thread 
    threads[NUM_THREADS - 1] = std::thread(unifRandVectorThreadRoutine, v, 
     (NUM_THREADS-1)*positionsEachThread, rows*columns, dist); 
    // threads[NUM_THREADS - 1].join(); 

    for(unsigned int i = 0 ; i < NUM_THREADS ; ++i) 
    { 
     threads[i].join(); 
    } 

    return v; 
} 

Al momento, ci vogliono circa 0,3 secondi: pensi che ci sia un modo per renderlo più efficiente?

---

Edit: Dare Ogni thread proprio generatore

Ho modificato la routine come segue

void unifRandVectorThreadRoutine 
    (std::vector<unsigned int>& vector, unsigned int start, 
    unsigned int end, std::uniform_int_distribution<>& dist) 
{ 
    std::mt19937_64 generator{rd()}; 
    for(unsigned int i = start ; i < end ; ++i) 
    { 
     vector[i] = dist(generator); 
    } 
} 

e il tempo di esecuzione è sceso della metà. Quindi sto ancora condividendo il std::random_device ma ogni thread ha il suo std::mt19937_64.

---

Edit: Dando ogni thread proprio vettore e quindi concatenando

ho cambiato il codice come segue:

void unifRandVectorThreadRoutine 
    (std::vector<unsigned int>& vector, unsigned int length, 
    std::uniform_int_distribution<>& dist) 
{ 
    vector.reserve(length); 
    std::mt19937_64 generator{rd()}; 
    for(unsigned int i = 0 ; i < length ; ++i) 
    { 
     vector.push_back(dist(generator)); 
    } 
} 

e

std::vector<unsigned int> uniformRandomVector 
    (unsigned int rows, unsigned int columns, unsigned long long int modulus) 
{ 
    std::uniform_int_distribution<> dist = initialize(modulus); 

    std::thread threads[NUM_THREADS]; 

    std::vector<unsigned int> v[NUM_THREADS]; 

    unsigned int positionsEachThread = rows*columns/NUM_THREADS; 

    // all but the last thread 
    for(unsigned int i = 0 ; i < NUM_THREADS - 1 ; ++i) 
    { 
     threads[i] = std::thread(unifRandVectorThreadRoutine, std::ref(v[i]), positionsEachThread, dist); 
    } 

    // last thread 
    threads[NUM_THREADS - 1] = std::thread(unifRandVectorThreadRoutine, std::ref(v[NUM_THREADS-1]), 
     rows*columns - (NUM_THREADS-1)*positionsEachThread, dist); 

    for(unsigned int i = 0 ; i < NUM_THREADS ; ++i) 
    { 
     threads[i].join(); 
    } 

    std::vector<unsigned int> finalVector; 
    finalVector.reserve(rows*columns); 

    for(unsigned int i = 0 ; i < NUM_THREADS ; ++i) 
    { 
     finalVector.insert(finalVector.end(), v[i].begin(), v[i].end()); 
    } 

    return finalVector; 
} 

Il tempo di esecuzione è un po 'peggio di prima, quando stavo usando un solo vettore condiviso tra tutti i thread. Mi manca qualcosa o può succedere?

---

Edit: utilizzando un PRNG diversa + benchmark

Utilizzando un diverso PRNG (come suggerito in alcuni commenti/risposte) aiuta molto: ho provato con il xorshift+ e qui è l'implementazione Sono utilizzando:

class xorShift128PlusGenerator 
{ 
public: 
    xorShift128PlusGenerator() 
    { 
     state[0] = rd(); 
     state[1] = rd(); 
    }; 


    unsigned long int next() 
    { 
     unsigned long int x = state[0]; 
     unsigned long int const y = state[1]; 
     state[0] = y; 
     x ^= x << 23; // a 
     state[1] = x^y^(x >> 17)^(y >> 26); // b, c 
     return state[1] + y; 
    } 


private: 
    std::random_device rd; // seed generator 
    unsigned long int state[2]; 

}; 

l'esame di routine è la seguente

void unifRandVectorThreadRoutine 
    (std::vector<unsigned int>& vector, unsigned int start, 
    unsigned int end) 
{ 
    xorShift128PlusGenerator prng; 
    for(unsigned int i = start ; i < end ; ++i) 
    { 
     vector[i] = prng.next(); 
    } 
} 

Dato che ora sono a casa e sto usando una macchina diversa (e più potente), ho rifatto i test per confrontare i risultati. Ecco cosa ottengo:

• Mersenne Twister con un generatore per thread: 0,075 secondi
• xorshift128 + condivisa tra tutte le discussioni: 0.023 secondi
• xorshift128 + con un generatore per thread: 0.023 secondi

Nota: il tempo di esecuzione varia ad ogni ripetizione. Questi sono solo valori tipici.

Quindi non sembra esserci differenza se il generatore di xorshift è condiviso o meno, ma con tutti questi miglioramenti il ​​tempo di esecuzione è diminuito in modo significativo.

Answer 1

Il generatore std::mt19937_64 generator{rd()}; è condiviso tra le discussioni. Ci sarà uno stato condiviso che richiede l'aggiornamento in esso, quindi la contesa; c'è una corsa di dati. Dovresti anche cercare di consentire a ciascun thread di utilizzare il proprio generatore: dovrai solo assicurarti che generino sequenze separate.

È possibile che si sia verificato un problema di contesa della cache intorno a std::vector<unsigned int> v;, viene dichiarato all'esterno dei thread e quindi viene colpito con ogni iterazione del ciclo for in ciascun thread. Lascia che ogni thread abbia il proprio vettore da riempire, una volta che tutti i thread sono stati completati, collima i loro risultati nel vettore v. Forse tramite std::future sarà il più veloce. La dimensione esatta della contesa dipende dalle dimensioni della linea della cache e dalla dimensione del vettore utilizzato (e segmentato).

In questo caso si riempie un numero elevato di elementi (7734500) con un numero relativamente piccolo di thread (4), il rapporto potrebbe portare a un minor numero di contese.

W.r.t. il numero di thread che potresti usare, dovresti considerare di legare lo NUM_THREADS alla concorrenza hardware disponibile sulla destinazione; Ad esempio std::thread::hardware_concurrency().

Quando si ha a che fare con un numero elevato di elementi, si potrebbe anche cercare di evitare inizializzazioni non necessarie e lo spostamento dei risultati (anche se il tipo int, la mossa è meno evidente qui). Anche il contenitore stesso è qualcosa di cui essere consapevole; vector richiede memoria contigua, quindi eventuali elementi aggiuntivi (durante una fase di coalizione) potrebbero causare allocazione e copia della memoria.

La velocità del generatore di numeri casuali può anche avere un impatto, altre implementazioni e/o algoritmi possono influire sui tempi di esecuzione finali in modo significativo da essere considerati.

Come sempre con tutte le domande basate sulle prestazioni - la soluzione finale richiede misurazione. Implementare le possibili soluzioni, misurare i processori e gli ambienti target e adattarli fino a quando non si trova una prestazione adeguata.

Answer 2

Il generatore Mersenne Twister (std::mt19937_64) non è troppo veloce. Potresti prendere in considerazione altri generatori come Xorshift +. Vedi, ad es., Questa domanda: What is performance-wise the best way to generate random bools? (la discussione là va oltre i semplici bool).

E dovresti sbarazzarti della corsa dati nel tuo codice. Utilizzare un generatore per thread.

Answer 3

std::vector<unsigned int> v; 
    v.resize(rows*columns); 

Purtroppo, std::vector::resize primitive valore intialize così, rendendo il programma una volta sola scrivere zeri sulla memoria vettore, quindi ignorando questo valore con i numeri casuali.

provare std::vector::reserve + std::vector::push_back.
significa che i thread non possono più condividere il vettore senza un blocco, ma è possibile assegnare a ciascuno il proprio vettore, utilizzare reserve+push_back quindi combinare tutti i risultati in un vettore più grande.

se ciò non è sufficiente, e odio dire che, utilizzare std::unique_ptr con malloc (con deleter costume). sì, questo è C, sì questo è cattivo, sì, abbiamo new[], ma lo malloc non azzererà la memoria (a differenza dei contenitori new[] e stl), quindi puoi dividere i segmenti della memoria in ogni thread e lasciarlo generare numero casuale su di esso.risparmierai combinando i vettori con un vettore combinato.