Ho openMP e MPI a mia disposizione, e lo sono statochiedendosi se qualcuno ha trovato una versione parallela di un algoritmo di riempimento flood (preferibilmente in c). In caso contrario, sarei interessato a schizzi su come farlo parallelizzare - è persino possibile dato il suo basato sulla ricorsione?
Wikipedia è abbastanza buono articolo se hai bisogno di rinfrescare la memoria sui riempimenti di piena.
Molte grazie per il vostro aiuto.
risposte:
4 per risposta № 1Non c'è niente di "intrinsecamente" ricorsivoflood-fill, solo che per fare un po 'di lavoro, hai bisogno di informazioni sulle celle "di frontiera" precedentemente scoperte. Se ci pensi in questo modo, è chiaro che il parallelismo è eminentemente possibile: anche con una singola coda, puoi usare quattro thread (uno per ogni direzione) e spostare solo la coda della coda quando la cella è stata esaminata da ogni thread o equivalentemente, quattro code, pensando in questo modo, si potrebbe anche immaginare di suddividere lo spazio in più code, magari con intervalli di coordinate.
un problema di base è che la definizione del problemadi solito include la condizione che nessuna cella venga mai rivista. questo implica che ogni lavoratore ha bisogno di una mappa aggiornata di quali celle sono state considerate (globalmente). le informazioni globali mutabili sono problematiche, in termini di prestazioni, anche se non è difficile pensare a modi per limitare la necessità di propagare gli aggiornamenti a livello globale ...