Cosa può rallentare l'esecuzione di un programma quando si usano più thread?

https://stackoverflow.com/questions/612860

03-07-2019
|

Domanda

Questa domanda riguarda lo stesso programma di cui precedentemente chiesto . Per ricapitolare, ho un programma con una struttura ad anello come questa:

for (int i1 = 0; i1 < N; i1++)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        histogram[bin_index(i1, i2, i3, i4)] += 1;

bin_index è una funzione completamente deterministica dei suoi argomenti che, ai fini di questa domanda, non usa né cambia alcuno stato condiviso - in altre parole, è manifestamente rientrato.

Ho prima scritto questo programma per usare un singolo thread. Quindi l'ho convertito per utilizzare più thread, in modo che il thread n esegua tutte le iterazioni del ciclo esterno in cui i1% nthreads == n . Quindi la funzione che viene eseguita in ogni thread sembra

for (int i1 = n; i1 < N; i1 += nthreads)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        thread_local_histogram[bin_index(i1, i2, i3, i4)] += 1;

e tutti i thread_local_histogram vengono aggiunti nel thread principale alla fine.

Ecco la cosa strana: quando eseguo il programma con solo 1 thread per una determinata dimensione del calcolo, ci vogliono circa 6 secondi. Quando lo eseguo con 2 o 3 thread, facendo esattamente lo stesso calcolo, ci vogliono circa 9 secondi. Perché? Mi aspetto che l'utilizzo di 2 thread sia più veloce di 1 thread poiché ho una CPU dual-core. Il programma non utilizza mutex o altre primitive di sincronizzazione, quindi due thread dovrebbero essere in grado di funzionare in parallelo.

Per riferimento: output tipico da time (presente su Linux) per un thread:

real    0m5.968s
user    0m5.856s
sys     0m0.064s

e due thread:

real    0m9.128s
user    0m10.129s
sys     0m6.576s

Il codice è all'indirizzo http://static.ellipsix.net/ext-tmp /distintegral.ccs

P.S. So che ci sono librerie progettate esattamente per questo tipo di cose che probabilmente potrebbero avere prestazioni migliori, ma è questa la mia ultima domanda, quindi non ho bisogno di sentire di nuovo quei suggerimenti. (Inoltre volevo usare pthreads come esperienza di apprendimento.)

Soluzione

Tutto ciò che ho detto finora nella mia altra risposta è ancora vero in generale, poiché la tua domanda era cosa "posso" ... tuttavia ora che ho visto il tuo codice reale, la mia prima scommessa sarebbe che il tuo utilizzo di la funzione random () rallenta tutto. Perché?

Vedi, random mantiene in memoria una variabile globale che memorizza l'ultimo valore casuale calcolato lì. Ogni volta che chiami random () (e lo chiami due volte all'interno di una singola funzione) legge il valore di questa variabile globale, esegue un calcolo (che non è così veloce; random () da solo è una funzione lenta) e scrive il risultato laggiù prima di restituirlo. Questa variabile globale non è per thread, è condivisa tra tutti i thread. Quindi ciò che ho scritto sull'avvelenamento da cache si applica sempre qui (anche se lo hai evitato per l'array avendo array separati per thread; questo è stato molto intelligente da parte tua!). Questo valore viene costantemente invalidato nella cache di entrambi i core e deve essere recuperato dalla memoria. Tuttavia, se hai solo un singolo thread, non succede nulla del genere, questa variabile non lascia mai la cache dopo che è stata inizialmente letta, dal momento che ha accesso permanente ancora e ancora e ancora.

Inoltre, per rendere le cose ancora peggiori, glibc ha una versione thread-random di random () - l'ho appena verificato guardando la fonte. Mentre questa sembra essere una buona idea in pratica, significa che ogni chiamata random () causerà il blocco di un mutex, l'accesso alla memoria e lo sblocco di un mutex. Pertanto due thread che chiamano casuali esattamente nello stesso momento causeranno il blocco di un thread per un paio di cicli della CPU. Questo è specifico dell'implementazione, tuttavia, poiché AFAIK non è necessario che random () sia thread-safe. La maggior parte delle funzioni lib standard non è richiesta per essere thread-safe, poiché lo standard C non è nemmeno a conoscenza del concetto di thread in primo luogo. Quando non lo chiamano nello stesso momento, il mutex non avrà alcuna influenza sulla velocità (poiché anche una singola app con thread deve bloccare / sbloccare il mutex), ma si applicherà nuovamente l'avvelenamento da cache.

