La suddivisione di un programma in 4 thread è più lento di un singolo thread

Question

Ho scritto un raytracer la scorsa settimana, e sono arrivato a un punto in cui è sufficiente che il multi-threading avrebbe senso.Ho provato con OpenMP per parallelizzare, ma con più thread è effettivamente più lento in esecuzione con uno.

Leggendo altre domande simili, in particolare circa la OpenMP, un suggerimento è stato che il gcc ottimizza il codice seriale di meglio.Tuttavia l'esecuzione di codice compilato sotto con export OMP_NUM_THREADS=1 è due volte più veloce con export OMP_NUM_THREADS=4.I. e.È lo stesso codice compilato in entrambe le corse.

Esecuzione del programma con time:

> export OMP_NUM_THREADS=1; time ./raytracer
real    0m34.344s
user    0m34.310s
sys     0m0.008s


> export OMP_NUM_THREADS=4; time ./raytracer
real    0m53.189s
user    0m20.677s
sys     0m0.096s

Tempo utente è molto più piccolo di quello reale, insolito caso di utilizzo di più core utente dovrebbe essere più grande reale come più nuclei sono in esecuzione allo stesso tempo.

Il codice che ho eseguito in parallelo utilizzando OpenMP

void Raytracer::render( Camera& cam ) {

    // let the camera know to use this raytracer for probing the scene
    cam.setSamplingFunc(getSamplingFunction());

    int i, j;

    #pragma omp parallel private(i, j)
    {

        // Construct a ray for each pixel.
        #pragma omp for schedule(dynamic, 4)
        for (i = 0; i < cam.height(); ++i) {
            for (j = 0; j < cam.width(); ++j) {
                cam.computePixel(i, j);
            }
        }
    }
}

Durante la lettura questa domanda Pensavo di aver trovato la mia risposta.Si parla della realizzazione di gclib rand() sincronizzazione chiama a sé per conservare stato per la generazione di un numero casuale tra i thread.Sto usando la funzione rand() un bel po di monte carlo di campionamento, così ho pensato che era il problema.Mi sono liberato di chiamate a rand, la loro sostituzione con un unico valore, ma utilizzando più thread è ancora più lento. EDIT:oops si rivelasse non ho provato questo correttamente, è stato l'valori casuali!

Ora che coloro che sono fuori del modo, vorrei discutere una panoramica di quello che viene fatto su ogni chiamata a computePixel, quindi speriamo che possa essere trovata una soluzione.

Nel mio raytracer io, essenzialmente, una scena albero, con tutti gli oggetti in esso.Questo albero è attraversato un sacco durante computePixel quando gli oggetti vengono testati per intersezione, tuttavia, non scrive sono fatto per questo albero, oggetti. computePixel essenzialmente si legge in scena un mucchio di volte, il richiamo di metodi su oggetti (che sono const metodi), e alla fine scrive un singolo valore alla propria pixel array.Questa è l'unica parte che io sono a conoscenza di dove più di un thread provare a scrivere alla stessa variabile membro.Non c'è sincronizzazione ovunque dal momento che due thread non può scrivere alla stessa cella nella matrice di pixel.

Qualcuno può suggerire luoghi in cui ci potrebbe essere una sorta di contesa?Cose da provare?

Vi ringrazio in anticipo.

EDIT: Mi dispiace, è stato stupido a non fornire più info sul mio sistema.

• Compilatore gcc 4.6 (con -O2 ottimizzazione)
• Linux Ubuntu 11.10
• OpenMP 3
• Intel i3-2310M Quad core 2.1 Ghz (sul mio portatile al momento)

Codice per il calcolo dei pixel:

class Camera {

    // constructors destructors
    private:
        // this is the array that is being written to, but not read from.
        Colour* _sensor; // allocated using new at construction.
}

void Camera::computePixel(int i, int j) const {

    Colour col;

    // simple code to construct appropriate ray for the pixel
    Ray3D ray(/* params */);
    col += _sceneSamplingFunc(ray); // calls a const method that traverses scene. 

    _sensor[i*_scrWidth+j] += col;
}

Tra le proposte, potrebbe essere l'albero di attraversamento che causa il rallentamento.Alcuni altri aspetti:c'è un bel po ' di ricorsione coinvolte una volta la funzione di campionamento è chiamato (ricorsiva di rimbalzo di raggi)- questo potrebbe essere la causa di questi problemi?

Answer 1

Grazie a tutti per i suggerimenti, ma dopo ulteriori analisi e sbarazzarsi di altri fattori, di generazione di numeri casuali fatto girare fuori per essere il colpevole.

Come indicato nella domanda di cui sopra, rand() ha bisogno di tenere traccia del suo stato da una chiamata e l'altra.Se più thread stanno cercando di modificare questo stato, sarebbe causa di una race condition, quindi, l'implementazione di default in glibc è blocco su ogni chiamata, per rendere la funzione thread-safe.Questo è terribile per le prestazioni.

Purtroppo le soluzioni a questo problema che ho visto su stackoverflow sono tutti locali, vale a direaffrontare il problema nel campo di applicazione in cui rand() viene chiamato.Invece io propongo un "quick and dirty" soluzione che chiunque può utilizzare il programma per implementare indipendente per la generazione di numeri casuali per ogni thread, che non richiede la sincronizzazione.

Ho provato il codice e funziona - non c'è nessun blocco e nessun evidente rallentamento a seguito delle chiamate per threadrand.Sentitevi liberi di segnalare eventuali palesi errori.

