Dovrei usare il threading e la ricorsione insieme?
-
03-07-2019 - |
Domanda
Ho armeggiato con alberi BSP da un po 'di tempo e sto anche giocando con i thread. Quando si aggiunge un triangolo a un albero BSP, si presenta l'opportunità di creare un nuovo thread allo scopo di elaborare i dati in parallelo.
insert(triangle, bspnode) { .... else if(triangle spans bspnode) { (frontpiece, backpiece) = plane_split(triangle, bspnode) insert(frontpiece, bspnode.front) insert(backpiece, bspnode.back) } .... }
Le due operazioni di inserimento sopra potrebbero essere eseguite da due thread e poiché non modificano gli stessi dati, è possibile utilizzare una sincronizzazione economica.
insert(triangle, bspnode) { .... else if(triangle spans bspnode) { (frontpiece, backpiece) = split(triangle, bspnode) handle = beginthread(insert(backpiece, bspnode.front)) insert(frontpiece, bspnode.back) if(handle) { waitforthread(handle) } else { insert(backpiece, bspnode.front) } } .... }
Questo nuovo metodo tenta di creare un thread per completare l'operazione in parallelo, ma non dovrebbe fallire se non è possibile creare il thread (tornerà semplicemente all'algoritmo originale).
È una buona pratica di programmazione o sto usando i thread in modo errato? Non sono stato in grado di trovare alcuna letteratura su questa tecnica. Mi piace che tende a utilizzare la mia CPU al massimo (2 core) e teoricamente si ridimensionerebbe a qualsiasi numero di processori disponibili. Non mi piace che potrebbe essere orribilmente dispendioso per CPU e memoria.
Soluzione
I thread sono fantastici se una parte dell'elaborazione sta aspettando qualcosa di esterno (input dell'utente, I / O, qualche altra elaborazione) - il thread che sta aspettando può continuare ad aspettare, mentre un thread che non sta aspettando prosegue .
Tuttavia, per le attività ad alta intensità di elaborazione, più thread che processori creano effettivamente sovraccarico. Sembra che i tuoi thread stiano facendo tutto il "lavoro della CPU", quindi mi atterrei a un thread per core - test per trovare il numero ottimale, tuttavia.
Il sovraccarico maggiore creato deriva dal cambio di contesto (congelamento di un thread e caricamento del contesto di esecuzione di quello successivo), nonché da errori della cache quando i thread eseguono attività con memoria diversa (se il thread può utilizzare efficacemente la cache della CPU) .
Altri suggerimenti
la soluzione migliore sarebbe quella di creare un pool di thread, quindi utilizzarlo 'in modo trasparente' per aggiungere nodi.
ad esempio, crea 2 thread all'avvio del programma, invitali ad attendere un semaforo o un evento. Quando si hanno nodi da aggiungere, i dati vengono inseriti in una coda, quindi si attiva il semaforo. Questo riattiva uno dei thread che estrae i dati dalla coda ed esegue l'elaborazione. (assicurati che l'accesso alla coda sia sicuro per i thread - è meglio sincronizzare completamente con una sezione critica).
Le prestazioni complessive della tua app sono più lente poiché hai più sovraccarico, copiando i dati nella coda ed eseguendo i thread extra, ma se hai usato l'esecuzione su un singolo core ora funzionerai su 2. Funziona meglio se l'elaborazione con thread è costosa.
Certo, ad esempio, Quicksort può essere programmato in modalità multithread abbastanza facilmente e ottenere grandi guadagni in termini di prestazioni su sistemi multi-core e alcune piccole perdite in termini di prestazioni in non-multithread. Ricorda solo che stai aggiungendo due volte overhead: una volta per il salvataggio dello stack nella ricorsione e una volta nel thread, quindi se stai facendo un gran numero di ricorsioni, potrebbe sopraffare un sistema più velocemente di un approccio non multithread.