Qual è il modo più efficiente per coordinare i thread su quali thread sono liberi?
Sto lavorando a un programma che invia messaggi tra i thread, guarda quali thread sono occupati, se uno è libero prende il primo libero (o in alcuni casi più liberi), lo contrassegna come preso, gli invia del lavoro e fa il proprio lavoro, quindi una volta finito attende che venga completato. La parte che è il collo di bottiglia di tutto questo è il coordinamento tra i thread su quale thread viene preso. Sembra un problema, sono sicuro che altri hanno incontrato, hanno alcune soluzioni da condividere, ma voglio anche sapere se puoi fare meglio di me.
La mia soluzione alla fine si riduce a: mantenere un set che rappresenta gli indici di thread liberi ed essere in grado di prendere un elemento dal set ottenendo l'indice di un thread libero o aggiungerlo di nuovo al set aumentando la dimensione di uno. Ordine irrilevante. Conosco in anticipo la dimensione fissa del set.
Ho provato alcuni modi per farlo:
Mantieni un singolo int lungo lungo senza segno e usa '__builtin_clz' (Interessante __builtin_ffsll era 10 volte più lento .. pensare non supportato con una singola istruzione sul mio processore) per contare il numero di bit in un singolo ciclo di istruzioni e prendere quello più basso e tabella di ricerca di maschere di bit per attivare e disattivare i bit, richiedendo contemporaneamente il loro numero di thread. Mi è piaciuta questa versione perché avevo solo bisogno di condividere un singolo atomic unsigned long long e potevo usare una singola operazione atomica ma fare 'fetch_and' in un ciclo fino a quando non hai ragione ha finito per rallentare il blocco e fare in modo non atomico. La versione che utilizzava il blocco è risultata più veloce, probabilmente perché i thread non si sono bloccati in loop ripetendo le stesse operazioni in attesa che altri finissero le loro.
Usa una lista collegata, alloca tutti i nodi in anticipo, mantieni un nodo head e una lista, se punta a nullptr, allora abbiamo raggiunto la fine della lista. L'ho fatto solo con una serratura perché necessita di due operazioni simultanee.
Mantenere una matrice che rappresenta tutti gli indici dei thread da richiedere. Incrementa un indice di matrice e restituisci il puntatore precedente per richiedere un thread o scambia l'ultimo thread preso con quello che viene liberato e decrementa il puntatore. Controlla se è gratuito.
Usa la coda moodycamel che mantiene una coda senza blocchi.
Felice di condividere il codice C ++, la risposta stava diventando piuttosto lunga quando ho provato a includerlo.
Tutti e tre sono veloci, __builtin_clzll non è universalmente supportato, quindi anche se un po 'più veloce, probabilmente non abbastanza per valerne la pena e probabilmente 10 volte più lento su computer che non lo supportano nativamente, simile a come __builtin_ffsll era lento. L'array e l'elenco collegato sono più o meno veloci l'uno con l'altro, l'array sembra leggermente più veloce in assenza di conflitto. Moody è 3 volte più lento.
Pensi di poter fare di meglio e di avere un modo più veloce per farlo? È ancora la parte più lenta di questo processo, che in alcuni casi vale a malapena il costo.
Pensieri per indicazioni stradali da esplorare:
- Sembra che dovrebbe esserci un modo per usare un paio di atomici, forse un array di atomici, uno alla volta, deve mantenere l'integrità del set con ogni operazione, il che lo rende complicato. La maggior parte delle soluzioni ad un certo punto necessitano di due operazioni da eseguire contemporaneamente, sembra che le atomiche potrebbero fornire una soluzione significativamente più veloce rispetto al blocco nel mio benchmarking.
- Potrebbe essere in grado di utilizzare il blocco ma rimuovere la necessità di controllare se l'elenco è vuoto o di scambiare elementi nell'array
- Forse utilizzare una struttura dati diversa, ad esempio due array, aggiungerli a uno svuotando l'altro, quindi cambiare quello che viene riempito e quale viene svuotato. Ciò significa che non è necessario scambiare elementi, ma semplicemente scambiare due puntatori agli array e solo quando uno è vuoto.
- È possibile che i thread che avviano i thread aggiungano lavoro a un elenco di lavoro da fare, quindi un altro thread può prenderlo mentre questo thread continua. In definitiva, è ancora necessario un set thread safe simile.
- Guarda se le persone brillanti su StackOverflow vedono indicazioni per esplorare che non ho ancora visto :)
Risposte
Tutto ciò di cui hai bisogno è un pool di thread , una coda (a list, dequeo un ring buffer), a mutexe a condition_variableper segnalare quando un nuovo elemento di lavoro è stato aggiunto alla coda.
Avvolgi gli elementi di lavoro packaged_taskse devi attendere il risultato di ciascuna attività.
Quando si aggiunge un nuovo elemento di lavoro alla coda, 1) blocca il mutex, 2) aggiunge l'elemento, 3) rilascia il blocco e 4) chiama cv::notify_one, che sbloccherà il primo thread disponibile.
Una volta che la configurazione di base funziona, se le attività sono troppo dettagliate, è possibile aggiungere alla soluzione il furto di lavoro per migliorare le prestazioni. È anche importante utilizzare il thread principale per eseguire parte del lavoro invece di aspettare il completamento di tutte le attività. Queste semplici (anche se goffe) ottimizzazioni spesso comportano un miglioramento complessivo delle prestazioni> 15% a causa della riduzione del cambio di contesto.
Inoltre, non dimenticare di pensare alla falsa condivisione . Potrebbe essere una buona idea riempire gli elementi delle attività a 64 byte, solo per essere al sicuro.