Y a-t-il une mise en œuvre de remplissage d'inondation parallèle?

Question

J'ai ouvert MPMP et MPI, et je me demandais si quelqu'un a rencontré une version parallèle de tout algorithme de remplissage d'inondation (de préférence en c). Sinon, je serais intéressé par des croquis de la façon de le faire paralléliser - est-ce même possible étant donné qu'il est basé sur la récursivité?

Wikipédia a une très bonne article si vous avez besoin de vous rafraîchir la mémoire sur les remplissages d'inondation.

Un grand merci pour votre aide.

Answer 1

Il n'y a rien de "intrinsèquement" récursif à propos de l'inondation, mais juste pour faire un peu de travail, vous avez besoin d'informations sur les cellules "frontalières" découvertes précédemment. Si vous y réfléchissez, il est clair que le parallélisme est éminemment possible: même avec une seule file d'attente, vous pouvez utiliser quatre threads (un pour chaque direction) et ne déplacer la queue que lorsque la cellule a été examinée par chaque fil. ou de manière équivalente, quatre files d'attente. En pensant de cette façon, on pourrait même imaginer partitionner l'espace en plusieurs files d'attente - seau par des plages de coordonnées, peut-être.

Un problème fondamental est que la définition du problème inclut généralement la condition qu'aucune cellule n'est jamais revisitée. cela implique que chaque travailleur a besoin d'une carte mise à jour des cellules considérées (globalement). l'information globale mutable est problématique, en termes de performances, bien qu'il ne soit pas difficile de penser à des moyens de limiter la nécessité de propager des mises à jour globalement ...