Sto codificando un'implementazione di Hash-Life in C ++ 14 e sto lavorando su un'implementazione multi-thread. Ha un potenziale evidente per il multi-threading. L'attività può essere suddivisa in essenzialmente 13 sotto-attività. 9 dei compiti sono in gran parte indipendenti e gli altri 4 dipendono da 4 dei 9 ma non l'uno dall'altro. Uno fa 9 (parallelo) che torna insieme per fare 4 (parallelo).
Il processo è in realtà ricorsivo, quindi quei 13 si scomporranno in 13 di loro fino a un livello 'banale' che è appena calcolato dalla forza bruta. Ad ogni livello di ricorsione le attività si riducono e sembra probabile che ci sia un punto in cui il multitasking perde il suo ritorno e l'algoritmo dovrebbe andare in sequenza. Ma questo è un dettaglio. Immagina di scomporre più livelli di parallelismo.
L'intera faccenda è solo l'accattonaggio per essere passati attraverso un pool di thread di lavoro.
Ciò che sto invitando sono le idee sui modi intelligenti di gestirlo.
Un pool di thread di base non funzionerà perché c'è un rischio (in pratica inevitabile) di un deadlock interessante. Se si esegue il troncamento di un'attività in 13 attività e si attende che vengano completate (o dodici e eseguite una serie o qualsiasi altra cosa), si inviterà a una situazione di stallo. Essenzialmente si finirà con tutti i thread in attesa di attività non avviate nella coda che non verranno mai avviate perché tutti i thread sono in attesa di attività non avviate nella coda che .... e così via. Hai bisogno di un numero maggiore di thread rispetto alle attività e mentre è possibile creare i thread, non è un modello efficiente e confrontato con i risultati di uno scambio di thread eccessivo.
Questo mi sembra un problema potenzialmente generico. Un modello base di pool di thread termina al meglio con i produttori e i lavoratori di n (task), ma questa è una situazione produttore-consumatore che sembra un modo naturale per parallelizzare la ricorsione e non è coperto da questo caso.
La mia idea principale è quella di evitare un deadlock quando un operatore si rende conto che è necessario completare un'attività per continuare e tale attività non viene avviata riprendendo l'attività e completandola in serie (deadlock evitato).
C'è una caratteristica interessante qui che significa che piuttosto che dormire e permettere ad un altro thread di essere scambiato in thread tenderà a rimanere attivi e tirare dentro il lavoro. C'è anche lo scopo di stimare la più grande attività non avviata e iniziare quella prima riducendo così il percorso critico e riduzione del tempo massimizzando l'utilizzo.
Lo svantaggio è che c'è un sovraccarico nel mettere un'attività in una coda se poi viene estratta e terminata nel thread che l'ha inviata. Ci sono modi per mitigarlo.
Il mio problema è che tutta la ricerca che posso fare non tornerà con nessuna analisi di questo tipo di problema.
Le persone desiderano infinitamente rastrellare il problema separato Producer vs Consumer e non riesco a trovare il modo di coprire questo modello ricorsivo che sembra così naturale.
Considerando un modello di "consumatori che sono essi stessi produttori" che sto cercando:
- Risorse (modelli, documenti, blog, codice, ecc.) che trattano questo problema.
- Proposte, approfondimenti o riflessioni.
- Commenti o idee.
Questo è particolarmente in considerazione per evitare il deadlock che l'uso 'ingenuo' di un 'thread' di base invita gli inviti.
C ++ 14 non è importante qui eccetto che ho una discreta libreria di threading a portata di mano.
Ho una soluzione giocattolo che risolve il problema di sommare i numeri 1 - n dividendo ricorsivamente l'intervallo e aggiungendo le parti in C ++ e sono pronto a condividere ma è un po 'troppo lungo per inserire questo post.