In teoria, find_end è parallelizzabile?

Question

Attualmente sto lavorando su un open-std proposal per portare funzionalità parallele al progetto su cui sto lavorando, ma ho incontrato un blocco stradale con find_end.

Ora find_end può essere descritto come:

Un algoritmo che cerca l'ultimo sottosequenza di elementi [s_first, s_last) nel gamma [first, last). La prima versione utilizza l'operatore == per confrontare gli elementi , la seconda versione utilizza il predicato binario dato p.

i requisiti sono stabiliti da cppreference. Ora non ho avuto problemi nel parallelizzare find/findif/findifnot ecc. Questi potrebbero facilmente essere suddivisi in partizioni separate che sono state eseguite in modo asincrono e non ho avuto problemi. Il problema con find_end è che dividere l'algoritmo in blocchi non è una soluzione, perché se abbiamo dire un vettore:

1 2 3 4 5 1 2 3 8

e vogliamo cercare 1 2.

Ok per prima cosa ho separato il vettore in blocchi in modo asincrono e ho appena cercato l'intervallo in ogni chunk giusto? Sembrava abbastanza facile per me, ma cosa succede se per qualche ragione ci sono solo 3 core disponibili, quindi il vettore è diviso in 3 blocchi:

1 2 3 | 4 5 1 | 2 3 8

Ora ho un problema, il secondo intervallo 1 2 è suddiviso in diverse partizioni. Questo porterà a molti risultati non validi per qualcuno che ha una quantità di core x che finisce per dividere i risultati della ricerca in y partizioni diverse. Stavo pensando che avrei fatto una specie di search chunks -> merge y chunks into y/2 chunks -> search -> in una ricerca ricorsiva di stile, ma questo sembra solo così inefficiente, l'intero punto di questo algoritmo è quello di migliorare l'efficienza . Potrei essere troppo pensieroso per questo calvario

tl; dr, c'è un modo per parallelizzare lo find_end in un modo a cui non sto pensando?

Answer 1

Sì, c'è un modo.

Lascia che N sia la dimensione dell'intervallo che stai cercando.

Dopo aver separato il vostro vettore in 3 pezzi (3 thread di lavoro indipendente):

1 2 3|4 5 1|2 3 8 

È possibile consentire ogni thread per eseguire in tutta la sua giusta pezzo adiacente (se presente) per n-1 elementi (poiché solo le operazioni di lettura sono coinvolte nella sequenza, ciò è perfettamente corretto e sicuro per i thread).

In questo caso: (N = 2)

• core 1 corsa sul 1 2 3 4

• Core 2 corsa su 4 5 1 2

• Core 3 corsa su 2 3 8

Answer 2

Poiché il punto find_end è quello di trovare l'occorrenza di un ago in un pagliaio , la parallelizzazione suddividendo il pagliaio in segmenti contigui spesso non produce alcun vantaggio perché se l'ago si trova effettivamente nell'ultimo segmento, il il lavoro svolto da tutti i processori diversi da quello assegnato all'ultimo segmento viene sprecato e il tempo è esattamente lo stesso di quello che sarebbe stato con un singolo processore. In teoria, la valutazione parallela consente di limitare il tempo massimo di ricerca, il che è vantaggioso se (1) i processori non sono in competizione per altri compiti e (2) ci sono relativamente poche istanze dell'ago nel pagliaio.

Inoltre, è necessario essere in grado di coordinare la fine del processo; ogni processo può abbandonare la ricerca quando trova una corrispondenza o quando il fratello minore ha trovato una corrispondenza o abbandonato la ricerca. Una volta che il processo 0 ha trovato una corrispondenza o ha esaurito i luoghi per cercarli, il processo con indice più basso con una corrispondenza vince.

Un'alternativa è l'interleave delle ricerche. Se si dispone k processori, allora il processore 0 viene proposta le sequenze che terminano last-0, last-k, last-2k ..., processore 1 è dato le sequenze che terminano alle last-1, last-k-1, last-2k-1 ... e in processore generico i (0 ≤ i < k) funziona su last-i, last-k-i, last-2k-i ...

Il coordinamento del processo è leggermente diverso dalla prima alternativa. Ancora una volta, ogni singolo processo può interrompersi non appena trova una corrispondenza. Inoltre, qualsiasi processo può interrompersi non appena il suo target attuale è inferiore all'ultima corrispondenza trovata da un altro processo.

Mentre ciò dovrebbe portare a una ragionevole parallelizzazione della ricerca, non è chiaro per me che sarà meglio di un algoritmo lineare non parallelizzato come Knuth-Morris-Pratt o Boyer-Moore, uno dei quali può essere banalmente modificato per cercare da destra a sinistra. Questi algoritmi saranno particolarmente utili nel caso non raro in cui l'ago è una costante in fase di compilazione, consentendo la possibilità di precomporre le tabelle di cambio necessarie. La parallelizzazione non interlacciata può beneficiare di KMP o BM, con lo stesso avvertimento di cui sopra: è probabile che la maggior parte del processo partecipante si riveli non utile.