Puoi pre-costruire un array con numeri casuali per ogni thread, contenente tutti i numeri casuali di cui ogni thread ha bisogno. Crealo nel thread principale prima di generare i thread e aggiungi un riferimento al puntatore struttura che passi a ogni thread. Quindi ottieni i numeri casuali da lì.

Oppure implementa il tuo generatore di numeri casuali se non hai bisogno del "migliore" numeri casuali sul pianeta, che funziona con la memoria per thread per mantenere il suo stato - che si potrebbe essere anche più veloci del generatore integrato del sistema.

Se una sola soluzione Linux funziona per te, puoi usare random_r . Ti permette di passare lo stato ad ogni chiamata. Basta usare un oggetto stato univoco per thread. Tuttavia, questa funzione è un'estensione glibc, molto probabilmente non è supportata da altre piattaforme (né parte degli standard C né degli standard POSIX AFAIK - ad esempio questa funzione non esiste su Mac OS X, potrebbe non esistere in Solaris o FreeBSD).

La creazione di un proprio generatore di numeri casuali non è in realtà così difficile. Se hai bisogno di numeri casuali reali, non dovresti usare random () in primo luogo. Casuale crea solo numeri pseudo-casuali (numeri che sembrano casuali, ma sono prevedibili se si conosce lo stato interno del generatore). Ecco il codice per uno che produce buoni numeri casuali uint32:

static uint32_t getRandom(uint32_t * m_z, uint32_t * m_w)
{
    *m_z = 36969 * (*m_z & 65535) + (*m_z >> 16);
    *m_w = 18000 * (*m_w & 65535) + (*m_w >> 16);
    return (*m_z << 16) + *m_w;
}

È importante " seed " m_z e m_w in qualche modo corretto, altrimenti i risultati non sono affatto casuali. Il valore seme stesso dovrebbe già essere casuale, ma qui è possibile utilizzare il generatore di numeri casuali di sistema.

uint32_t m_z = random();
uint32_t m_w = random();
uint32_t nextRandom;

for (...) {
    nextRandom = getRandom(&m_z, &m_w);
    // ...
}

In questo modo ogni thread deve solo chiamare random () due volte e quindi usa il tuo generatore. A proposito, se hai bisogno di doppi random (che sono tra 0 e 1), la funzione sopra può essere facilmente racchiusa per questo:

static double getRandomDouble(uint32_t * m_z, uint32_t * m_w)
{
    // The magic number below is 1/(2^32 + 2).
    // The result is strictly between 0 and 1.
    return (getRandom(m_z, m_w) + 1) * 2.328306435454494e-10;
}

Prova a fare questa modifica nel tuo codice e fammi sapere come sono i risultati del benchmark :-)

Altri suggerimenti

Per evitare ulteriori commenti su questo: quando ho scritto la mia risposta, l'interrogante non ha ancora pubblicato un link alla sua fonte, quindi non ho potuto personalizzare la mia risposta ai suoi problemi specifici. Stavo solo rispondendo alla domanda generale su cosa "può " causa un tale problema, non ho mai detto che questo si applicherà necessariamente al suo caso. Quando ha pubblicato un link alla sua fonte, ho scritto un'altra risposta, che si concentra esattamente solo sul suo stesso problema (che è causato dall'uso della funzione random () come ho spiegato nell'altra mia risposta). Tuttavia, poiché la domanda di questo post è ancora " Cosa può rallentare l'esecuzione di un programma quando si usano più thread? & Quot; e non " Cosa rende lenta la mia specifica applicazione? " ;, non ho visto la necessità di cambiare la mia risposta piuttosto generale (domanda generale - > risposta generale, domanda specifica - > risposta specifica).

1) Avvelenamento da cache
Tutti i thread accedono allo stesso array, che è un blocco di memoria. Ogni core ha la propria cache per accelerare l'accesso alla memoria. Dal momento che non solo leggono dall'array ma cambiano anche il contenuto, il contenuto viene effettivamente modificato solo nella cache, non nella memoria reale (almeno non immediatamente). Il problema è che l'altro thread sull'altro core potrebbe avere parti sovrapposte di memoria nella cache. Se ora il core 1 cambia il valore nella cache, deve dire al core 2 che questo valore è appena cambiato. Lo fa invalidando il contenuto della cache sul core 2 e il core 2 deve rileggere i dati dalla memoria, il che rallenta l'elaborazione. L'avvelenamento da cache può avvenire solo su macchine multi-core o multi-CPU. Se hai solo una CPU con un core questo non è un problema. Quindi, per scoprire se questo è il tuo problema o meno, basta disabilitare un core (la maggior parte dei sistemi operativi ti permetterà di farlo) e ripetere il test. Se ora è quasi altrettanto veloce, questo è stato il tuo problema.