threadrand.h

#ifndef _THREAD_RAND_H_
#define _THREAD_RAND_H_

// max number of thread states to store
const int maxThreadNum = 100;

void init_threadrand();

// requires openmp, for thread number
int threadrand();

#endif // _THREAD_RAND_H_

threadrand.cpp

#include "threadrand.h"
#include <cstdlib>
#include <boost/scoped_ptr.hpp>
#include <omp.h>

// can be replaced with array of ordinary pointers, but need to
// explicitly delete previous pointer allocations, and do null checks.
//
// Importantly, the double indirection tries to avoid putting all the
// thread states on the same cache line, which would cause cache invalidations
// to occur on other cores every time rand_r would modify the state.
// (i.e. false sharing)
// A better implementation would be to store each state in a structure
// that is the size of a cache line
static boost::scoped_ptr<unsigned int> randThreadStates[maxThreadNum];

// reinitialize the array of thread state pointers, with random
// seed values.
void init_threadrand() {
    for (int i = 0; i < maxThreadNum; ++i) {
        randThreadStates[i].reset(new unsigned int(std::rand()));
    }
}

// requires openmp, for thread number, to index into array of states.
int threadrand() {
    int i = omp_get_thread_num();
    return rand_r(randThreadStates[i].get());
}

Ora è possibile inizializzare gli stati casuali per i thread main utilizzando init_threadrand(), e , successivamente, ottenere un numero casuale utilizzando threadrand() quando si utilizza diversi thread in OpenMP.

Answer 2

La risposta è, senza sapere di che macchina si sta eseguendo su questo, e senza vedere il codice del tuo computePixel funzione che dipende.

C'è piuttosto un paio di fattori che potrebbero influenzare le prestazioni del codice, una cosa che mi viene in mente è la cache di allineamento.Forse, strutture di dati, e ha fatto parlare di un albero, non sono proprio l'ideale per la memorizzazione nella cache, e la CPU finisce l'attesa per i dati dalla RAM, dato che non vanno bene le cose in cache.Sbagliato cache-line allineamenti potrebbe causare qualcosa di simile.Se la CPU è di aspettare che le cose vengono da RAM, è probabile che il thread sarà contesto acceso, ed un altro verrà eseguito.

Il sistema operativo thread scheduler è non deterministico, quindi, quando un thread l'esecuzione non è una cosa prevedibile, quindi, se si dà il caso che il tuo thread non sono in esecuzione di un molto, o si contendono i core della CPU, questo potrebbe anche rallentare le cose.

Affinità di Thread, svolge anche un ruolo.Un thread sarà pianificata su un particolare nucleo, e normalmente si cercherà di mantenere questo thread sullo stesso core.Se più di uno dei tuoi thread sono in esecuzione su un singolo core, si troveranno a dover condividere la stessa base.Un'altra ragione per cui le cose potrebbero rallentare.Per motivi di prestazioni, una volta che un thread particolare è stato eseguito sulla base di un nucleo, di norma viene tenuto lì, a meno che non ci sia un buon motivo per sostituirlo con un altro nucleo.

C'è qualche altro fattore, che non ricordo largo della parte superiore della mia testa, però, vi consiglio di fare qualche lettura sulla filettatura.Si tratta di un complicato e vasto argomento.C'è un sacco di materiale là fuori.

Sono i dati che vengono scritti alla fine, i dati che altri thread bisogno di essere in grado di fare computePixel ?

Answer 3

Una forte possibilità è false condivisione.Sembra che si sta calcolando il pixel in sequenza, quindi ogni thread potrebbe essere al lavoro su interleaved pixel.Questo è di solito una cosa molto brutta da fare.

Quello che potrebbe accadere è che ogni thread sta tentando di scrivere il valore di un pixel l'uno accanto all'scritto in un altro thread (sono tutti di scrivere la matrice del sensore).Se questi due valori di output condividere la stessa CPU cache-per la linea di forza la CPU a svuotare la cache tra i processori.Questo si traduce in una quantità eccessiva di vampate di calore tra Cpu, che è relativamente lento.

Per risolvere questo problema è necessario assicurarsi che ogni thread funziona veramente su una regione autonoma.Adesso sembra si divide su più righe (io non sono positive in quanto non so OMP).Se questo funziona dipende da quanto è grande la tua righe sono-ma ancora alla fine di ogni riga si sovrappongono con l'inizio del successivo (in termini di linee di cache).Si potrebbe desiderare di provare a suddividere l'immagine in quattro blocchi e ogni thread lavoro su una serie sequenziale di righe (per come 1..10 11..20 21..30 31..40).Questo consentirebbe di ridurre notevolmente la condivisione.

Non preoccuparti per la lettura di dati costante.Così a lungo come il blocco di dati non viene modificato ogni thread può leggere le informazioni in modo efficiente.Tuttavia, essere diffidenti di ogni mutevole dati nella costante di dati.

Answer 4

Ho appena guardato e il Intel i3-2310M in realtà non hanno 4 core, ha 2 core e hyper-threading.Provare a eseguire il codice con solo 2 fili e vedi che aiuta.Trovo che, in generale, la tecnologia hyper-threading è totalmente inutile, quando si hanno un sacco di calcoli, e sul mio portatile ho spento ed ho ottenuto molto meglio di tempi di compilazione dei miei progetti.

Infatti, basta andare nel BIOS e disattivare l'HT-non è utile per lo sviluppo/macchine di calcolo.