Dichiarazione di non responsabilità: se non sei interessato alla parallelizzazione (sui cluster), questa domanda probabilmente non ti interessa e probabilmente non vale la pena leggerla.
TL; DR: cerco un modello di comunicazione (preferibilmente compatibile con MPI ) che assicuri in modo efficiente che ogni riga di dati venga elaborata una volta. Leggi anche il prossimo paragrafo per sapere cosa intendo per linea di dati.
Si consideri il seguente problema: Un algoritmo prende una linea di dati (nel mio caso, una matrice di numeri interi con dimensione fissa) e produce varie linee di dati che poi devono essere elaborate dallo stesso algoritmo. Ogni riga dati univoca deve essere elaborata solo una volta, poiché l'esito è puramente deterministico. L'insieme di linee dati univoche è finito, quindi dopo un numero finito di chiamate ricorsive di questo algoritmo produce l'intero set. L'obiettivo è trovare questo set.
Ho già implementato l'algoritmo e ho anche implementato una parallelizzazione. Ovviamente, dal momento che è necessario elaborare ogni riga di dati univoca , in ogni momento tutte le linee di dati attualmente non elaborate possono essere elaborate da processori diversi in parallelo.
D'altra parte, la parallelizzazione introduce il problema di impedire ai diversi processori di eseguire lavori ridondanti.
Un'implementazione banale dovrebbe inviare linee di dati ai processori, raccogliere tutti i risultati e distribuire nuovamente. Questo può essere inefficiente dal momento che gli elenchi dei risultati (possibilmente di grandi dimensioni) devono essere uniti prima che qualsiasi ulteriore lavoro possa essere svolto. Se tutti gli elenchi vengono restituiti nello stesso periodo, il master viene sopraffatto dalla mera quantità di dati mentre tutti gli slave rimangono inattivi fino al completamento di tutte le operazioni di fusione.
Il mio modello di comunicazione (per quanto mi sembra, migliorato) è ancora fondamentalmente Master-Slave:
Questo è ciò che fa il Maestro:
Distribute initial chunk of data lines to slaves
While there is at least one active slave
for each active slave
Request data line
if slave doesn't have a data line
set slave inactive, break
else
if the data line was previously processed
break
endif
if there is an inactive slave
send the data line to inactive slave and mark that slave as active
send the sending slave a notification to not process the data line
else
notify the slave to process the data line it just sent
endif
endif
endfor
endwhile
Ogni slave fa questo:
while true
wait for request
if data line available
send it
wait for master to say if the line should be processed here
process if necessary
go back to beginning
else
notify master
wait for master to send a data line
process the received line
go back to beginning
endif
Lo slave gestisce il proprio elenco locale di righe di dati elaborate e non elaborate. Per ogni richiesta, un elemento di quelli non elaborati viene spostato in quelli elaborati. Solo le voci univoche tra i due elenchi sono memorizzate.
In conclusione: solo il master conosce l'intero set di linee elaborate. uno slave elabora una linea dati se e solo se il master dice che non è stato elaborato in precedenza. Il Master non conosce i risultati per ciascuna linea di dati finché non ha richiesto tutte le linee disponibili da ciascun slave.
Per quanto posso pensare, questo modello di comunicazione dell'elenco di linee dati elaborate è piuttosto efficiente, ma sono nuovo nel mondo della parallelizzazione, specialmente nel mondo della parallelizzazione su un cluster.
Quali sono altri modi per comunicare in modo efficiente le linee dati tra più processori per garantire che ogni riga di dati venga elaborata esattamente una volta?
Questa domanda non è fondamentalmente legata alla combinazione di C++ e MPI , anche se qualsiasi risposta che riflette il modo in cui funziona l'interfaccia Message Passing è molto apprezzata.