2) Prevenzione degli scoppi di memoria
La memoria viene letta più velocemente se letta in sequenza a raffica, proprio come quando i file vengono letti da HD. Affrontare un certo punto della memoria è in realtà terribilmente lento (proprio come il "tempo di ricerca" su un HD), anche se il tuo PC ha la migliore memoria sul mercato. Tuttavia, una volta affrontato questo punto, le letture sequenziali sono veloci. Il primo indirizzamento avviene inviando un indice di riga e un indice di colonna e avendo sempre tempi di attesa prima che sia possibile accedere ai primi dati. Una volta che questi dati sono lì, la CPU inizia a scoppiare. Mentre i dati sono ancora in corso, invia già la richiesta per il prossimo burst. Fintanto che mantiene il burst (inviando sempre le richieste "Next line per favore"), la RAM continuerà a pompare i dati il ??più velocemente possibile (e questo è in realtà abbastanza veloce!). Il bursting funziona solo se i dati vengono letti in sequenza e solo se gli indirizzi di memoria crescono verso l'alto (AFAIK non è possibile passare da indirizzi alti a indirizzi bassi). Se ora due thread vengono eseguiti contemporaneamente ed entrambi continuano a leggere / scrivere memoria, tuttavia entrambi da indirizzi di memoria completamente diversi, ogni volta che il thread 2 deve leggere / scrivere dati, deve interrompere un possibile scoppio del thread 1 e viceversa . Questo problema peggiora se hai ancora più thread e questo problema è anche un problema su un sistema che ha solo una CPU single-core.

BTW che esegue più thread di quanti ne abbia i core non renderà mai il tuo processo più veloce (come hai già detto 3 thread), piuttosto rallenterà (gli switch di contesto del thread hanno effetti collaterali che riducono il throughput di elaborazione) - a differenza di quanto esegui più thread perché alcuni thread sono inattivi o bloccati su determinati eventi e quindi non possono elaborare attivamente alcun dato. In tal caso potrebbe essere logico eseguire più thread di quanti ne siano i core.

Stai vedendo linea cache che rimbalza . Sono davvero sorpreso che non si ottengano risultati errati, a causa delle condizioni di gara sui secchi dell'istogramma.

Una possibilità è che il tempo impiegato per creare i thread superi i risparmi ottenuti utilizzando i thread. Penserei che N non sia molto grande, se il tempo trascorso è di soli 6 secondi per un'operazione O (n ^ 4).

Non esiste inoltre alcuna garanzia che più thread verranno eseguiti su core o CPU diversi. Non sono sicuro di quale sia l'affinità di thread predefinita con Linux: potrebbe che entrambi i thread vengano eseguiti su un singolo core, il che annullerebbe i vantaggi di un pezzo di codice ad alta intensità di CPU come questo.

Questo articolo descrive in dettaglio l'affinità di thread predefinita e come cambia il tuo codice per assicurarti che i thread vengano eseguiti su core specifici.

Anche se i thread non accedono contemporaneamente agli stessi elementi dell'array, l'intero array può trovarsi in alcune pagine di memoria. Quando un core / processore scrive su quella pagina, deve invalidare la sua cache per tutti gli altri processori.

Evita che molti thread lavorino sullo stesso spazio di memoria. Allocare dati separati per ogni thread su cui lavorare, quindi unirli insieme al termine del calcolo.

In cima alla mia testa:

Interruttori di contesto
Contesa di risorse
Contesa CPU (se non vengono divise in più CPU).
Blocco della cache

David,

Sei sicuro di eseguire un kernel che supporta più processori? Se nel tuo sistema viene utilizzato un solo processore, la generazione di thread aggiuntivi ad alta intensità di CPU rallenterà il tuo programma.

E sei sicuro che il supporto per i thread nel tuo sistema utilizzi effettivamente più processori? Top, ad esempio, mostra che entrambi i core del processore sono stati utilizzati durante l'esecuzione del programma?

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow